Fibonacci数の総和 ~項をmoduloで分けてみよう~

Fibonacci数の総和

以下, 数列 ${F_{n}}_{n = 1}^{\infty}$ をFibonacci数列とする.
Fibonacci数列の総和は, 具体的に次のように求められる.

Fibonacci数の総和

$\begin{array}{r} \sum_{i = 1}^{n} F_{i} = F_{n + 2} - 1 \end{array}$

$\begin{aligned} F_{n + 2} - F_{n + 1} & = F_{n} \\ F_{n + 1} - F_{n} & = F_{n - 1} \\ F_{n} - F_{n - 1} & = F_{n - 2} \\ ⋮ \\ F_{3} - F_{2} & = F_{1} \end{aligned}$
の辺々を足せばよい.

では,
$\begin{array}{r} \sum_{\begin{array}{c} 1 \leq i \leq n, \\ i \equiv 0 (\mod 2) \end{array}} F_{i}, \sum_{\begin{array}{c} 1 \leq i \leq n, \\ i \equiv 1 (\mod 2) \end{array}} F_{i}, \end{array}$
などはどうだろうか？実は, これらも具体的に求めることができる. さらに, $3$ や $4$ を法としても, 簡単に求められるのである.

mod 2の場合

$\begin{aligned} \sum_{i = 1}^{n} F_{2 i} & = F_{2 n + 1} - 1, \\ \sum_{i = 1}^{n} F_{2 i - 1} & = F_{2 n} . \end{aligned}$

$α = \sum_{i = 1}^{n} F_{2 i}, β = \sum_{i = 1}^{n} F_{2 i - 1}$ とおくと,
$\begin{aligned} α - β & = (F_{2} - F_{1}) + (F_{4} - F_{3}) + (F_{6} - F_{5}) + \dots + (F_{2 n} - F_{2 n - 1}) \\ = 0 + F_{2} + F_{4} + \dots + F_{2 n - 2} \\ = α - F_{2 n} \end{aligned}$
より, $β = F_{2 n}$ . また定理 $1$ から
$\begin{array}{r} α + β = F_{2 n + 2} - 1 \end{array}$
が成り立つゆえ
$\begin{array}{r} α = F_{2 n + 2} - F_{2 n} - 1 = F_{2 n + 1} - 1. \end{array}$

これから, 次が得られる.

法

2

の総和

$\begin{aligned} \sum_{\begin{array}{c} 1 \leq i \leq n, \\ i \equiv 0 (\mod 2) \end{array}} F_{i} & = F_{2 ⌊ \frac{n}{2} ⌋ + 1} - 1, \\ \sum_{\begin{array}{c} 1 \leq i \leq n, \\ i \equiv 1 (\mod 2) \end{array}} F_{i} & = F_{2 ⌊ \frac{n + 1}{2} ⌋} . \end{aligned}$

mod 3の場合

証明の発想はmod2の場合と同じである.

$\begin{aligned} \sum_{i = 1}^{n} F_{3 i} & = \frac{F_{3 n + 2} - 1}{2}, \\ \sum_{i = 1}^{n} F_{3 i - 1} & = \frac{F_{3 n + 1} - 1}{2}, \\ \sum_{i = 1}^{n} F_{3 i - 2} & = \frac{F_{3 n}}{2} . \end{aligned}$

$α = \sum_{i = 1}^{n} F_{3 i}, β = \sum_{i = 1}^{n} F_{3 i - 1}, γ = \sum_{i = 1}^{n} F_{3 i - 2}$ とおくと,
$\begin{aligned} α + β + γ = F_{3 n + 2} - 1, \\ α - β = (F_{3} - F_{2}) + (F_{6} - F_{5}) + \dots + (F_{3 n} - F_{3 n - 1}) = F_{1} + F_{4} + \dots + F_{3 n - 2} = γ, \\ β - γ = (F_{2} - F_{1}) + (F_{5} - F_{3}) + \dots + (F_{3 n - 1} - F_{3 n - 2}) = F_{2} + F_{5} + \dots + F_{3 n - 3} = α - F_{3 n} \end{aligned}$
が成り立つので, 連立方程式とみて解けば
$\begin{array}{r} α = \frac{F_{3 n + 2} - 1}{2}, β = \frac{F_{3 n + 1} - 1}{2}, γ = \frac{F_{3 n}}{2} \end{array}$
が得られる.

上から, 次が成り立つ.

法

3

の総和

$\begin{array}{r} \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \equiv 0 (\mod 3) \end{array}} F_{i} = \frac{F_{3 ⌊ \frac{n}{3} ⌋ + 2} - 1}{2}, \\ \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \equiv 1 (\mod 3) \end{array}} F_{i} = \frac{F_{3 ⌊ \frac{n}{3} ⌋ + 1} - 1}{2}, \\ \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \equiv 2 (\mod 3) \end{array}} F_{i} = \frac{F_{3 ⌊ \frac{n}{3} ⌋}}{2}, \end{array}$

mod 4の場合

法が4の場合は, うまく対応しておりとてもきれいである. 変数が多くなるだけで証明方法は同じなので省略する.

$\begin{aligned} \sum_{i = 1}^{n} F_{4 i} & = \frac{F_{4 n + 4} - F_{4 n}}{5} - \frac{3}{5}, \\ \sum_{i = 1}^{n} F_{4 i - 1} & = \frac{F_{4 n + 3} - F_{4 n - 1}}{5} - \frac{1}{5}, \\ \sum_{i = 1}^{n} F_{4 n - 2} & = \frac{F_{4 n + 2} - F_{4 n - 2}}{5} - \frac{2}{5}, \\ \sum_{i = 1}^{n} F_{4 n - 3} & = \frac{F_{4 n + 1} - F_{4 n - 3}}{5} + \frac{1}{5} . \end{aligned}$