Fibonacci数の総和 ~項をmoduloで分けてみよう~
Fibonacci数の総和
以下, 数列$\Pas{F_n}_{n=1}^\infty$をFibonacci数列とする.
Fibonacci数列の総和は, 具体的に次のように求められる.
\begin{align} \sum_{i=1}^n F_i=F_{n+2}-1 \end{align}
\begin{align}
F_{n+2}-F_{n+1}&=F_{n}\\
F_{n+1}-F_{n}&=F_{n-1}\\
F_{n}-F_{n-1}&=F_{n-2}\\
&\;\;\vdots\\
F_3-F_2&=F_1
\end{align}
の辺々を足せばよい.
では,
\begin{align}
\sum_{\substack{1\leq i\leq n,\\i\equiv0\pmod2}}F_i, \quad\sum_{\substack{1\leq i\leq n,\\i\equiv1\pmod2}}F_i,
\end{align}
などはどうだろうか？実は, これらも具体的に求めることができる. さらに, $3$や$4$を法としても, 簡単に求められるのである.
mod 2の場合
\begin{align} \sum_{i=1}^nF_{2i}&=F_{2n+1}-1, \\ \sum_{i=1}^nF_{2i-1}&=F_{2n}. \end{align}
$\alpha=\sum_{i=1}^nF_{2i},\beta=\sum_{i=1}^nF_{2i-1}$とおくと,
\begin{align}
\alpha-\beta
&=\pas{F_2-F_1}+\pas{F_4-F_3}+\pas{F_6-F_5}+\cdots+\pas{F_{2n}-F_{2n-1}}\\
&=0+F_2+F_4+\cdots+F_{2n-2}\\
&=\alpha-F_{2n}
\end{align}
より, $\beta=F_{2n}$. また定理$1$から
\begin{align}
\alpha+\beta=F_{2n+2}-1
\end{align}
が成り立つゆえ
\begin{align}
\alpha=F_{2n+2}-F_{2n}-1=F_{2n+1}-1.
\end{align}
これから, 次が得られる.
\begin{align} \sum_{\substack{1\leq i\leq n,\\i\equiv0\pmod2}}F_i&=F_{2\floor{\frac{n}{2}}+1}-1,\\ \quad\sum_{\substack{1\leq i\leq n,\\i\equiv1\pmod2}}F_i&=F_{2\floor{\frac{n+1}{2}}}. \end{align}
mod 3の場合
証明の発想はmod2の場合と同じである.
\begin{align} \sum_{i=1}^nF_{3i}&=\frac{F_{3n+2}-1}{2},\\ \sum_{i=1}^nF_{3i-1}&=\frac{F_{3n+1}-1}{2},\\ \sum_{i=1}^nF_{3i-2}&=\frac{F_{3n}}{2}. \end{align}
$\alpha=\sum_{i=1}^n F_{3i},\beta=\sum_{i=1}^n F_{3i-1},\gamma=\sum_{i=1}^nF_{3i-2}$とおくと,
\begin{align}
&\alpha+\beta+\gamma=F_{3n+2}-1,\\
&\alpha-\beta=\pas{F_3-F_2}+\pas{F_6-F_5}+\cdots+\pas{F_{3n}-F_{3n-1}}=F_1+F_4+\cdots+F_{3n-2}=\gamma,\\
&\beta-\gamma=\pas{F_2-F_1}+\pas{F_5-F_3}+\cdots+\pas{F_{3n-1}-F_{3n-2}}=F_2+F_5+\cdots+F_{3n-3}=\alpha-F_{3n}
\end{align}
が成り立つので, 連立方程式とみて解けば
\begin{align}
\alpha=\frac{F_{3n+2}-1}{2}, \beta=\frac{F_{3n+1}-1}{2}, \gamma=\frac{F_{3n}}{2}
\end{align}
が得られる.
上から, 次が成り立つ.
\begin{align} \sum_{\substack{1\leq i\leq n\\i\equiv0\pmod3}}F_i=\frac{F_{3\floor{\frac{n}{3}}+2}-1}{2},\\ \sum_{\substack{1\leq i\leq n\\i\equiv1\pmod3}}F_i=\frac{F_{3\floor{\frac{n}{3}}+1}-1}{2},\\ \sum_{\substack{1\leq i\leq n\\i\equiv2\pmod3}}F_i=\frac{F_{3\floor{\frac{n}{3}}}}{2},\\ \end{align}
mod 4の場合
法が4の場合は, うまく対応しておりとてもきれいである. 変数が多くなるだけで証明方法は同じなので省略する.
\begin{align} \sum_{i=1}^nF_{4i}&=\frac{F_{4n+4}-F_{4n}}{5}-\frac{3}{5},\\ \sum_{i=1}^nF_{4i-1}&=\frac{F_{4n+3}-F_{4n-1}}{5}-\frac{1}{5},\\ \sum_{i=1}^nF_{4n-2}&=\frac{F_{4n+2}-F_{4n-2}}{5}-\frac{2}{5},\\ \sum_{i=1}^nF_{4n-3}&=\frac{F_{4n+1}-F_{4n-3}}{5}+\frac{1}{5}. \end{align}
mod $k$の場合
同様に,$\sum_{i=1}^nF_{ki+r}$を求めたい. しかし, $k$が合成数の場合は導出できるのに対し, 素数の場合はなぜかうまくいかないので, $k$に関する場合分けが必要なのではとにらんでいる. また進捗が生まれたらここに追記したい.
