フィボナッチ数列について

例題. 漸化式 $a_{n+2} = a_{n+1} + a_n$, $a_1=a_2=1$ から数列 $\{ a_n \}$ の一般項を導きなさい。

$a_{n+2} = a_{n+1} + a_n$ から $x^2 = x+1$ を考える。これを解くと $x=\frac{1+\sqrt{5}}{2}, \ \frac{1-\sqrt{5}}{2}$ となる。これらの値を $\alpha$, $\beta$ とする。

例題の漸化式は $$\begin{aligned} a_{n+2} - \alpha a_{n+1} &= \beta (a_{n+1} - \alpha a_n) \\ a_{n+2} - \beta a_{n+1} &= \alpha (a_{n+1} - \beta a_n) \end{aligned}$$ と変形できる。

$b_n = a_{n+1} - \alpha a_{n}$ と置くと, $b_{n+1} = \beta b_n$ が成り立つ。ゆえに, 数列 $\{ b_n \}$ は初項 $b_1 = a_2 - \alpha a_1 $, 公比 $\beta$ の等比数列である。したがって, 次が成り立つ。

$$b_{n} = (a_2 - \alpha a_1) \cdot \beta^{n-1}.$$

$c_n = a_{n+1} - \beta a_{n}$ と置くと, $c_{n+1} = \alpha c_n$ が成り立つ。ゆえに, 数列 $\{ c_n \}$ は初項 $c_1 = a_2 - \beta a_1 $, 公比 $\alpha$ の等比数列である。したがって, 次が成り立つ。

$$c_{n} = (a_2 - \beta a_1) \cdot \alpha^{n-1}.$$

以上から, $b_n = a_{n+1} - \alpha a_n$, $c_n = a_{n+1} - \beta a_n$ であったから, 次の２式を得ることができる。

$$\begin{aligned} a_{n+1} - \alpha a_n &= \beta \cdot \beta^{n-1} \\ a_{n+1} - \beta a_n &= \alpha \cdot \alpha^{n-1} \end{aligned}$$

$a_{n+1}$ を消去するために下の式の両辺から上の式の両辺をそれぞれ引くと, $$-(\beta- \alpha)a_n = \alpha^n - \beta^n$$ となる。

ゆえに, $$a_n = \frac{1}{\sqrt{5}} \left\{ \left(\frac{1+\sqrt{5}}{2} \right)^n - \left(\frac{1-\sqrt{5}}{2} \right)^n \right\}$$ を得ることができる。

証明.

数学的帰納法によって示す.

$n=1$ のとき, 左辺は $F_1 = 1$ である. 右辺は $F_3 -1 = 2-1 = 1$ である.

ゆえに, $n=1$ のとき, 示すべき等式は成り立つ.

$n=k \in \mathbb{N}$ のとき, $F_1 + \ldots + F_k = F_{k+2}-1$ が成り立つと仮定する.

$n = k+1$ のときについて,

$$\begin{aligned}
F_{n + 2}-1 &= F_{(k+1)+1}-1 \\
&= F_{k+2} +F_{k+1}-1 \\
&= F_{k+1} + (F_{k+2} - 1) \\
&= F_{k+1} + (F_{k} + \ldots + F_1) \\
&= F_{k+1} + \ldots + F_1 \\
&=F_n + \ldots + F_1
\end{aligned}$$

である。

ゆえに, $n=k+1$ のときも, 示すべき等式は成り立つ.

以上から, 数学的帰納法によって, 任意の自然数 $n$ について $F_1 + \ldots + F_n = F_{n+2}-1$ が成り立つ.

証明.

数学的帰納法によって示す.

$n=1$ のとき, 左辺は $F_1 = 1$ である. 右辺は $F_{2 \cdot 1} = 1$ である.

ゆえに, $n=1$ のとき, 示すべき等式は成り立つ.

$n=k \in \mathbb{N}$ のとき, $F_1 + F_3 + \ldots + F_{2k-1} = F_{2k} $ が成り立つと仮定する.

$n = k+1$ のときについて,

