主题
Search

斐波那契 n 步数

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

一个 n-步斐波那契数列 {F_k^((n))}_(k=1)^infty 定义为当 F_k^((n))=0 时 k<=0，F_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。

第 k 个 n-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 贡献

使用 Wolfram|Alpha 探索

参考文献

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 在 “整数数列在线百科全书” 中。

在 Wolfram|Alpha 中引用

斐波那契 n 步数

请引用为

Noe, Tony; Piezas, Tito III; 和 Weisstein, Eric W. "斐波那契 n 步数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Fibonaccin-StepNumber.html

主题分类