fabonacci

引入#

也许我们在网络当中会看到一个神奇的数： $\displaystyle\frac{1}{89}$

\frac{1}{89}=0.01123595505\dots

稍作注意可以很明显看到，似乎遵循着斐波那契的某种规律？

看起来像是很多个斐波那契数相加之后的结果？这里的 9 可以分解为 8 和 1，似乎全是斐波那契数相加起来的

根据 Fibonacci 数列的性质，可以得到一个等式：

\displaystyle\frac{1}{89}=\sum\limits_{n=1}^{\infty} \frac{F_{n}}{10^n}

其中：

F_{n}=F_{n-1}+F_{n-2}(n\geq 2),F_{0}=0,F_{1}=1

所以现在我们要来验证这个等式 ,看看它究竟是不是斐波那契数列加起来的结果

我们可以先将 $\frac{1}{10}$ 记为 $x$ ，现在原式为：

F(x)=\sum\limits_{n=1}^{\infty} F_{n}\cdot x^n

即

F(x)=1x^1+1x^2+2x^3+3x^4+5x^5+\dots

这是一个形式幂级数，这个形式似乎非常熟悉

我们来尝试使用一些技巧来求出 $F(x)$ ，因为我们知道 $F_{n}$ 的通项公式，所以可以构造 $F_{n-1},F_{n-2}$ :

\begin{align} F(x)=1x^1+1x^2+2x^3+3x^4+5x^5+8x^6+13x^7 +\dots \\ xF(x)=1x^2+1x^3+2x^4+3x^5+5x^6+8x^7+\dots \\ x^2F(x)=1x^3+1x^4+2x^5+3x^6+5x^7+\dots \end{align}

所以

(1-x-x^2)F(x)=x

\implies\boxed{F(x)=\frac{x}{1-x-x^2}}

更加形式化的论证

设

F(x)=\sum_{n=0}^{\infty}F_nx^n.

递推式

F_n=F_{n-1}+F_{n-2}

对 $n\ge2$ 成立。

对递推式两边乘以 $x^n$ ，并从 $n=2$ 到 $\infty$ 求和：

\sum_{n=2}^{\infty}F_nx^n = \sum_{n=2}^{\infty}F_{n-1}x^n + \sum_{n=2}^{\infty}F_{n-2}x^n.

逐项改写。

左边：

\sum_{n=2}^{\infty}F_nx^n = F(x)-F_0-F_1x = F(x)-x.

因为 $F_0=0,F_1=1$ 。

右边第一项：

\sum_{n=2}^{\infty}F_{n-1}x^n = x\sum_{n=2}^{\infty}F_{n-1}x^{n-1} = x\sum_{m=1}^{\infty}F_mx^m = x(F(x)-F_0) = xF(x).

右边第二项：

\sum_{n=2}^{\infty}F_{n-2}x^n = x^2\sum_{n=2}^{\infty}F_{n-2}x^{n-2} = x^2F(x).

所以

F(x)-x=xF(x)+x^2F(x).

整理：

F(x)(1-x-x^2)=x.

因此

F(x)=\frac{x}{1-x-x^2}.

取 $x=\frac{1}{10}$ ：

f\left( \frac{1}{10} \right)= \frac{\frac{1}{10}}{1-\frac{1}{10}-\left( \frac{1}{10} \right)^2}=\frac{10}{89}=0.1123595505\dots

这里的差距主要是由于我们 Fn 的定义不同，若这里的 $F_{1}$ 定义为 0(我们这里的 $F_{0}$ 定义为 0，主要为了后文方便)则为 $\frac{1}{89}$ ，但无论如何，可以发现它确实就是斐波那契数求和的结果

快速理解生成函数

以求集合 $\{1,2,3,4,5\}$ 元素和为 8 的子集个数为例：

通常我们看到这个问题显然可以直接枚举子集，然后选出和为 8 的个数，或者当做一个 DP/搜索题目去做。

但是这里可以使用

(1+x^1)(1+x^2)(1+x^3)(1+x^4)(1+x^5)

其中对于 $x^8$ 的系数则是答案

但是凭什么呢？

我想很多人都会赞同这种做法的正确性，仔细一想似乎也合理，因为每个都和其他多项式充分进行了计算，这不就是计算的子集

但是为什么我们会拉出这个多项式呢？且为什么偏偏是 $(1+x^k)$ 这样的形式？

说起加法/乘法原理都不陌生，我们先计算一下子集个数是怎么来的：

对于每个元素都有两种选择：选/不选

所以则是 $(1+1)(1+1)(1+1)(1+1)(1+1)=32$ 个子集

看起来似乎可以和上面的多项式一一对应；这里的加法代表了「或」、乘法代表了「和」

所以上面的即为 (不选 1或选 1)和(不选 2或选 2)和(不选 3或选 3)和(不选 4或选 4)和(不选 5或选 5)

这样似乎就好理解多了，我们可以将这个式子展开，例如第一项为 全部不选 下一项为 除了 1 全部不选…一共 32 项和子集对应，然后对于每一个项都可以被计算为某个值：将选择了的项全部相加。

