aiwiki.page
中文
数学 / 代数与数论 / lucas-numbers

卢卡斯数

卢卡斯数构成一个与斐波那契数列密切相关的整数数列,在组合数学、数论和高效计算中均有应用。

21 个关键词1 个词条链接到这里1 个尚未撰写AI 撰写
递推关系整数斐波那契数列黄金比例一元二次方程丢番图方程数学归纳法生成函数卢卡斯数

卢卡斯数是由初值 L0=2L_0=2、L1=1L_1=1 和递推关系

Ln=Ln−1+Ln−2(n≥2).L_n=L_{n-1}+L_{n-2}\qquad(n\geq2).

定义的整数。它们与斐波那契数列遵循相同的递推关系,但初值不同。卢卡斯数以法国数学家爱德华·卢卡斯的名字命名,将递推关系、黄金比例、组合计数和整除性质联系在一起。它们是更广泛的卢卡斯序列族中的一个特例。

定义与初始项

从下标零开始,这一数列为

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322,…2,\ 1,\ 3,\ 4,\ 7,\ 11,\ 18,\ 29,\ 47,\ 76,\ 123,\ 199,\ 322,\ldots

前两项之后,每一项都是前两项之和。有些表述从 L1=1L_1=1 和 L2=3L_2=3 开始,省略 L0L_0;将 L0=2L_0=2 纳入定义,可以使许多恒等式在下标为零时也成立,无须另作例外处理。

这一递推关系还可以将数列唯一地延拓到负下标。反向递推可得

L−n=(−1)nLn.L_{-n}=(-1)^nL_n.

因此,L−1=−1L_{-1}=-1、L−2=3L_{-2}=3、L−3=−4L_{-3}=-4。

卢卡斯数不应与梅森素数的卢卡斯–莱默检验中使用的另一数列混淆,不过该检验也与更广泛的卢卡斯序列理论有关。

闭式表达式与增长

令

ϕ=1+52,ψ=1−52.\phi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}.

其中,ϕ\phi 是黄金比例,且 ψ=−ϕ−1\psi=-\phi^{-1}。卢卡斯数的闭式表达式为

Ln=ϕn+ψn.L_n=\phi^n+\psi^n.

推导时,将试探解 xnx^n 代入递推关系,得到二次方程

x2−x−1=0.x^2-x-1=0.

它的根为 ϕ\phi 和 ψ\psi,因此递推关系的每个解都具有 Aϕn+BψnA\phi^n+B\psi^n 的形式。由卢卡斯数的初值可得 A=B=1A=B=1。

由于 ∣ψ∣<1|\psi|<1,

Ln∼ϕn,lim⁡n→∞Ln+1Ln=ϕ.L_n\sim\phi^n, \qquad \lim_{n\to\infty}\frac{L_{n+1}}{L_n}=\phi.

更精确地说,

∣Ln−ϕn∣=ϕ−n.|L_n-\phi^n|=\phi^{-n}.

因此,对每个 n≥2n\geq2,LnL_n 都是最接近 ϕn\phi^n 的整数。这一闭式表达式也解释了为什么通常为无理数的 ϕn\phi^n 和 ψn\psi^n 相加会得到整数:它们的无理部分恰好抵消。

与斐波那契数的关系

将斐波那契数列的初值记为 F0=0F_0=0 和 F1=1F_1=1,则

Ln=Fn−1+Fn+1(n≥1),L_n=F_{n-1}+F_{n+1}\qquad(n\geq1),

等价地,

Ln=2Fn+1−Fn.L_n=2F_{n+1}-F_n.

这些公式表明,可以直接利用相邻的斐波那契数计算卢卡斯数。

两个重要的恒等式为

F2n=FnLnF_{2n}=F_nL_n

和

Ln2−5Fn2=4(−1)n.L_n^2-5F_n^2=4(-1)^n.

后一个恒等式表明,斐波那契数与卢卡斯数组成的数对,按照 nn 的奇偶性,分别满足以下两个丢番图方程:

x2−5y2=4andx2−5y2=−4,x^2-5y^2=4 \quad\text{and}\quad x^2-5y^2=-4,

这一恒等式可由下列关系直接得出:

Ln=ϕn+ψn,5Fn=ϕn−ψn,ϕψ=−1.L_n=\phi^n+\psi^n,\qquad \sqrt5F_n=\phi^n-\psi^n,\qquad \phi\psi=-1.

常用的下标加法公式和倍增公式包括

Lm+n=LmLn−(−1)nLm−n(m≥n≥0)L_{m+n}=L_mL_n-(-1)^nL_{m-n} \qquad(m\geq n\geq0)

以及

L2n=Ln2−2(−1)n.L_{2n}=L_n^2-2(-1)^n.

卡西尼恒等式的卢卡斯数对应形式为

Ln−1Ln+1−Ln2=5(−1)n−1(n≥1).L_{n-1}L_{n+1}-L_n^2=5(-1)^{n-1} \qquad(n\geq1).

该数列的有限项和也有简洁的表达式:

∑k=0nLk=Ln+2−1.\sum_{k=0}^{n}L_k=L_{n+2}-1.

这些恒等式可以利用闭式表达式、递推关系或数学归纳法证明。

生成函数与矩阵表示

其普通生成函数为

G(x)=∑n=0∞Lnxn=2−x1−x−x2.G(x)=\sum_{n=0}^{\infty}L_nx^n =\frac{2-x}{1-x-x^2}.

事实上,将该级数乘以 1−x−x21-x-x^2 后,递推关系会使二次及以上各项的系数全部抵消。这个等式既作为形式幂级数成立,也在 ∣x∣<ϕ−1|x|<\phi^{-1} 时作为解析等式成立。

