수학적 귀납법과 불변식

타일이 연속해서 넘어지려면 첫 타일이 넘어져야 하고, 각 타일이 다음 타일을 넘어뜨려야 합니다. 수학적 귀납법도 이 두 조건을 모두 요구합니다. 직접증명을 바탕으로 자연수에 대한 전체 명제를 증명합니다.

귀납 가정은 결론을 미리 믿는 것이 아니다

$n\ge1$에 대해 $P(n)$을 증명하려면 P(1)을 먼저 확인하고, 임의의 $k\ge1$에 대해 P(k)가 참이라 가정했을 때 P(k+1)도 참임을 증명합니다. 두 조건이 합쳐져 P(1),P(2),P(3),…가 이어집니다. 귀납 단계만 있으면 첫 연결점이 없어 전체 결론을 얻지 못합니다.

명제: $1+2+\cdots+n=n(n+1)/2$.

기초 n=1에서는 양변이 1입니다. 귀납 가정으로 $1+\cdots+k=k(k+1)/2$를 둡니다. 다음 수 k+1을 더하면

$$1+\cdots+k+(k+1)=\frac{k(k+1)}2+(k+1) =\frac{(k+1)(k+2)}2.$$

마지막 식은 n=k+1일 때의 목표입니다. 가정이 쓰인 위치는 긴 합을 $k(k+1)/2$로 바꾼 줄입니다. k+1의 결과를 처음부터 가정하지 않습니다.

부등식에는 시작 범위가 중요하다

$2^n\ge n+1$은 $n\ge0$에서 참입니다. n=0에서 1≥1입니다. $2^k\ge k+1$을 가정하면 $2^{k+1}\ge2k+2\ge k+2$입니다. 마지막 비교는 k≥0이므로 참입니다. 단순히 '지수가 커지니까 된다' 대신 필요한 부등식을 두 줄로 이어 씁니다.

강한 귀납법은 P(k) 하나 대신 시작값부터 P(k)까지 전부를 가정합니다. $n\ge2$인 모든 정수가 소수의 곱으로 표현됨을 생각해 봅시다. 기초 n=2는 2 자체가 소수이므로 성립합니다. $2\le m\le k$인 모든 정수 m이 분해된다고 가정하고 k+1을 봅니다. k+1이 소수면 그 자체가 곱입니다. 합성수면 k+1=ab이며 $2\le a,b<k+1$라서 두 인수는 가정의 범위에 있습니다. 가정으로 a와 b를 소수의 곱으로 분해하고 두 곱을 이어 k+1의 분해를 얻습니다. 더 작은 두 정수의 분해를 사용할 수 있으므로 강한 가정이 자연스럽습니다. 일반 귀납법과 증명력은 같지만 쓰기 편한 문제가 다릅니다.

반복문을 읽는 귀납적 질문

1부터 n까지 더하는 반복문에서 i번째 반복 직후 누적합이 $1+\cdots+i$라는 성질은 불변식입니다. 반복 전 i=0에는 합이 0이고, 다음 반복에서 i+1을 더하면 성질이 유지됩니다. 반복 종료 때 i=n이면 원하는 결과입니다. 종료한다는 사실은 별도로 반복 횟수 n의 유한성으로 설명합니다. 불변식 유지 자체가 종료를 보장하지 않습니다.

스스로 풀어보기

문제 1. $1+3+\cdots+(2n-1)=n^2$를 n≥1에서 증명하세요.

힌트: 다음 홀수는 2k+1입니다.

풀이: 기초 n=1은 1=1입니다. k개의 합이 k²라고 가정하면 다음까지의 합은 $k^2+(2k+1)=(k+1)^2$입니다. 마지막 식이 k+1의 명제이므로 귀납법으로 성립합니다.

문제 2. P(k)→P(k+1)만 증명하면 모든 자연수에서 참이라고 말할 수 없는 이유를 예로 설명하세요.

풀이: P(n)을 'n은 n+1보다 크다'로 두면 모든 n에서 거짓입니다. P(k)가 거짓이므로 조건명제 P(k)→P(k+1)는 참으로 계산되지만 P(0)은 거짓입니다. 기초 단계가 없으면 거짓 명제들을 잇는 조건도 통과할 수 있습니다.

귀납 단계가 막히면 목표 P(k+1)을 따로 적고 P(k)와 다른 부분만 찾으세요. 트리의 구조적 반복은 트리, 알고리즘 불변식은 탐색으로 연결됩니다.