但是这里似乎又有一个问题了，为什么上面是 $(1+1)$ 体现的一样，可不可以是 $(1+1)(1+2)(1+3)(1+4)(1+5)$ 这样呢？

当然计算出的结果显然是不对的，but why not?

在计算的时候 或/和 运算分别被替换为了加法和乘法，要计算子集的元素和，显然应该将被选择的元素加起来才对(而对于这个错误的式子则是相乘的： $2\times3,3\times5\dots$ )，在这里应该 将乘法转变到加法，而指数运算就有这种性质： $x^3\times x^5=x^8$ ，这里的底数是怎样并不重要

于是，母函数/生成函数就出现了：

P(x)=(1+x^1)(1+x^2)(1+x^3)(1+x^4)(1+x^5)

对于上面的 (不选 1或选 1)和(不选 2或选 2)和(不选 3或选 3)和(不选 4或选 4)和(不选 5或选 5) 式子，这里每次不选对结果的影响为 0(加 0)，选了则影响对应的元素大小(加 k)，对于多个加法可以被合成为 1 个

所以可以被化简为这样

(加 0 或加 1)(加 0 或加 2)(加 0 或加 3)(加 0 或加 4)(加 0 或加 5)
= 加 0 或加 1 或加 2 或 2 加 3 或 2 加 4 或 3 加 5 或 3 加 6 或 3 加 7 或 3 加 8 或 3 加 9 或 3 加 10 或 2 加 11 或 2 加 12 或加 13 或加 14 或加 15

plaintext

而这和 $P(x)$ 原式展开之后式子之间是同构的(将这里的 加 k 变为 $x^k$ )，原式展开后为：

$1+x+x ^2+2 x^ 3+2 x^ 4+3 x^ 5+3 x^ 6+3 x^ 7+3 x^ 8+3 x^ 9+3 x^{10}+2 x^{11}+2 x^{12}+x^{13}+x^{14}+x^{15}$

这里我们的问题完美得到了解决

那如果换一个问题呢？

求集合 $\{1,2,3,4,5\}$ 有三个元素的子集个数

那么我们需要新的生成函数了

让我们来算算影响：加/不加入子集，对答案的影响为 1/0

所以是：

(加 0 或加 1)(加 0 或加 1)(加 0 或加 1)(加 0 或加 1)(加 0 或加 1)

plaintext

所以变为：

(1+x)^5

展开之后， $x^3$ 则为答案

现在新的问题又来了,凭什么这个幂级数就等于这个分数呢，感觉完全不对吧？这个等式来源于哪里？

对于等比数列的求和：

\begin{matrix} a_{n}=qa_{0}^{n-1}(n>1) \\ a_{0}+a_{0}q+a_{0}q^2+\dots+a_{0}q^{n-1}=\frac{a_{0}(1-q^n)}{1-q} \\ \\ \end{matrix}

所以

1+x+x^2+x^3+\dots+x^n=\frac{1-x^n}{1-x}

$x^n-1$ 和 $x-1$ 的拆解很多时候也能算作是一个技巧

n\in(-1,1),x\to \infty, \frac{1-x^n}{1-x}\to \frac{1}{1-x}

在定义域范围内，将对应的式子对应到图像上，确实和幂级数是对应的，这个式子的泰勒展开，也就是对应的幂级数

但是在定义域之外的情况，似乎就不太能够真正对应，对于这种情况，在数学的很多领域当中都会出现，比如虚数的出现也是在我们捏着鼻子去硬算，假设他是存在的，然后也发展出了数学分支

有时我们也能够看到这一个等式(黎曼函数的解析延拓)

\zeta(-1)=\sum\limits_{n=1}^\infty \frac{1}{n^{-1}}=\sum\limits_{n=1}^\infty n=1+2+3+4+\dots=-\frac{1}{12}

它超出了我们的常理，似乎是我们完全不可接受的，实际上按照常规的代数手段而言也确实是这样，应当有定义域的限制才对

而这里我们可以把它看作是形式幂级数等式，也就是说它并不是某个函数在某个 x 上取值是相等的，而是两个序列的每一项系数相等。形式幂级数把一串数用一个形式变量 x 编码起来

通项公式推导#

这里我们会给出多种通项公式的推导

构造等比数列#

令

\varphi=\frac{1+\sqrt 5}{2},\qquad \psi=\frac{1-\sqrt 5}{2}

考虑构造

G_n=F_{n+1}-\varphi F_n

利用递推 $F_{n+1}=F_n+F_{n-1}$ 以及 $\varphi \psi=-1,\varphi+\psi=1$ ：

\begin{aligned} G_n &=F_n+F_{n-1}-\varphi F_n\\ &=(1-\varphi)F_n+F_{n-1}\\ &=\psi F_n+F_{n-1}\\ &=\psi(F_n-\varphi F_{n-1})\\ &=\psi G_{n-1} \end{aligned}

也就是说 $G_n$ 是等比数列：