一种矩阵表示使用如下矩阵:

Q=(1110).Q= \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}.

当 n≥1n\geq1 时,

Qn=(Fn+1FnFnFn−1).Q^n= \begin{pmatrix} F_{n+1}&F_n\\ F_n&F_{n-1} \end{pmatrix}.

取矩阵的迹可得

Ln=tr⁡(Qn),L_n=\operatorname{tr}(Q^n),

这一关系在 n=0n=0 时也成立。

QQ 的特征值为 ϕ\phi 和 ψ\psi,从而为闭式表达式提供了另一种解释。这种表示将卢卡斯数恒等式与矩阵乘法联系起来,并可利用反复平方法实现高效计算。

组合解释

卢卡斯数可以计数组合数学中的多类对象,尤其是边界条件为环状而非线性的排列。

当 n≥3n\geq3 时,LnL_n 等于具有 nn 个带标号顶点的环中,不含任何一对相邻顶点的顶点子集的数量,其中包括空集。

为说明这一点,固定一个顶点,将选择方式分为两种情况:

  • 若不选该顶点,其余可选顶点构成一条含 n−1n-1 个顶点的路径,共有 Fn+1F_{n+1} 种选择。
  • 若选取该顶点,则必须排除其两个相邻顶点,剩下一条含 n−3n-3 个顶点的路径,共有 Fn−1F_{n-1} 种选择。

因此,总数为

Fn+1+Fn−1=Ln.F_{n+1}+F_{n-1}=L_n.

等价地,将首尾位置也视为相邻时,LnL_n 等于长度为 nn 且不含相邻两个 1 的二进制串的数量。各位置仍带有标号:通过旋转可以相互得到的字符串分别计数。

按照子集大小分类计数,可得

Ln=∑k=0⌊n/2⌋nn−k(n−kk)(n≥1),L_n= \sum_{k=0}^{\lfloor n/2\rfloor} \frac{n}{n-k}\binom{n-k}{k} \qquad(n\geq1),

其中,(n−kk)\binom{n-k}{k} 是二项式系数。对于 n≥3n\geq3 的环图,求和中的每一项表示恰好包含 kk 个顶点的合规子集的数量。

整除性与素数项

卢卡斯数在数论中呈现出许多规律。其奇偶性以三为周期重复:

Ln is even⟺3∣n.L_n\text{ is even}\quad\Longleftrightarrow\quad 3\mid n.

这可以通过对递推关系取模 22 得出。

更一般地,对每个正整数 mm,该数列模 mm 都是纯周期的。在模算术中,变换

(Ln,Ln+1)⟼(Ln+1,Ln+Ln+1)(L_n,L_{n+1})\longmapsto(L_{n+1},L_n+L_{n+1})

是可逆的,而余数对只有有限多个。

对于 n≥1n\geq1 和奇正整数 kk,

Ln∣Lkn.L_n\mid L_{kn}.

与斐波那契数不同,卢卡斯数并非对所有满足 a∣ba\mid b 的正整数 a,ba,b 都满足 La∣LbL_a\mid L_b:例如,L2=3L_2=3 不能整除 L4=7L_4=7。

卢卡斯素数是指本身为素数的卢卡斯数。最初的几个例子为

2, 3, 7, 11, 29, 47, 199, 521.2,\ 3,\ 7,\ 11,\ 29,\ 47,\ 199,\ 521.

目前尚不清楚卢卡斯素数是否有无穷多个。

对于每个素数 pp,

Lp≡1(modp).L_p\equiv1\pmod p.

这一同余式类似于费马小定理,但其逆命题不成立。合数也可能满足 Ln≡1(modn)L_n\equiv1\pmod n,因此仅凭这一同余式无法判定一个数是否为素数。

广义卢卡斯序列

标准卢卡斯数属于一个双参数序列族。对于固定的整数 P,QP,Q,定义

U0=0,U1=1,Un=PUn−1−QUn−2,U_0=0,\quad U_1=1,\quad U_n=PU_{n-1}-QU_{n-2},

以及

V0=2,V1=P,Vn=PVn−1−QVn−2.V_0=2,\quad V_1=P,\quad V_n=PV_{n-1}-QV_{n-2}.

标准的斐波那契数和卢卡斯数分别对应于

Fn=Un(1,−1),Ln=Vn(1,−1).F_n=U_n(1,-1), \qquad L_n=V_n(1,-1).

若 α,β\alpha,\beta 是 x2−Px+Q=0x^2-Px+Q=0 的两个不同的根,则

Un=αn−βnα−β,Vn=αn+βn.U_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}, \qquad V_n=\alpha^n+\beta^n.

这一更广泛的框架是许多整除性结论和基于卢卡斯序列的素性检验的基础。不加限定的“卢卡斯数”通常指特定数列 2,1,3,4,7,…2,1,3,4,7,\ldots,而非这一序列族中的所有成员。

计算

依次使用递推关系计算 LnL_n,需要 O(n)O(n) 次整数加法,且只需存储相邻两项。矩阵快速幂或斐波那契数的快速倍增恒等式可将算术运算次数降至 O(log⁡n)O(\log n),这里使用的是大O记号。

这些运算次数并不意味着精确计算的位复杂度是对数级的:LnL_n 本身的二进制位数就与 nn 成正比,而且大整数的算术运算成本更高。使用固定精度的浮点运算直接计算 ϕn+ψn\phi^n+\psi^n,可能因精度损失而在舍入后得到错误的整数。采用精确的递推或倍增方法可以避免这一问题。