最近看的书都有点依赖数学知识, 感觉自己有点不自量力了. 不过今天看到的一个关于斐波那契数列的特性挺有意思的, 在这里和大家分享一下.

TL;DR: 先说这个特性是什么

令 F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 (n >= 2). 显然 F 是一个斐波那契数列.

定义 gcd(x, y) 为 x 和 y 的最大公约数.

我们有 gcd(Fn, Fm) = Fgcd(n, m).

在证明这个结论之前, 我们先介绍两个证明过程中需要的前置知识.

前置知识一 - Fn+1 和 Fn 互质

这个结论使用数学归纳法很容易证明.

当 n = 0 的时候显然成立.

假设 n <= k - 1* 时都成立. 根据定义 *Fk+1 = Fk + Fk-1. 假设存在 d > 1, 可以同时整除 Fk+1 和 Fk, 易知 d 也可以整除两者之差 Fk-1, 这与 Fk 和 Fk-1 互质矛盾.

得证.

前置知识二 - Fn+m 和 Fn, Fm 的关系

Fn+m = FmFn+1 + Fm-1Fn

我们可以使用数学归纳法来证明这个结论.

当 m = 1 时, Fn+1 = F1Fn+1 + F0Fn = Fn+1 成立.

假设 m <= k 时, 都成立. 那么当 m = k + 1 时, 我们有

Fn+k+1

= Fn+k + Fn+k-1

=FkFn+1 + Fk-1Fn + Fk-1Fn+1 + Fk-2Fn (套用假设)

=(Fk + Fk-1)Fn+1 + (Fk-1 + Fk-2)Fn (合并同类项)

=Fk+1Fn+1 + FkFn (斐波那契数列定义)

得证.

公约数特性的证明

有了上面的前置知识, 我们就可以证明最开始提到的最大公约数特性了. 证明如下:

(1) 由于前置知识二 Fn+m = FmFn+1 + Fm-1Fn, 我们可以知道任何 Fn, Fm 的公约数, 都是 Fn+m 的约数.

(2) 与此同时, 由于Fn+m = FmFn+1 + Fm-1Fn, 并且Fn+1 和 Fn 互质, 我们可以知道任何 Fn+m, Fn 的公约数 d, 都是 Fm 的约数. 这是因为Fn+m - Fm-1Fn = FmFn+1, 等式左边能被 d 整除, 右边也必须能被 d 整除. 而 Fn+1 和 d 没有公约数, 所有 d 必须整除 Fm.

(3) 根据以上两个结论, 我们知道 d 能整除 Fm, Fn 等价于 d 能整除 Fm+n, Fn.

(4) 推广上面的结论, 我们可以知道 d 能整除 Fm, Fn 等价于 d 能整除 Fm+kn, Fn. 注意到 m = m + kn (mod n), 我们用 m 替换 m+kn 可以得到下面的结论 (5).

(5) d 能整除 Fm % n, Fn 等价于 d 能整除 Fm, Fn. 所以 gcd(Fm, Fn) = gcd(Fm%n, Fn). 这实际上就是欧几里得法求最大公约数的迭代过程, 迭代到最后可以得到**gcd(Fm, Fn) = gcd(F0, Fgcd(m, n))**.

(6) 由于 F0 =0, 且 gcd(0, x) = x, 我们得到 gcd(Fm, Fn) = Fgcd(m, n).

得证.

小彩蛋:斐波那契数的快速计算

对于第 n 个斐波那契数的计算, 相信有一定编程基础的朋友们都知道可以用简单的 O(n) 算法来实现. 这里来介绍一个简单的 O(logn) 的算法.

由于 F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 (n >= 2), 可知 Fn 是一个线性变换, 可以用一个矩阵表示.

所以

$$ \left[
\begin{matrix}
F_{n} \\
F_{n-1} \\
\end{matrix}
\right] = \left[
\begin{matrix}
1 & 1 \\
1 & 0 \\
\end{matrix}
\right] \left[
\begin{matrix}
F_{n-1} \\
F_{n-2} \\
\end{matrix}
\right]$$

不断替换可以得到

$$ \left[
\begin{matrix}
F_{n} \\
F_{n-1} \\
\end{matrix}
\right] = \left[
\begin{matrix}
1 & 1 \\
1 & 0 \\
\end{matrix}
\right]^{n-1} \left[
\begin{matrix}
F_{1} \\
F_{0} \\
\end{matrix}
\right] $$

由于矩阵乘法满足结合律, 我们可以使用快速幂算法来加速达到 O(logn) 的时间复杂度. 代码可以阅读这里. 阅读需要一定的数学知识, 但是核心思想很简单, 就是 $$x^n = (x \times x) ^{n/2} \times x^{n \% 2}$$.