拡張フィボナッチ数列（k-ボナッチ数列）の任意の項までの和を高速に求める手法の考案【前編】

はじめに

　掲題の内容については【前編】と【後編】の2つの記事で構成されています。本記事は【前編】となっており、主に式の導出についてを扱っています。

　また[【後編】の記事][link_1]では、C++で実装したプログラムを紹介しています。併せてご覧ください。

（これらの記事の内容は「[拡張フィボナッチ数列の任意の項までの和を高速に求める方法の考案][link_2]」[^1]を加筆、修正したものです。）

概要

　フィボナッチ数列とは「直前の2つの項を足して次の項を作る数列」であり、次のような漸化式で定義されます。

\begin{cases}
\begin{align}
F_0 &= 0\\
F_1 &= 1\\
F_{n} &= F_{n-1}+F_{n-2}
\end{align}
\end{cases}

　ここでフィボナッチ数列の $0$ 項目から $n$ 項目までの和について、以下の式が成り立つことが知られています。（この式の導出の仕方については[こちらの他の方の記事][link_3]をご参照ください[^2]。）

\sum^n_{i=0}F_i=F_{n+2}-F_1=F_{n+2}-1

　この公式では数列の $n+1$ 個の項の和が僅か $1$ 個の項の計算から導き出せることがわかります。フィボナッチ数列の任意の項の数は黄金比のもとになる一般項[^3]から求められるので、この和も高速に計算できます。

　今回私はこの公式のアイデアを応用し、トリボナッチ数列やテトラボナッチ数列などでも同じような和を導き出せる方程式を導出しました。この方程式では $n+1$ 個の項の和が僅か $2k-2$ 個の項の計算から導き出せます。

k-ボナッチ数列の定義

　拡張フィボナッチ数列は、フィボナッチ数列を「直前の $k$ 個の項を足して次の項を作る数列」に拡張したものです。以降これを「$k$-ボナッチ数列[^4]」と呼ぶことにします。

　このとき $k$-ボナッチ数列は次の漸化式で定義できます。

\begin{cases}
\begin{align}
F_0 &= F_1=\cdots=F_{k-3}=F_{k-2}=0\\
F_{k-1} &= 1\\
F_{n} &= F_{n-1}+F_{n-2}+\cdots+F_{n-(k-1)}+F_{n-k}=\sum^{n-1}_{i=n-k}F_i
\end{align}
\end{cases}

k-ボナッチ数列の任意の項までの和の公式

　$k$-ボナッチ数列の $0$ 項目から $n$ 項目までの和は以下の式で表すことができます。

\begin{align}
\sum^n_{i=0}F_i=\frac{F_{n+k}-F_{k-1}- \begin{align} \sum^{k-3}_{j=-1}\Bigl\{ (j+1)(F_{n+k-2-j}-F_{k-3-j})\Bigr\} \end{align} }{k-1}\\\\
\text(ただし, k\geq2)
\end{align}

式の導出および証明

　方程式の証明は数学的帰納法を用いて示しました。（導出部分も含めているため、蛇足的な部分もあります。）

$k$-ボナッチ数列の和の方程式について, 数学的帰納法を用いて証明する.

ⅰ）$k=2$ のとき
　$F_{n}=F_{n-1}+F_{n-2} \Leftrightarrow F_{n-2}=F_{n}-F_{n-1}$より,

\require{cancel}\begin{array}{rrcccc}
&F_{n}&=&{F_{n+2}}&-&\cancel{F_{n+1}}\\
&F_{n-1}&=&\cancel{F_{n+1}}&-&\cancel{F_{n}}\\
&F_{n-2}&=&\cancel{F_{n}}&-&\cancel{F_{n-1}}\\
&&\vdots\\
&F_1&=&\cancel{F_3}&-&\cancel{F_2}\\
+)&F_0&=&\cancel{F_2}&-&{F_1}\\
\hline
&\sum^n_{i=0}F_i&=&F_{n+2}&-&F_1
\end{array}

ⅱ）$k=3$ のとき
　$F_n=F_{n-1}+F_{n-2}+F_{n-3} \Leftrightarrow F_{n-3}=F_n-F_{n-1}-F_{n-2}$より,

