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

例題. 漸化式 $a_{n+2} = a_{n+1} + a_n$ から数列 $\{ 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\}$$ を得ることができる。

公式. フィボナッチ数列 $\{F_n\}$ について $F_1 + \ldots + F_n = F_{n+2} -1$ が成り立つ.

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

$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$ が成り立つ.

公式. フィボナッチ数列 $\{F_n\}$ について $F_1 + F_3 + \ldots + F_{2n-1} = F_{2n} $ が成り立つ.

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

$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} $ が成り立つ.

公式. フィボナッチ数列 $\{F_n\}$ について $F_2 + F_4 + \ldots + F_{2n} = F_{2n+1}-1$ が成り立つ.

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

$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 $ が成り立つ.

公式. フィボナッチ数列 $\{F_n\}$ について $F_1^2 + \ldots + F_n^2 = F_nF_{n+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}$ が成り立つ.

Pythonコード１. $n$ 番目のフィボナッチ数を出力する

n = int(input("何番目のフィボナッチ数を出力しますか？: "))
fib = [1, 1]

for i in range(2, n):
    fib.append(fib[i - 1] + fib[i - 2])

print(f"{n} 番目のフィボナッチ数は {fib[n-1]} です。")

Pythonコード２. $n$ 番目までのフィボナッチ数を出力する

n = int(input("何番目までのフィボナッチ数を出力しますか？: "))
fib = [1, 1]

for i in range(2, n):
    fib.append(fib[i - 1] + fib[i - 2])

print(fib)