수학적 귀납법

수학적 귀납법은 축소 논리이다

$n=k$일때를 이용해서 $n=k+1$로 확장하지 말고, $n=k+1$를 이용해서 $n=k$를 증명하라.

• 김일희 박사, 수학적 귀납법 99.99% "엉터리"로 배웠습니다..
• 김일희 박사, 어디서도 보기 힘든 절묘한 수학적 귀납법의 활용 (귀납가설을 다섯번 활용?).

트리로 증명

명제: 트리의의 점 개수가 $n$이면 선 개수는 $n-1$이다.

• 트리가 $2 \le n$면 단말이 존재한다.
• 트리에서 단말을 없애도 여전히 트리이다.

위를 이용하면:

1. 명제가 참이라고 가정함
2. $n=1$일 때, 선의 개수는 $0 = n-1$로 참.
3. $n = k + 1$인 트리가 있다면, 선의 개수는 $k$여야 함.
4. 위의 트리에서 단말을 없앤 트리는 $n=k$이고, 가정에 의해 선의 개수는 $k-1$임.
5. 단말을 없애면 선도 없어지니 $n=k+1 \Rightarrow k$가 맞음.

n까지의 합으로 증명

명제: $1 + 2 + \cdots + n=\frac{n(n+1)}{2}$

1. 명제가 참이라고 가정함.
2. $n=1$일 때, $1=\frac{2}{2}$이므로 참.
3. $n=k+1$이라고 하면, $1+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2}$이어야 함.
4. 가설에 의해 $(1+\cdots+k)+(k+1)=\frac{k(k+1)}{2} + (k+1)$
5. 우변의 식을 정리하면 $\frac{(k+1)(k+2)}{2}$이므로 모순이 없으니 명제가 참임.