fibonacci

什么是斐波那契数列?

斐波那契数列(Fibonacci sequence)是以意大利数学家列昂纳多·斐波那契的名字命名的数列。该数列具有一些很好的性质,比如在$n$很大时,$\frac{F_{n+1}}{F_n} \approx \phi$,其中$\phi$是黄金分割数,等于$1.618\cdots$ 。斐波那契数列在计算机里面有很多用途,例如斐波那契查找(二分查找的一种改进),斐波那契堆等。斐波那契数列定义为:
$$
F_n =
\begin{cases}
0, &(n=0)\\
1, &(n=1)\\
F_{n-1}+F_{n-2},&(n>1)\\
\end{cases}
$$

渐进关系的证明:

下面我们要来证明
$$
\lim_{n \to +\infty}\frac{F_{n+1}}{F_n} = \phi
$$
首先,为了证明这一公式,让我们先来证明下面的等式:
$$
F_n = \frac{\phi^n-{\hat\phi}^n}{\sqrt 5}
$$
其中$\phi$和$\hat \phi$分别是黄金分割数和其共轭数,他们是方程$x^2 = x + 1$的两个根。

显然
$$
F_0 = \frac{1-1}{\sqrt 5} = 0,\quad F_1 = \frac{\sqrt 5}{\sqrt 5} = 1
$$
满足欲证等式。

对于所有正整数$k$,若$F_{k-1}, \, F_k$满足我们要证明的等式,即
$$
F_{k-1} = \frac{\phi^{k-1} - {\hat \phi}^{k-1}}{\sqrt 5}, \quad
F_k = \frac{\phi^k - {\hat \phi}^k}{\sqrt 5}
$$

那么
$$
\begin{aligned}
F_{k+1}
&= F_{k} + F_{k-1}\\
&= \frac{\phi^k - {\hat \phi}^k}{\sqrt 5} + \frac{\phi^{k-1} - {\hat \phi}^{k-1}}{\sqrt 5}\\
&= \frac{(\phi^k + \phi^{k-1})-({\hat \phi}^k + {\hat \phi}^{k-1})}{\sqrt 5}
\end{aligned}
$$

由于$\phi$和$\hat \phi$满足方程$x^2 = x + 1$,因此
$$
\phi^2 = \phi + 1,\quad
{\hat \phi}^2 = {\hat \phi} + 1\\
\phi^3 = \phi^2 + \phi,\quad {\hat \phi}^3 = {\hat \phi}^2 +{\hat \phi}\\
\cdots \cdots \cdots \cdots \\
\phi^{k+1} = \phi^k + \phi^{k-1},\quad
{\hat \phi}^{k+1} = {\hat \phi}^k +{\hat \phi}^{k-1}\\
$$
代入上面的式子,便知$F_{k+1}$也满足该等式。
$$
\begin{aligned}
F_{k+1}
&= \frac{(\phi^k + \phi^{k-1})-({\hat \phi}^k + {\hat \phi}^{k-1})}{\sqrt 5}\\
&= \frac{\phi^{k+1} - {\hat \phi}^{k+1}}{\sqrt 5}
\end{aligned}
$$
显然,我们可以从$F_0$和$F_1$满足该等式,推知$F_2$也必定满足该等式,从$F_1$和$F_2$满足该等式又可推知$F_3$必定也满足……。这正是归纳法的思想。

利用我们刚刚证明了的等式,

因为
$$
|\hat \phi| = \Bigg{|}\frac{1 - \sqrt5}{2} \Bigg{|} < 1, \quad
\lim_{n \to +\infty} {\hat \phi}^n = 0
$$
所以
$$
\begin{aligned}
\lim_{n \to +\infty}{\frac{F_{n+1}}{F_n}} &= \lim_{n \to +\infty}{\frac{\phi^{n+1} - {\hat \phi}^{n+1}}{\phi^n - {\hat \phi}^n}}\\
&= \frac{\phi^{n+1}}{\phi^n}\\
&= \phi
\end{aligned}
$$
这就证明了文章开头给出的$F_{n+1}/F_n$与$\phi$的渐进关系。

一个小小的想法

