フィボナッチ数列の指数評価

方針

解答

⓪ 発想 — どう考え始めるか。 $F_{n+2}=F_{n+1}+F_n$ は2項前までを使う漸化式。だから帰納法も「$n=k,k+1$ の両方を仮定して $n=k+2$ を示す」2段仮定型が噛み合う(出発点の確認も $n=1,2$ の2つ必要)。

仮定を漸化式に入れると ${\left(\frac{7}{4}\right)}^{k+1}+{\left(\frac{7}{4}\right)}^k$。共通因数 ${\left(\frac{7}{4}\right)}^k$ をくくれば、示すべきことは

$$\frac{7}{4}+1\le {\left(\frac{7}{4}\right)}^2$$

というただの数の比較1つに潰れる。$\frac{44}{16}\le \frac{49}{16}$ ✓。この1点の余裕が帰納の歯車を回す。

① 出発点。 $F_1=1<\frac{7}{4}$ ✓、$F_2=1<{\left(\frac{7}{4}\right)}^2=\frac{49}{16}$ ✓。

② 帰納の段。 ある $k$ で $F_k<{\left(\frac{7}{4}\right)}^k$ と $F_{k+1}<{\left(\frac{7}{4}\right)}^{k+1}$ をともに仮定する。漸化式より

$$F_{k+2}=F_{k+1}+F_k<{\left(\frac{7}{4}\right)}^{k+1}+{\left(\frac{7}{4}\right)}^k={\left(\frac{7}{4}\right)}^k\left(\frac{7}{4}+1\right)={\left(\frac{7}{4}\right)}^k\cdot \frac{11}{4}$$

③ 定数の比較で締める。 $\frac{11}{4}=\frac{44}{16}\le \frac{49}{16}={\left(\frac{7}{4}\right)}^2$ だから

$$F_{k+2}<{\left(\frac{7}{4}\right)}^k\cdot {\left(\frac{7}{4}\right)}^2={\left(\frac{7}{4}\right)}^{k+2}$$

よって $n=k+2$ でも成立。①②③より、すべての自然数 $n$ で $F_n<{\left(\frac{7}{4}\right)}^n$。

まとめ: 「漸化式が2項使うなら、仮定も2つ・出発点も2つ」— 帰納法の設計は漸化式の形が決める。締めの比較 $r+1\le r^2$ は $r\ge \frac{1+\sqrt{5}}{2}$(黄金比)で成り立つ — $\frac{7}{4}$ がぎりぎりではなく少し余裕のある定数であること、そして黄金比がフィボナッチの真の成長率であることが、この1行に透けて見える。

発展 — 一歩先へ。 同じ設計図を逆向きに使うと、下からの評価も作れる。$r=\frac{3}{2}$ は $r+1>r^2$($\frac{5}{2}>\frac{9}{4}$)を満たすから、$F_{k+2}\ge {\left(\frac{3}{2}\right)}^{k-1}+{\left(\frac{3}{2}\right)}^{k-2}>{\left(\frac{3}{2}\right)}^k$ が回り、$F_n\ge {\left(\frac{3}{2}\right)}^{n-2}$。フィボナッチ数列は ${\left(\frac{3}{2}\right)}^n$ と ${\left(\frac{7}{4}\right)}^n$ の指数関数ではさまれ、真の成長率はその間の黄金比 $\phi =1.618\cdots$($F_{n+1}/F_n\to \phi$)になっている。

別解

黄金比で「ぴったり回る」評価を作る(なぜ $\frac{7}{4}$ で通るかの種明かし)。 じつはもっと鋭い不等式が、同じ設計図で証明できる。$\phi =\frac{1+\sqrt{5}}{2}$(黄金比、${\phi }^2=\phi +1$)として

$$F_n\le {\phi }^{n-1}$$

出発点: $F_1=1={\phi }^0$、$F_2=1\le \phi$ ✓。帰納の段:

$$F_{k+2}\le {\phi }^k+{\phi }^{k-1}={\phi }^{k-1}(\phi +1)={\phi }^{k-1}\cdot {\phi }^2={\phi }^{k+1}$$

${\phi }^2=\phi +1$ が等号で成り立つから、評価が一切緩まずに回る。これが黄金比の特別さだ。

あとは $\phi <\frac{7}{4}$ から $F_n\le {\phi }^{n-1}<{\left(\frac{7}{4}\right)}^{n-1}<{\left(\frac{7}{4}\right)}^n$ で、元の不等式が従う。

本解の比較 $r+1\le r^2$ が成り立つ境目こそ $r=\phi$。$\frac{7}{4}$ という定数は「黄金比より少し大きいから通る」— 問題の裏にある本当の境界線が、この別解で見える。