'강한' 귀납법?

일반 귀납법에서는 귀납 단계에서 P(n) -> P(n+1) 을 증명한다면 강한 귀납은 다음과 같이 증명한다.

1. P(0)이 참이고 (기본단계)
2. P(0),P(1),....,P(n) 모두가 참임이 P(n+1)을 함의한다면
3. P(m)도 마찬가지로 참이다.

예) 피보나치 수열

피보나치 수열은 수학자 피보나치가 13세기 초 인구 증가 모델(?)을 만들면서 생겼다고 한다. 파인애플 싹과 솔방울의 모양과 같은 자연의 많은 것들을 설명하는데 사용된다고 한다.

명제 : $F(n)$ is even IFF $F(n+3)$ is even

base case

피보나치 수열은 base case가 두 개 필요하다 : 0 일때와 1일때.

• n=0 : F(0) = 0 이고 F(3) = 2 로 둘 다 짝수다.
• n=1 : F(1) = 1 이고 F(4) = 3 으로 둘 다 짝수가 아니다.

귀납단계

어떤 수 m과 k가 있다고 하자.

$m + k$ is even IFF [m is even IFF k is even]. ((k가 짝수)일 경우에만 m도 짝수)일 경우에만 $m+k$도 짝수다. 즉 m과 k가 같은 홀짝성을 가질 경우에만 $m+k$는 짝수다.

강한 귀납은 0,1,...,n 까지 모든 경우가 P(n+1)을 함의한다는 것을 증명하는 방법이라고 했다.

1. $F(n+1)$ is even
2. IFF $F(n)+F(n-1)$ is even (def of $F(n+1)$)
3. IFF [$F(n)$ is even IFF $F(n-1)$ is even]
4. IFF [$F(n+3)$ is even IFF $F(n+2)$ is even] (by strong ind. hyp. $P(n),P(n-1)$)
5. IFF $F(n+3)+F(n+2)$ is even
6. IFF $F(n+4)$ is even.
   (by def of $F(n+4)$)

증명하려고 하는 명제는 F(n+1)의 경우, 즉 F(n+4)가 짝수인 경우에만 F(n+1)도 참이라는것.

• F(n+1)이 짝수라는 것은 F(n) + F(n-1)이 짝수라는 의미고,
• F(n) + F(n-1) 이 짝수라는 의미는 F(n-1)과 F(n)가 같은 홀짝성을 가진다는 의미이고, (위의 m,k 명제)
• F(n-1)과 F(n)이 같은 홀짝성을 가진다는 것은 거기에 같은 숫자를 더한다고 해도 (가령 3씩 더해 F(n+2)와 F(n+3) 모두) 같은 홀짝성을 가진다는 의미이고,
• F(n+2)와 F(n+3)이 같은 홀짝성을 가진다는 것은 그 다음 수열인 F(n+4)라는 의미다.