フィボナッチ数列の一般項(ビネーの公式)
フィボナッチ数列の漸化式 $a_{n+2} = a_{n+1} + a_n$, $a_1=a_2=1$ から一般項を導いてみよう。
ビネーの公式
フィボナッチ数列 $\{a_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\}$$
フィボナッチ数列の漸化式 $a_{n+2} = a_{n+1} + a_n$ から一般項を導く解法
- $\displaystyle \alpha = \frac{1+\sqrt{5}}{2}$ と $\displaystyle \beta = \frac{1-\sqrt{5}}{2}$ によって, 漸化式を次の形に変形する:$$\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}$$
- 数列 $\{ a_{n+1} - \alpha a_{n} \}_n$ は初項 $a_2 - \alpha a_1 = \beta$, 公比 $\beta$ の等比数列と認識でき, $a_{n+1} - \alpha a_n$ $= \beta \cdot \beta^{n-1}$ が得られる.
- 数列 $\{ a_{n+1} - \beta a_{n} \}_n$ は初項 $a_2 - \beta a_1 = \alpha$, 公比 $\alpha$ の等比数列と認識でき, $a_{n+1} - \beta a_n$ $=\alpha \cdot \alpha^{n-1}$ が得られる.
- (2)の式 $a_{n+1} - \alpha a_n$ $=\beta^{n}$ と(3)の式 $a_{n+1} - \beta a_n$ $=\alpha^{n}$ から $a_{n+1}$ を消去することで $a_n$ $\displaystyle =\frac{1}{\alpha - \beta}(\alpha^n-\beta^n)$ を導く.
例題. 漸化式 $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}$$ と変形できる。
例えば, $a_{n+2} - \alpha a_{n+1} = \beta (a_{n+1} - \alpha a_n)$ を計算すると $a_{n+2} = (\alpha + \beta) a_{n+1} - \alpha \beta a_n$ となる。
実際に $\alpha + \beta = 1$, $- \alpha \beta = 1$ である。
$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}.$$
$b_1 = a_2 - \alpha a_1$ $= 1 - \frac{1 + \sqrt{5}}{2} \cdot 1$ $=\frac{1 - \sqrt{5}}{2}$ $=\beta$.
$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}.$$
$c_1 = a_2 - \beta a_1$ $= 1 - \frac{1 - \sqrt{5}}{2} \cdot 1$ $=\frac{1 + \sqrt{5}}{2}$ $=\alpha$.
以上から, $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$$ となる。
$-(\beta - \alpha)$ $\displaystyle= -\frac{1 - \sqrt{5}}{2} + \frac{1 + \sqrt{5}}{2}$ $= \sqrt{5}$.
ゆえに, $$a_n = \frac{1}{\sqrt{5}} \left\{ \left(\frac{1+\sqrt{5}}{2} \right)^n - \left(\frac{1-\sqrt{5}}{2} \right)^n \right\}$$ を得ることができる。
$\alpha = \frac{1 + \sqrt{5}}{2}$
$\beta = \frac{1 - \sqrt{5}}{2}$
とすると,
$\alpha + \beta =1$,
$\alpha \beta =-1$,
$\alpha - \beta = \sqrt{5}$
である。
$a_1$ $= \frac{1}{\sqrt{5}} (\alpha -\beta )$ $= \frac{1}{\sqrt{5}} \cdot \sqrt{5}$ $=1.$
$a_2$ $= \frac{1}{\sqrt{5}} (\alpha^2 -\beta^2 )$ $= \frac{1}{\sqrt{5}} (\alpha - \beta)(\alpha + \beta)$ $=1.$
$a_3$ $= \frac{1}{\sqrt{5}} (\alpha^3 -\beta^3 )$ $= \frac{1}{\sqrt{5}} (\alpha - \beta)$ $\{(\alpha + \beta)^2 - \alpha \beta \}$ $=2.$
