主題
Search

斐波那契 n 步數


一個 n-步斐波那契數列 {F_k^((n))}_(k=1)^infty 定義為當 F_k^((n))=0k<=0F_1^((n))=F_2^((n))=1,以及根據 線性遞推方程 的其他項

 F_k^((n))=sum_(i=1)^nF_(k-i)^((n))
(1)

對於 k>2

使用 布朗判據,可以證明 n-步斐波那契數是完備的;也就是說,每個正數都可以寫成不同的 n-步斐波那契數之和。正如 Fraenkel (1985) 所討論的,每個正數都有一個唯一的 Zeckendorf 型別展開式,作為不同的 n-步斐波那契數之和,並且該和不包含 n 個連續的 n-步斐波那契數。Zeckendorf 型別展開式可以使用 貪婪演算法 計算。

下表總結了前幾個 n-步斐波那契數列。

nOEIS名稱數列
1退化1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, ...
2A000045斐波那契數1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
3A000073三波那契數1, 1, 2, 4, 7, 13, 24, 44, 81, ...
4A000078四波那契數1, 1, 2, 4, 8, 15, 29, 56, 108, ...
5A001591五波那契數1, 1, 2, 4, 8, 16, 31, 61, 120, ...
6A001592六波那契數1, 1, 2, 4, 8, 16, 32, 63, 125, ...
7A066178七波那契數1, 1, 2, 4, 8, 16, 32, 64, 127, ...

n拋硬幣 中不出現 k 次連續反面的機率由 F_(n+2)^((k))/2^n 給出,其中 F_l^((k)) 是斐波那契 k-步數。

極限 lim_(k->infty)F_k^((n))/F_(k-1)^((n)) 稱為 n-anacci 常數,透過解以下方程給出

 x^n(2-x)=1,
(2)

或等價地

 P(x)=x^n-x^(n-1)-x^(n-2)-...-x-1=0,
(3)

對於 x,然後取 x>1。對於 偶數 n,恰好有兩個實根,一個大於 1,一個小於 1,對於 奇數 n恰好有一個 實根,它總是 >=1

kn-anacci 數 F_k^((n)) 的精確公式可以由下式給出

 F_k^((n))=nint((r^(k-1)(r-1))/((n+1)r-2n)),
(4)

其中 r=(x^(-n)+x-2)_([5+(-1)^n]/2) 是一個 多項式根

另一個公式以 n 個根 x_i of P(x) 表示。這具有一般形式

 F_k^((n))=sum_(i=1)^n(x_i^k)/(Q_n(x_i)),
(5)

其中 Q_n(x)x_i 的多項式,前幾個是

Q_2(x)=2x-1
(6)
Q_3(x)=-x^2+4x-1
(7)
Q_4(x)=-x^3+6x-1
(8)
Q_5(x)=-x^4+x^2+8x-1.
(9)

當排列成對應於最小系數的 數字三角形 時,這給出了

 -1,2 
-1,4,-1 
-1,6,0,-1 
-1,8,1,0,-1 
-1,10,2,1,0,-1 
-1,12,3,2,1,0,-1
(10)

(OEIS A118745) 對於 n=2 到 7,對於更高的 n,模式很容易辨別。

如果 n=2,方程 (9) 簡化為

 x^2(2-x)=1
(11)
 x^3-2x^2+1=(x-1)(x^2-x-1)=0,
(12)

給出解

 x=1,1/2(1+/-sqrt(5)).
(13)

因此,比率為

 x=1/2(1+sqrt(5))=phi=1.618...,
(14)

正如預期的那樣,這是黃金比例

FibonacciNStepLimits

對於 n=1, 2, ... 的解析解由以下給出

x_1=1
(15)
x_2=1/2(1+sqrt(5))
(16)
x_3=1/3[1+(19-3sqrt(33))^(1/3)+(19+3sqrt(33))^(1/3)]
(17)
=(x^3-x^2-x-1)_1
(18)
x_4=(x^4-x^3-x^2-x-1)_2
(19)

數值上為 1, 1.61803 (OEIS A001622), 1.83929 (OEIS A058265; 三波那契常數), 1.92756 (OEIS A086088; 四波那契常數), 1.96595, ..., 當 n->infty 時接近 2。


另請參閱

斐波那契數, 七波那契數, 六波那契數, Lucas n 步數, 五波那契數, 四波那契常數, 四波那契數, 三波那契常數, 三波那契數, Zeckendorf 表示

本條目部分內容由 Tony Noe 貢獻

本條目部分內容由 Tito Piezas III 貢獻

使用 探索

參考文獻

Fraenkel, A. S. "Systems of Numeration." Amer. Math. Monthly 92, 105-114, 1985.Noe, T. D. and Post, J. V. "Primes in Fibonacci n-step and Lucas n-Step Sequences." J. Integer Seq. 8, Article 05.4.4, 2005. http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html.Sloane, N. J. A. 數列 A000045/M0692, A000073/M1074, A000078/M1108, A001591, A001622, A046698, A058265, A086088, 和 A118745 在 “整數數列線上百科全書” 中。

在 中引用

斐波那契 n 步數

請引用為

Noe, Tony; Piezas, Tito III; 和 Weisstein, Eric W. "斐波那契 n 步數。" 來自 Web 資源。 https://mathworld.tw/Fibonaccin-StepNumber.html

主題分類