G_n=\psi^n G_0,G _0=F_ 1-\varphi F_0=1

所以

F_{n+1}-\varphi F_n=\psi^n

于是

F_{n+1}=\varphi F_n+\psi^n

从 $F_0=0$ 开始迭代：

\begin{aligned} F_n &=\varphi F_{n-1}+\psi^{n-1}\\ &=\varphi(\varphi F_{n-2}+\psi^{n-2})+\psi^{n-1}\\ &=\varphi^2F_{n-2}+\varphi\psi^{n-2}+\psi^{n-1}\\ &=\cdots\\ &=\varphi^nF_0+\sum_{k=0}^{n-1}\varphi^{n-1-k}\psi^k\\ &=\sum_{k=0}^{n-1}\varphi^{n-1-k}\psi^k \end{aligned}

设

S=\sum_{k=0}^{n-1}\varphi^{n-1-k}\psi^k

则

\varphi S-\psi S =\varphi^n-\psi^n.

因为

\varphi S=\sum_{k=0}^{n-1}\varphi^{n-k}\psi^k, \psi S=\sum_{k=0}^{n-1}\varphi^{n-1-k}\psi^{k+1}.

两式相减，中间项全部抵消，得到

(\varphi-\psi)S=\varphi^n-\psi^n.

F_n=\frac{\varphi^n-\psi^n}{\varphi-\psi}

所以

\boxed{ F_n=\frac 1{\sqrt 5} \left[ \left(\frac{1+\sqrt 5}{2}\right)^n - \left(\frac{1-\sqrt 5}{2}\right)^n \right] }

生成函数#

设

F(x)=\sum_{n=0}^{\infty}F_nx^n

利用

F_n=F_{n-1}+F_{n-2}

可以推出(引入已经给出)

F(x)=\frac{x}{1-x-x^2}

设

\frac{x}{1-x-x^2} = \frac{A}{1-\alpha x} + \frac{B}{1-\beta x}.

解得：

A=\frac{1}{\sqrt{ 5 }},B=-\frac{1}{\sqrt{ 5 }}

\implies\frac{x}{1-x-x^2} = \frac{1}{\sqrt 5} \left( \frac{1}{1-\alpha x} - \frac{1}{1-\beta x} \right)

由前面学到的知识，可以知道，这就是 $\frac{1}{1-x}$ 的形式，所以

\frac{1}{1-\alpha x}=\sum\limits_{n=0}^{\infty}(\alpha x)^n, \frac{1}{1-\beta x}=\sum\limits_{n=0}^{\infty}(\beta x)^n

所以

F(x)=\frac{1}{\sqrt{ 5 }}\sum\limits_{n=0}^{\infty}(\alpha^n -\beta^n)x^n=\sum\limits_{n=0}^{\infty}F_{n}x^n

\implies F_{n}=\frac{1}{\sqrt{ 5 }}(\alpha^n-\beta^n)

这里的 $\alpha,\beta$ 在计算 $A,B$ 的时候，那个等式就已经可以得出，不再赘述

矩阵幂与对角化#

递推的矩阵形式

由

F_{n+1}=F_n+F_{n-1}

可得

\begin{pmatrix} F_{n+1}\\ F_n \end{pmatrix} = \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix} \begin{pmatrix} F_n\\ F_{n-1} \end{pmatrix}.

记

A=\begin{pmatrix}1&1\\1&0\end{pmatrix}.

于是

\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix} =A^n \begin{pmatrix}F_1\\F_0\end{pmatrix} =A^n \begin{pmatrix}1\\0\end{pmatrix}.

求 $A$ 的特征值和特征向量

特征多项式为

\det(A-\lambda I) = \begin{vmatrix} 1-\lambda&1\\ 1&-\lambda \end{vmatrix} =\lambda^2-\lambda-1.

所以特征值为

\lambda=\varphi,\psi.

其中

\varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}.

对特征值 $\varphi$ ，求特征向量：

A\begin{pmatrix}\varphi\\1\end{pmatrix} = \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix} \begin{pmatrix}\varphi\\1\end{pmatrix} = \begin{pmatrix}\varphi+1\\\varphi\end{pmatrix} = \begin{pmatrix}\varphi^2\\\varphi\end{pmatrix} = \varphi\begin{pmatrix}\varphi\\1\end{pmatrix}.

这里用了

\varphi^2=\varphi+1.

所以特征向量可取

v_\varphi=\begin{pmatrix}\varphi\\1\end{pmatrix}.

同理，

v_\psi=\begin{pmatrix}\psi\\1\end{pmatrix}.

令

P= \begin{pmatrix} \varphi&\psi\\ 1&1 \end{pmatrix}.

则

A=P \begin{pmatrix} \varphi&0\\ 0&\psi \end{pmatrix} P^{-1}.

计算 $P^{-1}$

因为

\det P=\varphi-\psi=\sqrt5,

所以

P^{-1} = \frac1{\sqrt5} \begin{pmatrix} 1&-\psi\\ -1&\varphi \end{pmatrix}.

