準備

数列$\set{u_n}$をフィボナッチ数列とします. すなわち $\set{u_n}$で以下の条件で定められる数列です:

\[\begin{align} u_1 = 1, \quad u_2 = 1, \\ u_{n + 2} = u_n + u_{n + 1}. \end{align}\]

このとき, 数列$\set{u_n}$の一般項を求めてみましょう.

なお, 都合上

\[\alpha = \frac{1 + \sqrt{5}}{2}, \quad \beta = \frac{1 - \sqrt{5}}{2}\]

と置きます.

すると

\[\alpha + \beta = 1, \quad \alpha - \beta = \sqrt{5}, \quad \alpha \beta = -1\]

が成り立ちます.

特定方程式による解法

\[u_{n + 2} = u_n + u_{n + 1}\]

だったので 特定方程式は

\[c^2 = 1 + c\]

です. これを解くと

\[c = \alpha, \beta\]

を得ます. よって数列$\set{u_n}$の一般項は

\[u_n = \lambda_1 \alpha^{n - 1} + \lambda_2 \beta^{n - 1}\]

で与えられます. ただし, ここで $\lambda_1, \lambda_2$は適当な実数です.

$u_1 = 1$より

\[\lambda_1 + \lambda_2 = 1\]

を得ます. また, $u_2 = 1$より

\[\lambda_1 \alpha + \lambda_2 \beta = 1\]

を得ます.

この二式を連立方程式と見て解くと

\[\lambda_1 = \frac{1 + \sqrt{5}}{2\sqrt{5}} = \frac{1}{\sqrt{5}} \alpha, \quad \lambda_2 = \frac{1 - \sqrt{5}}{2\sqrt{5}} = \frac{1}{\sqrt{5}} \beta\]

を得ます. 以上によって

\[\begin{align} u_n &= \lambda_1 \alpha^{n - 1} + \lambda_2 \beta^{n - 1} \\ &= \frac{1}{\sqrt{5}} \alpha^n - \frac{1}{\sqrt{5}}\beta^n \\ &= \frac{1}{\sqrt{5}} (\alpha^n - \beta^n) \end{align}\]

を得ます.

行列による解法

\[u_{n + 2} = u_n + u_{n + 1}\]

より

\[\begin{pmatrix} u_{n + 2} \\ u_{n + 1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} u_n \\ u_{n + 1} \end{pmatrix}\]

を得ます.

よって

\[A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\]

とおくと

\[\begin{align} \begin{pmatrix} u_{n + 2} \\ u_{n + 1} \end{pmatrix} &= A \begin{pmatrix} u_n \\ u_{n + 1} \end{pmatrix} \\ &= A^2 \begin{pmatrix} u_{n - 1} \\ u_n \end{pmatrix} \\ &= \cdots \\ &= A^n \begin{pmatrix} u_1 \\ u_2 \end{pmatrix} = A^n \begin{pmatrix} 1 \\ 1 \end{pmatrix} \end{align}\]

が成り立ちます.

ここで 対角化を利用して$A^n$を計算してみましょう.

このとき $A$の固有方程式は

\[\begin{align} \det(\lambda E - A) &= \det \begin{pmatrix} \lambda - 1 & -1 \\ -1 & \lambda \end{pmatrix} \\ &= \lambda^2 - \lambda - 1 = (\lambda - \alpha)(\lambda - \beta) = 0 \end{align}\]

となるので, $A$の固有値は $\alpha, \beta$となります.

それぞれについて計算すると, 固有値$\alpha$に対しては$(1, -\beta)$が, 固有値$\beta$に対しては$(1, -\alpha)$が固有ベクトルであることが分かります.

よって

\[P = \begin{pmatrix} 1 & 1 \\ -\beta & -\alpha \end{pmatrix}\]

と置くと

\[P^{-1}AP = \begin{pmatrix} \alpha & \\ & \beta \end{pmatrix}\]

なので

\[A^n = P \begin{pmatrix} \alpha^n & \\ & \beta^n \end{pmatrix}P^{-1}.\]

ここで

\[\begin{align} P^{-1} &= \frac{1}{\beta - \alpha}\begin{pmatrix} -\alpha & -1 \\ \beta & 1 \end{pmatrix} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} -\alpha & -1 \\ \beta & 1 \end{pmatrix} \end{align}\]

であるから

