いろいろな方法でフィボナッチ数の一般項を表現する

フィボナッチ数列($F_n$) は、次の漸化式で定義される数列です。

初項を$F_0$として初めの方を書き下すとこんなかんじになります。

いろいろな方法でフィボナッチ数の一般項を表現する

フィボナッチ数の一般項を表現する式としてはいろいろなものが知られています。
ここでは有名なものから私が個人的に見つけたものまでいろいろ紹介したいと思います。

よく知られた表現

　　　　$F_n=\frac{1}{\sqrt{5}}\{{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\}$

ビネ (Binet) の公式と呼ばれています。同じことですが黄金比 $\phi =\frac{1+\sqrt{5}}{2}$ を使うと次のようにシンプルにできます。

　　　　$F_n=\frac{{\phi }^n-(-\phi {)}^{-n}}{\sqrt{5}}$

行列を使った表現

行列を使った表現も面白いです。
　　　　$\left(\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right)={\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n$

四捨五入を使った表現

四捨五入を使って表すこともできます。
　　　$F_n={\phi }^n$ を $\sqrt{5}$で割ってから四捨五入した数

もうちょっと数式らしくしてみましょう。
四捨五入する関数を $\lfloor x\rceil$ とします。床関数(その数を超えない最大の整数を返す関数。例えば$\lfloor 3.14\rfloor =3$)を使うと
　　　$\lfloor x\rceil =\lfloor x+\frac{1}{2}\rfloor$
となります。これを使うと、次のように表現することができます。
　　　$F_n=\lfloor \frac{{\phi }^n}{\sqrt{5}}\rceil$

二項係数を使った表現

　二項係数は${}_n{C}_k$の形で表現されることも多いですが、ここでは$(\genfrac{}{}{0ex}{}{n}{k})$ と表現します。すなわち
　　　　$(\genfrac{}{}{0ex}{}{n}{k})={}_n{C}_k=\frac{n!}{k!(n-k)!}$

これを使うと、次のような表現もできます。
　　　　${\displaystyle F_n=\frac{1}{2^{n-1}}\sum _{k=0}^{\lfloor \frac{n-1}{2}\rfloor }(\genfrac{}{}{0ex}{}{n}{2k+1})5^k}$

この式はカタランの公式と呼ばれています。

そのほか色々な表現

そのほか色々な表現を集めました。中には私が個人的に発見したものも含めています(既知かもしれませんが)。見た目は違いますが全部同じ数列になるのは面白いですね!
なお、$\phi =\frac{1+\sqrt{5}}{2},\overline{\phi }=\frac{1-\sqrt{5}}{2}$ とします。また、1の原始n乗根を${\zeta }_n(=e^{\frac{2i\pi }{n}})$と表します。

　　　　${\displaystyle F_n=\sum _{k=0}^{\lfloor \frac{n-1}{2}\rfloor }(\genfrac{}{}{0ex}{}{n-k-1}{k})}$
　　　　${\displaystyle F_n=\sum _{k=1}^n{\phi }^{n-k}{\overline{\phi }}^{k-1}}$
　　　　${\displaystyle F_n=\sum _{k=1}^n(-1{)}^{n-k}{(-\phi )}^{1+n-2k}}$
　　　　${\displaystyle F_n={(-\phi )}^{1-n}\sum _{k=0}^{n-1}{(-{\phi }^2)}^k}$
　　　　${\displaystyle F_n=\sum _{k=0}^{n-1}{e}^{(n-1-2k)\log \phi +ik\pi }}$
　　　　${\displaystyle F_n=\sum _{k=0}^{\mathrm{\infty }}(e^{(n-1-2k)\log \phi +ik\pi }-e^{(-n-1-2k)\log \phi +i(n+k)\pi })}$
　　　　${\displaystyle F_n={(-\phi )}^{1-n}\prod _{k=1}^{n-1}(-{\phi }^2-{\zeta }_n^k)}$
　　　　${\displaystyle F_n=\prod _{k=1}^{n-1}(\phi +\frac{{\zeta }_n^k}{\phi })}$
　　　　${\displaystyle F_n=\prod _{k=1}^{\lfloor \frac{n-1}{2}\rfloor }(1+4{\cos }^2\frac{k\pi }{n})}$
　　　　${\displaystyle F_n=\prod _{k=1}^{\lfloor \frac{n-1}{2}\rfloor }(3+2\cos \frac{2k\pi }{n})}$
　　　　${\displaystyle F_n=2^{n-1}\sum _{k=1}^n\frac{{\cos }^{k-1}\frac{3\pi }{5}}{{\cos }^{k-n}\frac{\pi }{5}}}$
　　　　${\displaystyle F_n=2^{n-1}\sum _{k=1}^{\mathrm{\infty }}(\frac{{\cos }^{k-1}\frac{3\pi }{5}}{{\cos }^{k-n}\frac{\pi }{5}}-\frac{{\sin }^{n+k-1}\frac{11\pi }{10}}{{\sin }^k\frac{3\pi }{10}})}$
　　　　${\displaystyle F_n=\frac{{\overline{\phi }}^n}{\phi -\overline{\phi }}\prod _{d|n}{C}_d(-{\phi }^2)}$

　　　　${\displaystyle F_n=1+\sum _{k=0}^{\lfloor \frac{n-3}{3}\rfloor }(-1{)}^k(\genfrac{}{}{0ex}{}{n-2k-3}{k})2^{n-3k-3}(n\ge 1)}$
　　　　${\displaystyle F_n=1+2^{n-3}\sum _{k=0}^{\lfloor \frac{n-3}{3}\rfloor }\frac{(1{)}_{n-3-2k}}{(1{)}_{n-3-3k}\cdot k!}{(-\frac{1}{2})}^{3k}(n\ge 1)}$