于是

A^n = P \begin{pmatrix} \varphi^n&0\\ 0&\psi^n \end{pmatrix} P^{-1}.

求 $F_n$

因为

\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix} =A^n \begin{pmatrix}1\\0\end{pmatrix},

先算

P^{-1} \begin{pmatrix}1\\0\end{pmatrix} = \frac1{\sqrt5} \begin{pmatrix} 1&-\psi\\ -1&\varphi \end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix} = \frac1{\sqrt5} \begin{pmatrix}1\\-1\end{pmatrix}.

所以

\begin{aligned} \begin{pmatrix}F_{n+1}\\F_n\end{pmatrix} &= P \begin{pmatrix} \varphi^n&0\\ 0&\psi^n \end{pmatrix} P^{-1} \begin{pmatrix}1\\0\end{pmatrix}\\ &= \frac1{\sqrt5} \begin{pmatrix} \varphi&\psi\\ 1&1 \end{pmatrix} \begin{pmatrix} \varphi^n&0\\ 0&\psi^n \end{pmatrix} \begin{pmatrix}1\\-1\end{pmatrix}\\ &= \frac1{\sqrt5} \begin{pmatrix} \varphi&\psi\\ 1&1 \end{pmatrix} \begin{pmatrix} \varphi^n\\ -\psi^n \end{pmatrix}\\ &= \frac1{\sqrt5} \begin{pmatrix} \varphi^{n+1}-\psi^{n+1}\\ \varphi^n-\psi^n \end{pmatrix}. \end{aligned}

比较第二个分量，得到

\boxed{ F_n=\frac{\varphi^n-\psi^n}{\sqrt5}. }

组合数学#

这里考虑走楼梯的场景：

设走完 $m$ 级阶梯的方法数为 $T_{m}$

易得： $T_{0}=1,T_{1}=1$ ,且 $T_{m}=T_{m-1}+T_{m-2}$

可以发现这里的 $T_{n}$ 相对于我们定义的 $F_{n}$ 偏移了一位

假设走完 $m$ 级时，走了 $k$ 步 2 级阶梯，则剩下的 $m-2k$ 级是使用的 1 级走

一共走了 $m-2k+k=m-k$ 步

所以是在 $m-k$ 步中选出了 $k$ 步走 2 级，方法数为

\binom{m-k}{k}

当然走一级和走二级是等价/对称的，也可以是 $\binom{m-k}{m-2k}$ ，结果是一样的

易得：

T_m=\sum_{k=0}^{\lfloor m/2\rfloor}\binom{m-k}{k}.

\implies F_n=T_{n-1} = \sum_{k=0}^{\lfloor (n-1)/2\rfloor} \binom{n-1-k}{k}.

这里可以选择求 $T_{m}$ 或者 $F_{n}$ 的生成函数，不过 $T_{m}$ 看起来更简洁

求

T_{m}

的生成函数

设

G(x)=\sum_{m=0}^{\infty}T_mx^m.

代入

T_m=\sum_{k=0}^{\lfloor m/2\rfloor}\binom{m-k}{k}.

约定当 $k>m-k$ 时 $\binom{m-k}{k}=0$ ，则

G(x) = \sum_{m=0}^{\infty} \sum_{k=0}^{\infty} \binom{m-k}{k}x^m.

交换求和顺序。令

j=m-k,

则

m=j+k.

于是

G(x) = \sum_{k=0}^{\infty} \sum_{j=k}^{\infty} \binom{j}{k}x^{j+k}.

整理：

G(x) = \sum_{k=0}^{\infty}x^k \sum_{j=k}^{\infty}\binom{j}{k}x^j.

利用恒等式

\sum_{j=k}^{\infty}\binom{j}{k}x^j = \frac{x^k}{(1-x)^{k+1}},

得到

G(x) = \sum_{k=0}^{\infty} x^k\cdot \frac{x^k}{(1-x)^{k+1}} = \sum_{k=0}^{\infty} \frac{x^{2k}}{(1-x)^{k+1}}.

提出 $\frac1{1-x}$ ：

G(x) = \frac1{1-x} \sum_{k=0}^{\infty} \left(\frac{x^2}{1-x}\right)^k.

这是几何级数，公比为 $\frac{x^2}{1-x}$ ，所以

G(x) = \frac1{1-x} \cdot \frac1{1-\frac{x^2}{1-x}} = \frac1{1-x} \cdot \frac{1-x}{1-x-x^2} = \frac1{1-x-x^2}.

因此

G(x)=\frac1{1-x-x^2}.

求完生成函数就前面一样了，不再赘述

一些性质#

普通有限和#

由递推关系，

F_k=F_{k+2}-F_{k+1}.

相加以后，中间项全部抵消：

\begin{aligned} \sum_{k=1}^{N}F_k &=(F_3-F_2)+(F_4-F_3)+\cdots+(F_{N+2}-F_{N+1})\\ &=F_{N+2}-F_2. \end{aligned}

所以

\boxed{\sum_{k=1}^{N}F_k=F_{N+2}-1}.