$$\begin{aligned}
F_{2n} &= F_{2(k+1)} \\
&= F_{2k+1} +F_{2k} \\
&= F_{2k+1} + (F_{2k-1} + \ldots +F_1) \\
&= F_{2n-1} + \ldots + F_1
\end{aligned}$$

である.

ゆえに, $n=k+1$ のときも, 示すべき等式は成り立つ.

以上から, 数学的帰納法によって, 任意の自然数 $n$ について $F_1 + F_3 + \ldots + F_{2n-1} = F_{2n} $ が成り立つ.

証明.

数学的帰納法によって示す.

$n=1$ のとき, 左辺は $F_2 = 1$ である. 右辺は $F_{2 \cdot 1 +1}-1 = 2-1=1$ である.

ゆえに, $n=1$ のとき, 示すべき等式は成り立つ.

$n=k \in \mathbb{N}$ のとき, $F_2 + F_4 + \ldots + F_{2k} = F_{2k+1}-1 $ が成り立つと仮定する.

$n = k+1$ のときについて,

$$\begin{aligned}
F_{2n+1} -1 &= F_{2(k+1)+1} -1 \\
&= F_{2k+3} -1 \\
&= F_{2k+2} +F_{2k+1}-1 \\
&= F_{2(k+1)} + (F_{2k} + \ldots +F_2) \\
&= F_{2(k+1)} + \ldots + F_2 \\
&= F_{2n} + \ldots + F_2 \\
\end{aligned}$$

である.

ゆえに, $n=k+1$ のときも, 示すべき等式は成り立つ.

以上から, 数学的帰納法によって, 任意の自然数 $n$ について $F_2 + F_4 + \ldots + F_{2n} = F_{2n+1}-1 $ が成り立つ.

証明.

数学的帰納法によって示す.

$n=1$ のとき, 左辺は $F_1^2 = 1$ である. 右辺は $F_1F_2 = 1 \cdot 1 =1$ である.

ゆえに, $n=1$ のとき, 示すべき等式は成り立つ.

$n=k \in \mathbb{N}$ のとき, $F_1^2 + \ldots + F_k^2 = F_kF_{k+1}$ が成り立つと仮定する.

$n = k+1$ のときについて,

$$\begin{aligned}
F_{n}F_{n + 1} &= F_{k+1}F_{k+2} \\
&= F_{k+1}(F_{k+1} + F_k) \\
&= F_{k+1}^2 + F_kF_{k+1} \\
&= F_{k+1}^2 + (F_{k}^2 + \ldots + F_1^2) \\
&= F_{k+1}^2 + \ldots + F_1^2 \\
&=F_n^2 + \ldots + F_1^2
\end{aligned}$$

である。

ゆえに, $n=k+1$ のときも, 示すべき等式は成り立つ.

以上から, 数学的帰納法によって, 任意の自然数 $n$ について $F_1^2 + \ldots + F_n^2 = F_{n}F_{n+1}$ が成り立つ.

証明.

フィボナッチ数列の一般項の式（ビネーの公式）を利用して命題を示す.

フィボナッチ数列の比を計算する.

$\begin{aligned}
&\frac{F_{n+1}}{F_n} \\
&=\frac{ \frac{1}{\sqrt{5}} \left\{ \phi^{n+1} - \left(-\phi^{-1} \right)^{n+1} \right\}}{ \frac{1}{\sqrt{5}} \left\{ \phi^n - \left(-\phi^{-1} \right)^n \right\}}\\
&=\frac{\phi^{n+1} - \left(-\phi^{-1} \right)^{n+1}}{\phi^n - \left(-\phi^{-1} \right)^n} \\
&=\frac{\phi + \phi^{-1}(-\phi^{-2})^{n}}{1 - (-\phi^{-2} )^n}
\end{aligned}$

最後の計算は分母と分子を $\phi^n$ で割っている.

ここで, $0<\phi^{-2}<1$ であるから,

$\displaystyle \lim_{n \to \infty} (-\phi^{-2})^n = 0$

が成り立つ.