\require{cancel}\begin{array}{rrccccl}
&F_{n}&=&F_{n+3}&-&\cancel{F_{n+2}}&-F_{n+1}\\
&F_{n-1}&=&\cancel{F_{n+2}}&-&\cancel{F_{n+1}}&-F_{n}\\
&F_{n-2}&=&\cancel{F_{n+1}}&-&\cancel{F_{n}}&-F_{n-1}\\
&&\vdots\\
&F_1&=&\cancel{F_4}&-&\cancel{F_3}&-F_2\\
+)&F_0&=&\cancel{F_3}&-&F_2&-F_1\\
\hline
&\sum^n_{i=0}F_i&=&F_{n+3}&-&F_2&-\sum^{n+1}_{j=1}F_j\\
\Leftrightarrow &2\sum^n_{i=0}F_i&=&F_{n+2}&-&F_2&-(F_{n+1}-F_0)
\end{array}

ⅲ）$k=4$ のとき
　同様に,

\require{cancel}\begin{array}{rrccccl}
&F_{n}&=&F_{n+4}&-&\cancel{F_{n+3}}&-F_{n+2}-F_{n+1}\\
&F_{n-1}&=&\cancel{F_{n+3}}&-&\cancel{F_{n+2}}&-F_{n+1}-F_{n}\\
&F_{n-2}&=&\cancel{F_{n+2}}&-&\cancel{F_{n+1}}&-F_{n}-F_{n-1}\\
&&\vdots\\
&F_1&=&\cancel{F_5}&-&\cancel{F_4}&-F_3-F_2\\
+)&F_0&=&\cancel{F_4}&-&F_3&-F_2-F_1\\
\hline
&\sum^n_{i=0}F_i&=&F_{n+4}&-&F_3&\underbrace{-\sum^{n+2}_{j=2}F_j-\sum^{n+1}_{l=1}F_l}_{2個}\\
\Leftrightarrow &3\sum^n_{i=0}F_i&=&F_{n+4}&-&F_3&-(F_{n+2}+2F_{n+1}-F_1-2F_0)
\end{array}

ⅳ）$k=5$ のとき
　同様に,

\require{cancel}\begin{array}{rrccccl}
&F_{n}&=&F_{n+5}&-&\cancel{F_{n+4}}&-F_{n+3}-F_{n+2}-F_{n+1}\\
&F_{n-1}&=&\cancel{F_{n+4}}&-&\cancel{F_{n+3}}&-F_{n+2}-F_{n+1}-F_{n}\\
&F_{n-2}&=&\cancel{F_{n+3}}&-&\cancel{F_{n+2}}&-F_{n+1}-F_{n}-F_{n-1}\\
&&\vdots\\
&F_1&=&\cancel{F_6}&-&\cancel{F_5}&-F_4-F_3-F_2\\
+)&F_0&=&\cancel{F_5}&-&F_4&-F_3-F_2-F_1\\
\hline
&\sum^n_{i=0}F_i&=&F_{n+5}&-&F_4&\underbrace{-\sum^{n+3}_{j=3}F_j-\sum^{n+2}_{l=2}F_l-\sum^{n+1}_{r=1}F_r}_{3個}\\
\Leftrightarrow &4\sum^n_{i=0}F_i&=&F_{n+5}&-&F_4&-(F_{n+3}+2F_{n+2}+3F_{n+1}-F_2-2F_1-3F_0)\\
\Leftrightarrow &4\sum^n_{i=0}F_i&=&F_{n+5}&-&F_4&-\sum^{2}_{j=0}\Bigl\{(j+1)(F_{n+3-j}-F_{2-j})\Bigr\}
\end{array}

ⅴ）$k=A$ のとき
　以下の式（※）が成り立つと仮定する.

\begin{align}
(A-1)\sum^n_{i=0}F_i=F_{n+A}-F_{A-1}-\sum^{A-3}_{j=-1}\Bigl\{ (j+1)(F_{n+A-2-j}-F_{A-3-j})\Bigr\} \tag{※}
\end{align}

ⅵ）$k=A+1$ のとき

\begin{align}
F_n&=F_{n-1}+F_{n-2}+\cdots+F_{n-A}+F_{n-(A+1)}\\
\Leftrightarrow F_{n-(A+1)}&=F_n-F_{n-1}-F_{n-2}-\cdots-F_{n-A}
\end{align}

より,