平方和#

注意

\begin{aligned} F_kF_{k+1}-F_{k-1}F_k &=F_k(F_{k+1}-F_{k-1})\\ &=F_k^2. \end{aligned}

因而

\begin{aligned} \sum_{k=1}^{N}F_k^2 &=\sum_{k=1}^{N}\bigl(F_kF_{k+1}-F_{k-1}F_k\bigr)\\ &=F_NF_{N+1}-F_0F_1. \end{aligned}

得到

\boxed{\sum_{k=1}^{N}F_k^2=F_NF_{N+1}}.

奇/偶项和#

对奇数项，递推关系给出

F_{2k-1}=F_{2k}-F_{2k-2}.

因此

\boxed{ \sum_{k=1}^{N}F_{2k-1}=F_{2N}-F_0=F_{2N} }.

对偶数项，

F_{2k}=F_{2k+1}-F_{2k-1},

因此

\boxed{ \sum_{k=1}^{N}F_{2k}=F_{2N+1}-F_1=F_{2N+1}-1 }.

两个公式相加，就得到

\sum_{k=1}^{2N}F_k =F_{2N}+F_{2N+1}-1 =F_{2N+2}-1,

与普通有限和公式一致。

倒数和#

求它的倒数无穷和：

S=\sum_{n=1}^{\infty}\frac1{F_n} =1+1+\frac12+\frac13+\frac15+\frac18+\cdots.

令

q=\frac1\varphi=\frac{\sqrt5-1}{2},\qquad 0<q<1,

就有

\frac1{F_n} =\frac{\sqrt5}{\varphi^n-(-\varphi^{-1})^n} =\frac{\sqrt5\,q^n}{1-(-q^2)^n}.

这也直接说明了倒数和为什么收敛。因为

1-(-q^2)^n\geq 1-q^{2n}\geq 1-q^2>0,

所以

0<\frac1{F_n}\leq\frac{\sqrt5}{1-q^2}\,q^n.

右侧是收敛等比级数的通项，故由比较判别法， $S$ 收敛。

接着求它的精确表示。利用等比级数展开

\frac1{1-x}=\sum_{k=0}^{\infty}x^k,\qquad |x|<1,

得到

\begin{aligned} \frac1{F_n} &=\sqrt5\,q^n\sum_{k=0}^{\infty}(-q^2)^{nk}\\ &=\sqrt5\sum_{k=0}^{\infty}(-1)^{nk}q^{(2k+1)n}. \end{aligned}

因此

S=\sqrt5\sum_{n=1}^{\infty}\sum_{k=0}^{\infty} (-1)^{nk}q^{(2k+1)n}.

这里可以交换求和顺序，因为双重级数绝对收敛：

\sum_{n=1}^{\infty}\sum_{k=0}^{\infty} \left|(-1)^{nk}q^{(2k+1)n}\right| =\sum_{n=1}^{\infty}\frac{q^n}{1-q^{2n}} \leq\frac1{1-q^2}\sum_{n=1}^{\infty}q^n<\infty.

交换顺序后，对 $n$ 的求和就是等比级数：

\begin{aligned} S &=\sqrt5\sum_{k=0}^{\infty} \sum_{n=1}^{\infty}\left[(-1)^kq^{2k+1}\right]^n\\ &=\sqrt5\sum_{k=0}^{\infty} \frac{(-1)^kq^{2k+1}}{1-(-1)^kq^{2k+1}}. \end{aligned}

代回 $q=\varphi^{-1}$ ，得到精确表达式

\boxed{ S=\sqrt5\sum_{k=0}^{\infty} \frac{(-1)^k}{\varphi^{2k+1}-(-1)^k} },\qquad \varphi=\frac{1+\sqrt5}{2}.

展开前几项，就是

S=\sqrt5\left( \frac1{\varphi-1} -\frac1{\varphi^3+1} +\frac1{\varphi^5-1} -\frac1{\varphi^7+1} +\cdots \right).

这个表达式的项按几何速度减小，可以用于数值计算，结果为

\boxed{ \sum_{n=1}^{\infty}\frac1{F_n} =3.3598856662431775\ldots }

它没有已知的简单初等闭式，但可以从通项公式推导出精确的级数表示。

倒数平方和#

S_2=\sum_{n=1}^{\infty}\frac1{F_n^2} =1+1+\frac14+\frac19+\frac1{25}+\frac1{64}+\cdots.

令

\varphi=\frac{1+\sqrt5}{2},\qquad q=\frac1\varphi=\frac{\sqrt5-1}{2}.

Binet 公式为

F_n=\frac{\varphi^n-(-\varphi^{-1})^n}{\sqrt5} =\frac{\varphi^n\bigl(1-(-q^2)^n\bigr)}{\sqrt5}.

所以

\frac1{F_n^2} =5\frac{q^{2n}}{\bigl(1-(-q^2)^n\bigr)^2}.

利用

\frac1{(1-x)^2}=\sum_{k=0}^{\infty}(k+1)x^k, \qquad |x|<1,