将上面给出的等式稍作修改
$$
\phi^n-{\hat\phi}^n = F_n \cdot {\sqrt 5}
$$

$$
({\frac{1 + \sqrt5}{2}})^n-({\frac{1 - \sqrt5}{2}})^n = F_n \cdot {\sqrt 5}
$$

$$
\frac{(1 + \sqrt5)^n - (1 - \sqrt5)^n}{\sqrt 5} = 2^{n}F_n
$$
我们猜想这个等式具有一般性,即若以
$$
G_{mn} = \frac{(1 + \sqrt{m})^n - (1 - \sqrt{m})^n}{\sqrt{m}}
$$
表示某一整数数列$G_m$的第$n$项,则$G_{mn}$一定为整数。

这个结论其实是显然的,我下面将给出一个证明,这个证明通过给出$G_{mn}$的递推公式来证明$G_m$的任一项都是整数。至于数列$G_m​$是否像斐波那契数列一样具有一些美好的性质,这就有待于兴趣者去探索了。

证明:

$$
G_{m0} = 0, \quad G_{m1} = 2, \quad G_{m2} = 4
$$
显然为整数。
当$n$为大于0的整数时,
$$
\begin{aligned}
G_{m(n+1)}
&= \frac{(1 + \sqrt{m})^{n+1} - (1 - \sqrt{m})^{n+1}}{\sqrt{m}}\\
&= \frac{(1 + \sqrt{m})[(1 - \sqrt{m})^n + \sqrt{m}G_{mn}] - (1 - \sqrt{m})[(1 + \sqrt{m})^n - \sqrt{m}G_{mn}]}{\sqrt{m}}\\
&= \frac{2\sqrt{m}G_{mn} + [(1 + \sqrt{m})(1 - \sqrt{m})^n - (1 - \sqrt{m})(1 + \sqrt{m})^n]}{\sqrt{m}}\\
&= 2G_{mn} + [(1 + \sqrt{m})(1 - \sqrt{m})]\frac{(1 - \sqrt{m})^{n-1} - (1 + \sqrt{m})^{n-1}}{\sqrt{m}}\\
&= 2G_{mn} + [(\sqrt{m} + 1)(\sqrt{m} - 1)]\frac{(1 + \sqrt{m})^{n-1} - (1 - \sqrt{m})^{n-1}}{\sqrt{m}}\\
&= 2G_{mn} + (m - 1)G_{m(n-1)}
\end{aligned}
$$
这表明$G_{m(n+1)}$可以由$G_{mn}$和$G_{m(n-1)}$仅通过加法和乘法得到,而我们知道,整数的加法运算和乘法运算只能产生整数,因为数列的第一二项都是整数,所以其后面的任一项也比必然是整数。

这就证明了我们的猜想。

从证明的结果,$G_{mn}$的递推公式可以看出,数列
$$
H_{mn} = \frac{(\frac{(1 + \sqrt{m})}{2})^{n} - (\frac{(1 - \sqrt{m})}{2})^{n}}{\sqrt{m}}
$$
的递推公式应该是
$$
H_{mn} =
\begin{cases}
{0,} & n = 0\\
{1,} & n = 1\\
{H_{m(n-1)} + \frac{m - 1}{4}H_{m(n-2)},} & n > 1
\end{cases}
$$
当m等于5时,$H_{5n}$正是这篇文章的主题,斐波那契数列。

斐波那契数的计算

  • 直接递归计算
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)
  • 通过循环消除栈的开销
def fibonacci(n):
    l, v = 0, 1
    for i in range(1, n ,2):
        l += v
        v += l
    if n & 1:
        return v
    return l

斐波那契数的快速计算

在$n​$大于1时,不断将$F_n=F_{n-1}+F_{n-2}​$代入$F_n​$的迭代计算式右边的第一项,可把$F_n​$作如下展开:
$$
\begin{aligned}
F_n &= F_{n-1} + F_{n-2}\\
&=1F_{n-1}+1F_{n-2}= F_{2}F_{n-1}+F_{1}F_{n-2}\\
&= 2F_{n-2}+1F_{n-3} = F_{3}F_{n-2}+F_{2}F_{n-3}\\
&= 3F_{n-3}+2F_{n-4} = F_{4}F_{n-3}+F_{3}F_{n-4}\\
&= 5F_{n-4}+3F_{n-5} = F_{5}F_{n-4}+F_{4}F_{n-5}\\
&\ldots\ldots\ldots\ldots
\end{aligned}
$$