\require{cancel}\begin{array}{rrccccl}
&F_{n}&=&F_{n+(A+1)}&-&\cancel{F_{n+A}}&-F_{n+(A-1)}-\cdots-F_{n+2}-F_{n+1}\\
&F_{n-1}&=&\cancel{F_{n+A}}&-&\cancel{F_{n+(A-1)}}&-F_{n+(A-2)}-\cdots-F_{n+1}-F_{n}\\
&F_{n-2}&=&\cancel{F_{n+(A-1)}}&-&\cancel{F_{n+(A-2)}}&-F_{n+(A-3)}-\cdots-F_{n-1}-F_{n-2}\\
&&\vdots\\
&F_1&=&\cancel{F_{A+2}}&-&\cancel{F_{A+1}}&-F_A-\cdots-F_3-F_2\\
+)&F_0&=&\cancel{F_{A+1}}&-&F_A&-F_{A-1}-\cdots-F_2-F_1\\
\hline
&\sum^n_{i=0}F_i&=&F_{n+(A+1)}&-&F_{A-1}&\underbrace{-\sum^{n+(A-1)}_{j=A-1}F_j-\sum^{n+(A-2)}_{l=A-2}F_l-\cdots-\sum^{n+1}_{r=1}F_r}_{A-1個}\\
\Leftrightarrow &A\sum^n_{i=0}F_i&=&F_{n+(A+1)}&-&F_{A-1}&-\sum^{A-2}_{j=0}\Bigl\{\sum^{n+(A-1)-j}_{l=n+1}F_l-\sum^{(A-2)-j}_{r=0}F_r\Bigr\}\\
\Leftrightarrow &A\sum^n_{i=0}F_i&=&F_{n+(A+1)}&-&F_{A-1}&-\sum^{A-2}_{j=0}\Bigl\{(j+1)(F_{n+(A-1)-j}-F_{(A-2)-j})\Bigr\}\\
\Leftrightarrow &\bigl\{(A+1)-1\bigr\}\sum^n_{i=0}F_i&=&F_{n+(A+1)}&-&F_{(A+1)-1}&-\sum^{(A+1)-3}_{j=-1}\Bigl\{(j+1)(F_{n+(A+1)-2-j}-F_{(A+1)-3-j})\Bigr\}
\end{array}

　これより式（※）は $k=A+1$ のときも成り立つ.

よって, 数学的帰納法より式（※）は成立する.

式の利点

　この方程式の主な特徴は「$n+1$ 個の項の和を僅か $2k-2$ 個の項による計算で表現できている」という点です。$n+1>2k-2$ ⇔ $n>2k-3$ の場合、つまり $n$ の値が大きいときに効果的です。従来法と比べるとかなり高速に計算できると思います。

プログラムへの実装（C++）

　[【後編】][link_1]では、このアイデアを用いた $k$-ボナッチ数列に関するコード（C++）を紹介しています。正確かつ高速化するために細かい点も工夫したので是非ご覧ください。

[^1]: today Diary「[拡張フィボナッチ数列の任意の項までの和を高速に求める方法の考案][link_2]」（はてなブログ）.
[^2]: A4の宇宙「[フィボナッチ数列の和][link_3]」（はてなブログ）.
[^3]: @nigohirokiさんの記事「[フィボナッチ数列の一般項を求める方法][link_5]」を参照.
[^4]: 「$k$-ボナッチ数列」の名称は, @magolorsさんの記事「[拡張フィボナッチ数列(k-ボナッチ数列 : 直前のk項の和)の一般項を線形代数とPythonで求める][link_4]」から拝借させていただきました.

[link_1]:https://qiita.com/today2049/items/e9b18851e76d324562c0
"拡張フィボナッチ数列（k-ボナッチ数列）の任意の項までの和を高速に求める手法の考案【後編】"
[link_2]: https://today-f.hatenablog.jp/entry/20200826/1598430734
"拡張フィボナッチ数列の任意の項までの和を高速に求める方法の考案"
[link_3]: https://a4.hateblo.jp/entry/2018/10/28/142243
"フィナッチ数列の和"
[link_4]: https://qiita.com/magolors/items/359b1da94830a71fec08
"拡張フィボナッチ数列(k-ボナッチ数列 : 直前のk項の和)の一般項を線形代数とPythonで求める"
[link_5]: https://qiita.com/nigohiroki/items/732dba563425904afa6e
"フィボナッチ数列の一般項を求める方法"
[link_test]: https://today-f.hatenablog.jp/