フィボナッチ数
フィボナッチ数列の最初の2項を 2, 1 に置き換えた数列の項をリュカ数という。
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, ... (OECS A000032)
この数列の一般項は
L n = ( 1 + 5 2 ) n + ( 1 − 5 2 ) n = φ n + ( 1 − φ ) n = φ n + ( − φ ) − n {\displaystyle L_{n}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}=\phi ^{n}+(1-\phi )^{n}={\phi ^{n}+(-\phi )^{-n}}}
と表される。
フィボナッチ数列やリュカ数の列を一般化したものがリュカ数列であり、1878年にエドゥアール・リュカが体系的な研究を行い、1913年にロバート・ダニエル・カーマイケル(英語版)がその結果を整理、拡張した。これらの研究が現代のフィボナッチ数の理論の基礎となった。
特に直前の三項の和として各項が定まるトリボナッチ数列は、フィボナッチ数列に次いでよく調べられている。0-fil型でオフセットが0番目からのものは
T0 = T1 = 0, T2 = 1,
Tn+3 = Tn + Tn+1 + Tn+2 (n ≥ 0)
と表される。第0~21項の値は次の通りである:
0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, ... (OEIS A000073)
トリボナッチ数列の一般項は次で表される。
T n = α n ( α − β ) ( α − γ ) + β n ( β − γ ) ( β − α ) + γ n ( γ − α ) ( γ − β ) {\displaystyle T_{n}={\frac {\alpha ^{n}}{(\alpha -\beta )(\alpha -\gamma )}}+{\frac {\beta ^{n}}{(\beta -\gamma )(\beta -\alpha )}}+{\frac {\gamma ^{n}}{(\gamma -\alpha )(\gamma -\beta )}}}
ただし、α, β, γ は三次方程式 x − x − x − 1 = 0 の3解
ただし、 ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } は床関数である。
なお、後述の負数番への拡張を考慮した場合、n < 0 では逆に一般項の第1項の絶対値が0.5未満となるため、n < 0 における Fn の正確な整数値は以下の式で得られる。
F n = − ⌊ ( − φ ) − n 5 + 1 2 ⌋ = − ⌊ 1 5 ( 1 − 5 2 ) n + 1 2 ⌋ {\displaystyle F_{n}=-\left\lfloor {\frac {(-\phi )^{-n}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor =-\left\lfloor {\frac {1}{\sqrt {5}}}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{2}}\right\rfloor }
これらのことから、任意の整数 n における Fn の正確な整数値は以下の式で得られる。
F n = ( sgn  n ) ⌊ { ( sgn  n ) φ } | n | 5 + 1 2 ⌋ = ( sgn  n ) ⌊ 1 5 { 1 + ( sgn  n ) 5 2 } n + 1 2 ⌋ {\displaystyle F_{n}=(\operatorname {sgn} n)\left\lfloor {\frac {\{(\operatorname {sgn} n)\phi \}^{|n|}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor =(\operatorname {sgn} n)\left\lfloor {\frac {1}{\sqrt {5}}}\left\{{\frac {1+(\operatorname {sgn} n){\sqrt {5}}}{2}}\right\}^{n}+{\frac {1}{2}}\right\rfloor }
ただし、sgn x は符号関数である。
また、フィボナッチ数列の漸化式は次のように行列表現できる:
( F n + 2 F n + 1 ) = ( 1 1 1 0 ) ( F n + 1 F n ) {\displaystyle {F_{n+2} \choose F_{n+1}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}{F_{n+1} \choose F_{n}}}
∴ ( F n + 1 F n F n F n − 1 ) = ( 1 1 1 0 ) n {\displaystyle \therefore {\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}}
母関数は
g ( x ) = ∑ n = 0 ∞ F n x n = x 1 − x − x 2 {\displaystyle g(x)=\textstyle \sum \limits _{n=0}^{\infty }F_{n}x^{n}={\dfrac {x}{1-x-x^{2}}}}
である。