ゆえに, $\displaystyle \lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \phi$ が成り立つ.

解説.

$a_n=\displaystyle \sum_{k=0}^{[\frac{n}{2}]}{}_{n-k} \mathrm{C}_k$ とする.

---

まず, $\{a_n\}_{n \leq 0}$ がパスカルの三角形に引いた $n$ 番目の直線上の数の和を表していることを示す.

$a_0=\displaystyle \sum_{k=0}^{0}{}_{0-k} \mathrm{C}_k$ $={}_0\mathrm{C}_0$ であるため, $a_0=1=F_1$ である.

$a_1=\displaystyle \sum_{k=0}^{0}{}_{1-k} \mathrm{C}_k$ $={}_1\mathrm{C}_0$ であるため, $a_1=1=F_2$ である.

さて, $n \geq 2$ として, $a_n$ の式を作る.

ある直線上の数のうち最も左の数が ${}_n\mathrm{C}_0$ であるとき, 直線上の次の数は「１つ上の段の１つ右の数」である. これは, ${}_{n-1} \mathrm{C}_1$ である.

同様に次の数は, ${}_{n-2}\mathrm{C}_2$ である. $k$ $(\geq 0)$ 番目の数は ${}_{n-k}\mathrm{C}_k$ である.

この数は $n-k \geq k$ である限り, パスカルの三角形上の数を表す. したがって, $\displaystyle k \leq \frac{n}{2}$ が必要である.

ゆえに, $\displaystyle \sum_{k=0}^{[\frac{n}{2}]}{}_{n-k} \mathrm{C}_k$ が直線上にある数の和を表すことが分かる.

---

次に, $n \geq 2$ として, $a_{n} = a_{n-1} + a_{n-2}$ であることを示す.

$n$ が偶数の場合, $\ell$ を整数として $n=2 \ell$ とする. このとき,

$a_n$ $\displaystyle =\sum_{k=0}^{\ell}{}_{2\ell-k} \mathrm{C}_k$ $\displaystyle = {}_{2\ell}\mathrm{C}_0 +\sum_{k=1}^{\ell-1}{}_{2\ell-k} \mathrm{C}_k+{}_{\ell} \mathrm{C}_\ell$ $\displaystyle = 2 +\sum_{k=1}^{\ell-1}{}_{2\ell-k} \mathrm{C}_k$

$a_{n-1}$ $\displaystyle =\sum_{k=0}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_k$ $\displaystyle ={}_{2\ell-1}\mathrm{C}_0+\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_k$ $\displaystyle =1+\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_k$

$a_{n-2}$ $\displaystyle =\sum_{k=0}^{\ell-1}{}_{(2\ell-2)-k} \mathrm{C}_k$ $\displaystyle =\sum_{k=1}^{\ell}{}_{(2\ell-2)-(k-1)} \mathrm{C}_{k-1}$ $\displaystyle =\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_{k-1}+{}_{\ell-1} \mathrm{C}_{\ell-1}$ $\displaystyle =\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_{k-1}+1$

である.

$a_{n-1}+a_{n-2}$ を計算すると,

$\displaystyle 1+\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_k$ $\displaystyle +\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_{k-1}+1$

$=\displaystyle 2+\sum_{k=1}^{\ell-1} \{{}_{(2\ell-1)-k}\mathrm{C}_k +{}_{(2\ell-1)-k} \mathrm{C}_{k-1} \}$

となる. 次の関係式を利用して, さらに計算すると,

${}_n\mathrm{C}_r +{}_n\mathrm{C}_{r+1} = {}_{n+1}\mathrm{C}_{r+1}$

$\displaystyle 2+\sum_{k=1}^{\ell-1} {}_{2\ell-k}\mathrm{C}_k$

となり, $a_n$ の式と等しいことが分かる.

また, $n$ が奇数のときも同様の議論が成り立つ.

以上から, $n\geq 2$ のとき, $a_{n} = a_{n-1}+a_{n-2}$ かつ $a_1=a_0=1$ であるから, $a_n = F_{n+1}$ である.