수학적 귀납법 (Mathematical Induction)
쉽게 풀면
도미노를 일렬로 세워놓고 전부 쓰러뜨리고 싶다고 해봅시다. 모든 도미노를 하나하나 손으로 밀 필요는 없습니다. 대신 두 가지만 확인하면 됩니다. 첫째, "첫 번째 도미노가 쓰러진다"(기초 단계). 둘째, "어떤 도미노가 쓰러지면 바로 다음 도미노도 반드시 쓰러진다"(귀납 단계). 이 두 가지만 참이면, 도미노는 처음부터 끝까지 전부 쓰러진다는 것이 논리적으로 보장됩니다. 수학적 귀납법도 똑같은 원리로, "n=1일 때 성립"과 "n=k일 때 성립하면 n=k+1일 때도 성립"이라는 두 단계만 증명해서 모든 자연수 n에 대한 성립을 보입니다.
왜 중요한가
수학적 귀납법은 무한히 많은 경우를 유한한 단계의 논증으로 정당화할 수 있게 해주기 때문에, 알고리즘의 정확성 증명, 자료구조의 불변조건 증명, 조합론적 항등식 증명 등 다양한 분야의 논문에서 표준적인 증명 도구로 쓰입니다. 특히 전산학에서는 재귀적으로 정의된 알고리즘이나 프로그램의 정확성을 보이는 데 필수적이며, 형식적 검증(formal verification) 연구에서도 핵심 뼈대를 이룹니다. 이 때문에 증명의 엄밀성을 요구하는 이론 논문일수록 귀납법의 기초 단계와 귀납 단계가 명시적으로 서술되어 있는지가 중요하게 다뤄집니다.
논문에서는 이렇게 쓰입니다
이 문장은 알고리즘의 기초 사례(가장 작은 입력)에서 정확성을 확인한 뒤, "n에서 성립하면 n+1에서도 성립한다"는 귀납 단계를 증명함으로써 모든 경우에 대한 정확성을 보였다는 뜻입니다. 전산학·수학 논문에서 알고리즘이나 수식의 일반적 성립을 증명할 때 흔히 쓰입니다.
이 문장은 자료구조 이론에서 트리와 같은 재귀적 구조의 성질을 증명할 때 귀납법이 자연스럽게 적용된다는 것을 보여줍니다. 구조가 재귀적으로 정의될수록 귀납법과의 대응이 직관적입니다.
이 문장에서 "강한 귀납법"은 n=k일 때뿐 아니라 그 이전의 모든 값에서 성립함을 가정해 다음 단계를 유도하는 변형된 형태로, 조합론이나 정수론 논문에서 종종 등장합니다.
조금 더 깊게 보면
수학적 귀납법에는 기본형 외에도 여러 변형이 있는데, n=k에서의 성립만 가정하는 대신 n보다 작은 모든 값에서의 성립을 가정하는 "강한 귀납법(strong induction)"이 대표적이며, 정수의 정렬성 원리(well-ordering principle)와 논리적으로 동치임이 알려져 있습니다. 또한 자연수뿐 아니라 트리, 리스트 같은 재귀적으로 정의된 구조에 대해서도 "구조적 귀납법(structural induction)"이라는 형태로 확장되어 전산학의 정확성 증명에 널리 쓰입니다. 논문을 읽을 때는 저자가 어떤 형태의 귀납법을 사용했는지, 그리고 기초 단계와 귀납 단계가 실제로 대상 명제 전체를 빠짐없이 덮는지 확인하는 것이 중요합니다.
주의할 점
가장 흔한 실수는 귀납 단계만 증명하고 기초 단계를 빠뜨리는 것입니다. 귀납 단계만으로는 "성립하는 경우가 이어진다"는 것만 보일 뿐, 애초에 어디서부터 성립하는지는 알 수 없습니다. 또한 귀납 단계에서 "n=k일 때 성립한다고 가정"하는 것은 결론을 미리 참으로 놓는 것이 아니라, 조건부로 다음 단계를 유도하기 위한 가정일 뿐이라는 점도 명제와 논리의 조건문 구조를 이해하면 명확해집니다.