可得

\begin{aligned} \frac1{F_n^2} &=5q^{2n}\sum_{k=0}^{\infty}(k+1)(-q^2)^{nk}\\ &=5\sum_{k=0}^{\infty}(k+1)(-1)^{nk}q^{(2k+2)n}. \end{aligned}

交换求和顺序后，对 $n$ 求等比级数：

\begin{aligned} S_2 &=5\sum_{k=0}^{\infty}(k+1) \sum_{n=1}^{\infty} \left[(-1)^kq^{2k+2}\right]^n\\ &=5\sum_{k=0}^{\infty}(k+1) \frac{(-1)^kq^{2k+2}}{1-(-1)^kq^{2k+2}}. \end{aligned}

由于

\frac{q^m}{1-(-1)^kq^m} =\frac1{\varphi^m-(-1)^k},

最终得到

\boxed{ \sum_{n=1}^{\infty}\frac1{F_n^2} =5\sum_{k=0}^{\infty} \frac{(k+1)(-1)^k}{\varphi^{2k+2}-(-1)^k} }.

数值为

\boxed{ \sum_{n=1}^{\infty}\frac1{F_n^2} =2.4263207511672411877415694\ldots }.

它通常就以这种快速收敛的 $\varphi$ -级数或数值常数表示，目前没有一个像有限平方和那样广为接受的初等闭式。计算前 $N$ 项时，尾项还可以估计为

0<S_2-\sum_{n=1}^{N}\frac1{F_n^2} \leq \frac43\left(\frac1{F_{N+1}^2}+\frac1{F_{N+2}^2}\right),

因为 $F_{n+2}\ge 2F_n$ 。

更一般地，对任意正整数 $p$ ，同样的方法给出统一公式

\boxed{ \sum_{n=1}^{\infty}\frac1{F_n^p} =5^{p/2}\sum_{k=0}^{\infty} \binom{p+k-1}{k} \frac{(-1)^k}{\varphi^{p+2k}-(-1)^k} }.

其中 $p=1$ 就得到前面提到的倒数和

\sum_{n=1}^{\infty}\frac1{F_n} =3.359885666243177553\ldots,

而 $p=2$ 就是上面的倒数平方和。由于 $F_n\sim \varphi^n/\sqrt5$ ，所以所有 $p>0$ 的倒数幂级数都收敛。

Cassini 恒等式#

对矩阵公式取行列式：

\det(Q^n)=(\det Q)^n=(-1)^n.

另一方面，

\det(Q^n)=F_{n+1}F_{n-1}-F_n^2.

所以

\boxed{F_{n+1}F_{n-1}-F_n^2=(-1)^n}.

例如 $8\times3-5^2=-1$ ，而 $13\times5-8^2=1$ 。

倒数乘积和#

先看此前提到的

\sum_{n=1}^{\infty}\frac1{F_nF_{n+2}}.

因为 $F_{n+2}-F_n=F_{n+1}$ ，有

\begin{aligned} \frac1{F_nF_{n+1}}-\frac1{F_{n+1}F_{n+2}} &=\frac{F_{n+2}-F_n}{F_nF_{n+1}F_{n+2}}\\ &=\frac1{F_nF_{n+2}}. \end{aligned}

所以前 $N$ 项之和为

\sum_{n=1}^{N}\frac1{F_nF_{n+2}} =1-\frac1{F_{N+1}F_{N+2}}.

最后一项趋于 $0$ ，得到

\boxed{\sum_{n=1}^{\infty}\frac1{F_nF_{n+2}}=1}.

另一个有趣的结果直接来自 Cassini 恒等式。它给出

\begin{aligned} r_{n+1}-r_n &=\frac{F_{n+2}F_n-F_{n+1}^2}{F_nF_{n+1}}\\ &=\frac{(-1)^{n+1}}{F_nF_{n+1}}. \end{aligned}

$r_{n}=\frac{F_{n+1}}{F_{n}}$

相加得到

\sum_{n=1}^{N}\frac{(-1)^{n+1}}{F_nF_{n+1}} =r_{N+1}-r_1.

由于 $r_1=1$ 、 $r_{N+1}\to\varphi$ ，所以

\boxed{ \sum_{n=1}^{\infty}\frac{(-1)^{n+1}}{F_nF_{n+1}} =\varphi-1=\frac1\varphi }.

展开就是

1-\frac12+\frac16-\frac1{15}+\frac1{40}-\cdots =\frac{\sqrt5-1}{2}.

下标为 $2$ 的幂的倒数和#

考虑

T=\sum_{k=0}^{\infty}\frac1{F_{2^k}} =1+1+\frac13+\frac1{21}+\frac1{987}+\cdots.

它能化成一个简单的代数数。先由加法公式得到

F_{2n}=F_n(F_{n+1}+F_{n-1}),\qquad F_{2n+1}=F_{n+1}^2+F_n^2.

加法公式证明

要证：

F_{m+n}=F_mF_{n+1}+F_{m-1}F_n. \tag{1}

