수학적 귀납법 (proof by induction)

컴퓨터과학·AI

한 줄 정의: 어떤 명제가 기본 경우(base case)에서 성립함을 보이고, 임의의 n에서 성립한다고 가정했을 때 n+1에서도 성립함을 보임으로써 모든 자연수(또는 재귀적 구조)에 대해 명제가 성립함을 증명하는 방법.

쉽게 풀면

수학적 귀납법은 도미노가 쓰러지는 원리에 비유할 수 있다. 첫 번째 도미노가 쓰러진다는 것(기본 경우)과, 어떤 도미노가 쓰러지면 반드시 다음 도미노도 쓰러진다는 것(귀납 단계)만 보이면, 무한히 많은 도미노가 모두 쓰러진다는 것을 증명할 수 있다. 컴퓨터과학에서는 알고리즘의 정확성을 증명하거나, 재귀적으로 정의된 자료구조(리스트, 트리 등)의 성질을 증명할 때 이 기법을 구조적 귀납법의 형태로 자주 사용한다.

왜 중요한가

수학적 귀납법은 재귀적으로 정의되는 자연수, 리스트, 트리 등 무한히 많은 경우를 유한한 두 단계(기본 경우와 귀납 단계)로 압축해 증명할 수 있게 해주기 때문에, 알고리즘의 정확성 증명, 프로그래밍 언어의 타입 안전성 증명, 정형 검증처럼 "모든 입력에 대해 성립함"을 엄밀히 보여야 하는 컴퓨터과학·이산수학 연구에서 필수적인 도구로 쓰인다. 특히 재귀 구조를 다루는 프로그램 검증에서는 구조적 귀납법이라는 형태로 거의 표준적으로 사용된다.

논문에서는 이렇게 쓰입니다

"본 정렬 알고리즘의 정확성은 입력 크기에 대한 수학적 귀납법을 통해 증명되었다."

재귀 알고리즘이나 재귀적 자료구조에 대한 성질을 엄밀하게 증명하는 표준 기법으로 인용된다.

"이진트리의 구조에 대한 귀납법을 적용하여, 제안한 순회 알고리즘이 모든 노드를 정확히 한 번씩 방문함을 증명하였다."

자료구조 분야에서 재귀적으로 정의된 트리나 그래프의 성질을 구조적 귀납법으로 증명할 때 쓰이는 표현입니다.

"타입 시스템의 진행성(progress)과 보존성(preservation) 정리는 항의 구조에 대한 귀납법을 통해 증명되며, 이를 통해 타입 안전성이 보장된다."

프로그래밍 언어 이론 분야에서 타입 시스템의 안전성을 증명하는 표준적인 방식으로도 자주 사용됩니다.

조금 더 깊게 보면

수학적 귀납법에는 n에서 n+1로 넘어갈 때 바로 이전 경우 하나만 가정하는 약한 귀납법과, n보다 작은 모든 경우가 성립한다고 가정하는 강한 귀납법(완전 귀납법)이 있으며, 자료구조가 재귀적으로 여러 하위 구조로 나뉘는 경우에는 강한 귀납법에 해당하는 구조적 귀납법이 더 자연스럽게 쓰인다. 타입 이론에서는 이러한 귀납적 증명 방식이 재귀적 프로그램의 구성과 형식적으로 대응된다는 커리-하워드 대응 관점에서도 논의된다.

주의할 점

기본 경우를 빠뜨리거나 귀납 단계에서 암묵적으로 잘못된 가정을 사용하면 증명 전체가 무효가 되므로, 두 단계 모두 엄밀하게 검토해야 한다.