フィボナッチ数列と2項係数
フィボナッチ数列と2項係数
フィボナッチ数列は2項係数の和を使って次のように表される。
\[ F_{n+1}=\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }C\left(n-k,k\right),n\in\mathbb{N}_{0}\cup\left\{ -1\right\} \]
フィボナッチ数列は2項係数の和を使って次のように表される。
\[ F_{n+1}=\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }C\left(n-k,k\right),n\in\mathbb{N}_{0}\cup\left\{ -1\right\} \]
-
\(\left\lfloor x\right\rfloor \)は床関数(1)
\begin{align*} F_{3} & =\sum_{k=0}^{\left\lfloor \frac{2}{2}\right\rfloor }C\left(2-k,k\right)\\ & =\sum_{k=0}^{1}C\left(2-k,k\right)\\ & =C\left(2,0\right)+C\left(1,1\right)\\ & =1+1\\ & =2 \end{align*}(2)
\begin{align*} F_{4} & =\sum_{k=0}^{\left\lfloor \frac{3}{2}\right\rfloor }C\left(3-k,k\right)\\ & =\sum_{k=0}^{1}C\left(3-k,k\right)\\ & =C\left(3,0\right)+C\left(2,1\right)\\ & =1+2\\ & =3 \end{align*}(0)
\begin{align*} \sum_{k=0}^{\infty}F_{k}x^{k} & =x\frac{1}{1-x-x^{2}}\\ & =x\sum_{k=0}^{\infty}\sum_{j=0}^{\infty}C\left(k,j\right)x^{k+j}\cmt{\because x+xy<1\rightarrow\sum_{j=0}^{\infty}\sum_{k=0}^{\infty}C\left(j,k\right)x^{j}y^{k}=\left(1-x-xy\right)^{-1}}\\ & =x\sum_{k=0}^{\infty}\sum_{j=0}^{\infty}C\left(k-j,j\right)x^{k}\\ & =x\sum_{k=0}^{\infty}\sum_{j=0}^{k}C\left(k-j,j\right)x^{k}\\ & =x\sum_{k=0}^{\infty}\sum_{j=0}^{\left\lfloor \frac{k}{2}\right\rfloor }C\left(k-j,j\right)x^{k}\\ & =\sum_{k=1}^{\infty}\sum_{j=0}^{\left\lfloor \frac{k}{2}\right\rfloor }C(k-j-1,j)x^{k} \end{align*} これより、\[ F_{k+1}=\sum_{j=0}^{\left\lfloor \frac{k}{2}\right\rfloor }C(k-j,j) \] となり、\(k=0,-1\)でも成り立つので題意は成り立つ。
(0)-2
\(n\)段の階段を1段または2段ずつ登るとき、\(F_{n+1}\)通りの登り方がある。これを違う方法で考える。2段を\(k\)回昇るとき、合計で\(n-2k+k=n-k\)回登らなくてはいけなく、その場合の数は\(C(n-k,k)\)となる。\(k\)の範囲は\(0\)から\(\left\lfloor \frac{n}{2}\right\rfloor \)なので\(\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }C(n-k,k)\)となる。
(0)-3
○と×を×が連続しないように\(n-1\)個並べる方法は\(F_{n+1}\)通りある。これを違う方法で考える。×の個数を\(k\)とすると×が連続しないように間に○を\(k-1\)個入れる必要があるので、\(C\left(n-\left(k-1\right),k\right)\)通りある。\(n-1-k-\left(k-1\right)\geq0\)でないといけないので\(k\)の範囲は0から\(\left\lfloor \frac{n}{2}\right\rfloor \)となり、\(\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }C\left(\left(n-1\right)-\left(k-1\right),k\right)=\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }C\left(n-k,k\right)\)通りになる。ページ情報
タイトル | フィボナッチ数列と2項係数 |
URL | https://www.nomuramath.com/kq2vle0d/ |
SNSボタン |
フィボナッチ数の負整数での値
\[
F_{-n}=\left(-1\right)^{n+1}F_{n}
\]
フィボナッチ数列の一般項(ビネの公式)
\[
F_{n}=\frac{1}{\sqrt{5}}\left\{ \left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right\}
\]
フィボナッチ数列の定義
\[
F_{n+2}=F_{n+1}+F_{n}
\]
フィボナッチ数列の行列表示
\[
\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}
\]