固定 $m\ge 1$ ，对 $n$ 归纳。

当 $n=0$ ：

F_mF_1+F_{m-1}F_0=F_m\cdot1+F_{m-1}\cdot0=F_m=F_{m+0}.

当 $n=1$ ：

F_mF_2+F_{m-1}F_1=F_m\cdot1+F_{m-1}\cdot1=F_m+F_{m-1}=F_{m+1}.

所以 $n=0,1$ 时成立。

假设对 $n$ 和 $n-1$ 成立，即

F_{m+n}=F_mF_{n+1}+F_{m-1}F_n,

F_{m+n-1}=F_mF_n+F_{m-1}F_{n-1}.

那么

\begin{aligned} F_{m+n+1} &=F_{m+n}+F_{m+n-1}\\ &=\bigl(F_mF_{n+1}+F_{m-1}F_n\bigr) +\bigl(F_mF_n+F_{m-1}F_{n-1}\bigr)\\ &=F_m(F_{n+1}+F_n)+F_{m-1}(F_n+F_{n-1})\\ &=F_mF_{n+2}+F_{m-1}F_{n+1}. \end{aligned}

这正是公式 (1) 在 $n+1$ 时的形式。因此归纳成立。

所以

\boxed{F_{m+n}=F_mF_{n+1}+F_{m-1}F_n.}

因此

\begin{aligned} r_n-r_{2n} &=\frac{F_{n+1}}{F_n} -\frac{F_{n+1}^2+F_n^2}{F_n(F_{n+1}+F_{n-1})}\\ &=\frac{F_{n+1}F_{n-1}-F_n^2}{F_{2n}}\\ &=\frac{(-1)^n}{F_{2n}}. \end{aligned}

最后一步又使用了 Cassini 恒等式。

当 $k\ge2$ 时，取 $n=2^{k-1}$ ，此时 $n$ 为偶数，得到

\frac1{F_{2^k}}=r_{2^{k-1}}-r_{2^k}.

所以，对 $K\ge1$ ，

\begin{aligned} \sum_{k=0}^{K}\frac1{F_{2^k}} &=\frac1{F_1}+\frac1{F_2} +\sum_{k=2}^{K}\bigl(r_{2^{k-1}}-r_{2^k}\bigr)\\ &=2+r_2-r_{2^K}\\ &=4-r_{2^K}. \end{aligned}

取极限，便有

\boxed{ \sum_{k=0}^{\infty}\frac1{F_{2^k}} =4-\varphi =\frac{7-\sqrt5}{2} =2.381966011250105\ldots }.

黄金分割与连分数#

令

r_n=\frac{F_{n+1}}{F_n}.

由通项公式可得一个精确的误差式：

\begin{aligned} F_{n+1}-\varphi F_n &=\frac{\varphi^{n+1}-\psi^{n+1}-\varphi(\varphi^n-\psi^n)}{\sqrt5}\\ &=\frac{\psi^n(\varphi-\psi)}{\sqrt5} =\psi^n. \end{aligned}

所以

\boxed{ r_n-\varphi=\frac{\psi^n}{F_n} =\frac{(-1)^n}{\varphi^nF_n} }.

因为右边趋于 $0$ ，便有

\boxed{\frac{F_{n+1}}{F_n}\longrightarrow\varphi}.

同时可以看出：奇数下标的 $r_n$ 小于 $\varphi$ ，偶数下标的 $r_n$ 大于 $\varphi$ ，并且

|r_n-\varphi|\sim\sqrt5\,\varphi^{-2n}.

连分数简介

一个连分数通常写成

x=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cdots}}}

简记为

x=[a_0;a_1,a_2,a_3,\dots]

其中 $a_0$ 可以是整数，后面通常要求 $a_1,a_2,\dots$ 是正整数。这种叫简单连分数。

例如：

\frac{43}{19}=2+\frac{5}{19} =2+\cfrac{1}{3+\cfrac{1}{1+\cfrac{1}{4}}} =[2;3,1,4]

有理数的连分数是有限的

任何有理数都能用欧几里得算法展开成有限连分数。

比如 $\frac{43}{19}$ ：

43=2\cdot 19+5

19=3\cdot 5+4

5=1\cdot 4+1

4=4\cdot 1+0

取商：

[2;3,1,4]

反过来，有限连分数一定是有理数。

无理数给出无限连分数

一些经典例子：

\sqrt2=[1;2,2,2,\dots]

\varphi=\frac{1+\sqrt5}{2}=[1;1,1,1,\dots]

\pi=[3;7,15,1,292,1,\dots]

黄金比例 $\varphi$ 的连分数全是 1，所以它在一定意义下是“最难被有理数逼近”的数之一。

收敛子：连分数的近似值

把连分数截断，得到

\frac{p_n}{q_n}=[a_0;a_1,\dots,a_n]

叫第 $n$ 个收敛子。它们会交替地从两边逼近原数。

例如 $\pi=[3;7,15,1,292,\dots]$ 的前几个收敛子是：