\[\begin{align} A^n &= P \begin{pmatrix} \alpha^n & \\ & \beta^n \end{pmatrix} P ^{-1} \\ &= \begin{pmatrix} 1 & 1 \\ -\beta & -\alpha \end{pmatrix} \begin{pmatrix} \alpha^n & \\ & \beta^n \end{pmatrix}\cdot \frac{1}{\sqrt{5}} \begin{pmatrix} -\alpha & -1 \\ \beta & 1 \end{pmatrix} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \beta^{n + 1} - \alpha^{n + 1} & \beta^n - \alpha^n \\ \alpha^{n + 1} \beta - \alpha \beta^{n + 1} & \alpha^n \beta - \alpha \beta^n \end{pmatrix}. \end{align}\]

を得ます. ここで $\alpha\beta = -1$なので

\[\begin{align} A^n &= \frac1{\sqrt{5}} \begin{pmatrix} \beta^{n + 1} - \alpha^{n + 1} & \beta^n - \alpha^n \\ -\alpha^n + \beta^n & -\alpha^{n - 1} + \beta^{n - 1} \end{pmatrix}. \end{align}\]

よって

\[\begin{align} \begin{pmatrix} x_{n + 2} \\ x_{n + 1} \end{pmatrix} &= \frac1{\sqrt{5}} \begin{pmatrix} \alpha^{n + 1} - \beta^{n + 1} & \alpha^n - \beta^n \\ \alpha^n - \beta^n & \alpha^{n - 1} - \beta^{n - 1} \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} \\ &= \frac1{\sqrt{5}} \begin{pmatrix} \alpha^{n + 1} - \beta^{n + 1} + \alpha^n - \beta^n \\ \alpha^n - \beta^n + \alpha^{n - 1} - \beta^{n - 1} \end{pmatrix} \\ &= \frac1{\sqrt{5}} \begin{pmatrix} \alpha^{n + 1} + \alpha^n - (\beta^{n + 1} + \beta^n) \\ \alpha^n + \alpha^{n - 1} - (\beta^n + \beta^{n - 1}) \end{pmatrix}. \end{align}\]

ここで $\alpha^2 = \alpha + 1$より

\[\alpha^{n + 2} = \alpha^{n + 1} + \alpha^n, \quad \alpha^{n + 1} = \alpha^{n} + \alpha^{n - 1}\]

を得ます. 同様に

\[\beta^{n + 2} = \beta^{n + 1} + \beta^n, \quad \beta^{n + 1} = \beta^{n} + \beta^{n - 1}\]

を得ます.

よって

\(\begin{pmatrix} x_{n + 2} \\ x_{n + 1} \end{pmatrix} = \frac1{\sqrt{5}} \begin{pmatrix} \alpha^{n + 2} - \beta^{n + 2} \\ \alpha^{n + 1} - \beta^{n + 1} \end{pmatrix}\) を得ます.

以上によって

\[x_{n + 2} = \frac1{\sqrt{5}} (\alpha^{n + 2} - \beta^{n + 2}).\]

すなわち

\[x_n = \frac1{\sqrt{5}}(\alpha^n - \beta^n)\]

を得ます.

母関数による解法

関数$f(x) = u_1 + u_2x + u_3x^2 + \cdots$を考える. $xf(x) = u_1x + u_2x^2 + \cdots$を両辺に足すと

\[\begin{align} (1 + x)f(x) &= u_1 + u_3x + u_4x^2 + \cdots \\ &= u_1 + \frac{1}{x}(u_3x^2 + u_4x^3 + \cdots) \\ &= u_1 + \frac1{x}(f(x) - 1 - x) \\ &= \frac1{x}(f(x) - 1). \end{align}\]

また, これより

\[f(x) = \frac1{1 - x - x^2}\]

を得ます.

\[\begin{align} f(x) &= \frac1{(1 - \alpha x)(1 - \beta x)} \\ &= \frac1{\alpha x - \beta x}\left(\frac1{1 - \alpha x} - \frac1{1 - \beta x}\right) \\ &= \frac1{\sqrt{5}x}((1 + \alpha x + (\alpha x)^2 + \cdots) \\ & \quad - (1 + \beta x + (\beta x)^2 + \cdots )) \\ &= \frac1{\sqrt{5}}((\alpha - \beta) + (\alpha^2 - \beta^2)x + (\alpha^3 - \beta^3)x^2 + \cdots ). \end{align}\]

以上によって

\[u_n = \frac1{\sqrt{5}}(\alpha^n - \beta^n)\]

を得ます.