強い帰納法（2項以上仮定）
P(1) と「P(1), P(2), …, P(k) を仮定して P(k+1) を導く」でも結論できます。
フィボナッチ数列の性質などに使います。
📘 例題① フィボナッチ数列 F_1=F_2=1、F_{n+2}=F_{n+1}+F_n について、F_n < 2ⁿ を示せ。
解答：n=1,2：1<2、1<4 OK。
n=k, k+1 で成り立つと仮定 → F_{k+2} = F_{k+1}+F_k < 2ᵏ⁺¹+2ᵏ = 3·2ᵏ < 4·2ᵏ = 2ᵏ⁺².
ゆえに F_n < 2ⁿ。
解答：n=1,2：1<2、1<4 OK。
n=k, k+1 で成り立つと仮定 → F_{k+2} = F_{k+1}+F_k < 2ᵏ⁺¹+2ᵏ = 3·2ᵏ < 4·2ᵏ = 2ᵏ⁺².
ゆえに F_n < 2ⁿ。
💡 ポイント
- 漸化式が 2項離れているときは2項仮定の強い帰納法
練習問題
- F_n を F_{n+2}=F_{n+1}+F_n、F_1=F_2=1 で定義。F_3, F_4, F_5 は？
解答・解説
- 解答：F_3=2、F_4=3、F_5=5