3,\quad \frac{22}{7},\quad \frac{333}{106},\quad \frac{355}{113},\dots

其中 $22/7$ 和 $355/113$ 都是很有名的 $\pi$ 近似。

收敛子可以用递推公式快速计算：

p_n=a_np_{n-1}+p_{n-2}

q_n=a_nq_{n-1}+q_{n-2}

初值常取

p_{-2}=0,\quad p_{-1}=1,\quad q_{-2}=1,\quad q_{-1}=0

递推关系给出

r_{n+1}=\frac{F_{n+1}}{F_{n}}=1+\frac1{r_n},\qquad r_1=1.

因而

r_1=1,\quad r_2=2,\quad r_3=\frac32,\quad r_4=\frac53,\quad r_5=\frac85,\ldots

每次都在已有表达式外面加一层 $1+1/(\cdot)$ ，所以

r_n=[\underbrace{1;1,\ldots,1}_{n\text{ 个 }1}].

取极限得到

\boxed{\varphi=[1;1,1,1,\ldots]}.

从方程上也能验证：它的值 $x>0$ 满足 $x=1+1/x$ ，即 $x^2-x-1=0$ ，故 $x=\varphi$ 。

所以可以得到斐波那契数比值、 $\varphi$ 、连分数的关系

n\to \infty, \frac{F_{n+1}}{F_{n}}=\varphi=\frac{1+\sqrt{ 5 }}{2} =1+\frac{1}{1+\frac{1}{1+...} }=[1;1,1,\dots]

gcd#

先证明相邻项互质

相邻项互质

对任意整数 $a,b$ ，有

\gcd(a+b,a)=\gcd(a,b).

若 $d \mid a$ 且 $d\mid b$ 易得 $d\mid xa+yb$ 即 $a,b$ 的线性组合，则 $d\mid a+b,d\mid b\to d\mid1\cdot(a+b)+(-1)\cdot b\to d\mid b$

所以：

\gcd(F_n,F_{n+1}) =\gcd(F_n,F_n+F_{n-1}) =\gcd(F_n,F_{n-1}) =1.

由递推关系，

\gcd(F_n,F_{n-1}) =\gcd(F_{n-1},F_{n-2}) =\cdots=\gcd(F_1,F_0)=1.

对于上面有说到的加法公式：

$F_{m+n}=F_mF_{n+1}+F_{m-1}F_n$ ，代入 $m'=n,n'=m-n$

F_m=F_nF_{m-n+1}+F_{n-1}F_{m-n}.

根据上方的引理，因而

\begin{aligned} \gcd(F_m,F_n) &=\gcd(F_{n-1}F_{m-n},F_n)\\ &=\gcd(F_{m-n},F_n). \end{aligned}

于是，每把下标对 $(m,n)$ 换成 $(m-n,n)$ ，对应斐波那契数的最大公因数都保持不变。不断执行「欧几里得算法」，最终下标变成 $(d,0)$ ，其中 $d=\gcd(m,n)$ 。因此

\boxed{\gcd(F_m,F_n)=F_{\gcd(m,n)}}.

特别地，如果 $m\mid n$ ，那么

\boxed{F_m\mid F_n}.

所以下标之间的整除关系，会传递给对应的斐波那契数。

Zeckendorf 表示#

使用 $F_2,F_3,F_4,\ldots=1,2,3,5,\ldots$ ，每项最多使用一次，并要求使用的下标互不相邻。结论是：

每个正整数都有且只有一种这样的表示。

例如

100=89+8+3=F_{11}+F_6+F_4.

证明存在性

对正整数 $M$ ，选不超过它的最大斐波那契数 $F_k$ ，即

F_k\le M<F_{k+1}.

减去 $F_k$ 后，余数满足

0\le M-F_k<F_{k+1}-F_k=F_{k-1}.

所以下一个选中的数至多是 $F_{k-2}$ ，自然不会与 $F_k$ 相邻。对余数重复这一过程，每次余数都减小，最终到达 $0$ ，得到所需表示。

证明唯一性

令 $A_k$ 表示从 $F_2,\ldots,F_k$ 中选取互不相邻项，所能得到的最大和。根据是否选 $F_k$ ，

A_k=\max\{A_{k-1},\ F_k+A_{k-2}\}.

从 $A_1=0$ 、 $A_2=1$ 出发，归纳得到

\boxed{A_k=F_{k+1}-1}.

假设同一个整数有两个不同的合法表示，消去共同项，设最大的不同下标为 $k$ 。其中一个表示包含 $F_k$ ，其剩余总和至少为 $F_k$ ；另一个表示只能使用下标不超过 $k-1$ 的项，其总和至多为

A_{k-1}=F_k-1.

两边无法相等，矛盾。因此表示唯一。

较小的、不相邻的斐波那契数，即使全部按最大可能方式相加，也达不到下一个斐波那契数。这正是唯一性证明的关键。

一个简单的局部规则，经过不断重复之后，可以形成远比规则本身丰富的整体结构。同一个结构可以在不同问题中被重新发现