不难发现$F_n$的展开式满足下面这个通式:
$$
\begin{aligned}
F_n &= F_kF_{n-k+1} + F_{k - 1}F_{n - k}\\
&= F_{k+1}F_{n-k} + F_{k}F_{n - (k+1)},(k\Rightarrow k+1)\\
\end{aligned}
$$

这里可以分为两种情况进行讨论。

  1. $n$为偶数,取$k=n/2$,则 $n-k=k$,采用迭代式的第一式,提公因子$F_k$,得:
    $$
    F_n = F_k(F_{k+1}+F_{k-1}) = F_k({F_k + 2F_{k-1}})
    $$

  2. $n$为奇数,取$k= \left\lfloor{n/2}\right\rfloor$,则 $n-k=k+1$,采用迭代式第二式,则可得:
    $$
    F_n = F_{k+1}^2+F_k^2
    $$

归纳为一个公式如下:

$$
F_n =
\begin{cases}
F_{k+1}^2+F_k^2, &(n为奇数,k= \left\lfloor{n/2}\right\rfloor)\\
F_k({F_k + 2F_{k-1}}),&(n为偶数,k={n/2})
\end{cases}
$$
显然,这一公式使得我们可以在约$\log_2{n}$次迭代后计算出$F_n$的值。

下面根据这个公式用Python语言来计算$F_n$。

  • 简单一点的,直接递归计算
from functools import lru_cache
@lru_cache(maxsize = 20)
def fibonacci(n):
    if n < 2:
        return n
    x = fibonacci((n >> 1) - 1)
    y = fibonacci(n >> 1)
    if n & 0x1:
        x += y
        return x * x + y * y
    else:
        return y * (y + 2 * x)
  • 复杂点的,作展开,自底向上循环计算
def fibonacci(n):
    x, y, bits = 0, 1, []
    while n > 0:
        bits.insert(0, n & 0x1 == 1)
        n >>= 1
    for bit in bits[:-1]:
        u, v = x * (x + 2 * y), (x**2 + y**2)
        x, y = (u + v, u) if bit else (u, v)
    if bits and (bits[-1]):
        return x * (x + 2 * y) + x**2 + y**2
    return x * (x + 2 * y)

通过优化算法,我们确实在很大程度上减少了计算$F_n$所需的迭代次数,但这并不意味着算法的效率将有指数级的提升,或者说时间复杂度会有对数级的下降,因为乘法运算显然会比加法运算花费更多的时间。但即便如此,对于$F_n$的直接计算,相较于普通的计算方法,上述算法的加速效果还是很可观的。具体时间复杂度的分析就不在此展开了。

附注

关于斐波那契数列的快速算法还有幂矩阵法,不过理论和实践都表明,上面的这一种方法的速度约为幂矩阵法的4倍。

斐波那契数列幂矩阵算法的Python实现:

def fibo_mat(n):
    lhm = [[0,1], [1,1]]
    rhm = [[0], [1]]
    em = [[1,0], [0,1]]
    # multiply two matrixes
    def matrix_mul(lhm, rhm):
        # initialize an empty matrix filled with zero
        result=[[0 for i in range(len(rhm[0]))] for j in range(len(rhm))]
        # multiply loop
        for i in range(len(lhm)):
            for j in range(len(rhm[0])):
                for k in range(len(rhm)):
                    result[i][j] += lhm[i][k] * rhm[k][j]
        return result

    def matrix_square(mat):
        return matrix_mul(mat, mat)
        #quick transform
    def fib_pow(mat, n):
        if not n:
            return em
        elif(n & 0x1):
            return matrix_mul(mat,fib_pow(mat ,n - 1))
        else:
            return matrix_square(fib_pow(mat, n >> 1))
    return matrix_mul(fib_pow(lhm,n),rhm)[0][0]