1

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

35
0
$$\newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{C}[0]{\mathbb{C}} \newcommand{ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{N}[0]{\mathbb{N}} \newcommand{pas}[1]{\left(#1\right)} \newcommand{Pas}[1]{\left\{#1\right\}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

Fibonacci数の総和

以下, 数列$\Pas{F_n}_{n=1}^\infty$をFibonacci数列とする.
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}

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

$2$の総和

\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}
が得られる.

上から, 次が成り立つ.

$3$の総和

\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$に関する場合分けが必要なのではとにらんでいる. また進捗が生まれたらここに追記したい.

投稿日:202112

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

Sep
Sep
26
4078
解析数論が好きです! ねこに包まれたい。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中