RainAir

学习笔记斐波那契数列初探

学习笔记

题解(9)

/ 注册

斐波那契数列初探

815 浏览 0 回复 2020-02-28

RainAir

+关注

定义

$F_n = \begin{cases} 0 & n = 0 \\\ 1 & n = 1 \\\ F_{n-1}+F_{n-2} & otherwise \end{cases}$

一些小性质

一些 simple 的运算

运算 1

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

证明：拆开算就可以了

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

运算2

$F_{n+1}F_{n-1}-F_n^2 = (-1)^n$

证明：数学归纳法一下就可以了。
咕咕咕~

运算3

我们如果把斐波那契数列扩展到负数，那么有公式

$F_{-n} = (-1)^{n-1}F_n$

运算4

$F_{n+k} = F_{n+1}F_k + F_nF_{k-1}$

证明：
首先验证小范围的 k 发现是正确的。
那么我们设 $\forall k \in [1,i-1]$ 是正确的，现在尝试证明 $k=i$ 是正确的。

$图片说明$

一些正常的小性质

性质 1

$gcd(F_i,F_{i-1}) = 1(i>1)$

证明：考虑辗转相减法：

$gcd(F_i,F_{i-1}) = gcd(F_{i-1},F_i-F_{i-1}) = \cdots = gcd(1,0) = 1$

性质 2

$n | m \Leftrightarrow F_n | F_m$

我们首先证明从左到右：
我们将 $m$ 表示为 $kn$ ，现在需要证明 $F_n | F_{kn}$
考虑 $k=2$ 的情形：

$F_{2n} = F_{n+n} = F_{n+1}F_n + F_{n}F_{n-1} \Rightarrow F_{n} | F_{2n}$

同理：当 $k=3$ 的时候，借助上面的结论，显然也有

$F_{3n} = F_{n+2n} = F_{n+1}F_{2n}+F_{n}F_{2n-1} \Rightarrow F_{n} | F_{3n}$

归纳证明命题正确。
现在我们证明从右到左，首先我们来观察一个引理：

引理 1：$ $gcd(F_m,F_n) = F_{gcd(m,n)}$ $

证明：我们不妨设 $m>n$ ，则 $m = n+(m-n)$ 。

所以有 $ $F_m = F_{n+(m-n)} = F_{n+1}F_{m-n}+F_{n}F_{m-n-1}$ $

即

$gcd(F_m,F_n) = gcd(F_{n+1}F_{m-n}+F_{n}F_{m-n-1},F_n)$

显然经过数次辗转相减后会变成：

$gcd(F_{n+1}F_{m-n},F_n)$

注意到 $gcd(F_{n+1},F_n) = 1$ ，所以可以得

$gcd(F_{n},F_{m-n})$

观察下标由 $(m,n) \to (n,m-n)$ ，实质是在对下标辗转相减，也就是求下标的 gcd。
现在我们来考虑证明命题

$F_n | F_m \Rightarrow n|m$

因为整除所以可以得到

$F_n | gcd(F_n,F_m) \Rightarrow F_n | F_{gcd(n,m)}$

注意到满足条件的 $gcd(n,m)$ 的最小值是 $n$ ,所以我们就证明了上述命题。

性质三（马蒂亚舍维奇引理）

$F_n^2 | F_m \Leftrightarrow nF_n | m$

证明：
我们考虑 $\forall k \in N^*$ ，观察什么时候有 $F_{kn} \mod F_n^2 = 0$ 。
首先可以知道的是 $F_n \mod F_{n}^2 = F_n$ ，这并不是零。
注意到有 $F_{n+1} \equiv F_{n-1} (\mod F_i)$ ，所以

$F_{2n} = F_nF_{n+1}+F_nF_{n-1}\equiv 2F_nF_{n+1}(\mod F_n^2)$

类似地，我们对于 $2n+1$ 还有

$F_{2n+1} = F_{n+1}^2 + F_{n}^2 \equiv F_{n+1}^2 (\mod F_n^2)$

通过对于 $2n$ 和 $2n+1$ 的计算使我们可以计算 $3n$ 和 $3n+1$ ：
$图片说明$

仿照上面的过程，对 $k$ 用数学归纳法，可以得到规律：

$F_{kn} \equiv kF_nF_{n+1}^{k-1} \text{和} F_{kn+1} \equiv F_{n+1}^k (\mod F_n^2)$

因为 $gcd(F_n,F_{n+1}) = 1$ ，所以
$图片说明$
说明存在这样的 $k$ ，证毕。

斐波那契数系

我们考虑用斐波那契数来表示任意的数，记

$j >> k \Leftrightarrow j\geq k+2$

那么每个正整数有唯一的表示形式

$n = \sum_{0 \leq i \leq r} F_{k_i},\text{满足} k_1 >> k_2 >> \cdots >> k_r >> 0$

显然我们可以用贪心构造这样的一组解，并且这组解是唯一的。证明留给读者自己思考。
这样斐波那契数系的定义就出来了：

$n = (b_m, b_{m-1} \cdots b_2 )_ F \Leftrightarrow \sum_{k=2}^m b_k F_k$

求斐波那契数列的通项式

当然是直接生成函数
我们考虑无穷级数

$F(z) = \sum_{n\geq0} f_nz^n$

观察如下级数的系数特点：
$图片说明$
于是我们可以发现

$F(z) - zF(z) - z^2F(z) = 1$

可以解出来一个关于 $F(z)$ 的更紧凑的公式

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

显然大家都知道生成函数为 $\frac{1}{1-x}$ 表示的序列是 $\sum_{i \geq 0} x^i$ ，考虑尽量表示成类似于这样的形式，这样就能求出一个关于系数的通项公式了。

我们可以将分母的式子 $1-z-z^2$ 因式分解，变成 $(1-\phi z)(1- \hat{\phi} z)$ 。
运用初中知识容易解得：
$图片说明$

哎是不是十分像 $\frac{1}{1-kx}$ 的形式了？我们考虑把这玩意拆开

$\frac{a}{(1-\phi z)} + \frac{b}{(1-\hat{\phi} z)}$

为了确定 $a,b$ 的值，我们需要解方程

$a(1-\hat{\phi}z) + b(1-\phi z) = 1$

考虑首先将其看成关于 $z$ 的方程，变形可得：

$(a+b-1)-z(a\hat{\phi} + b \phi ) = 0$

这样就列个方程组？
$图片说明$
我们~~写个高斯消元跑一下~~用计算器算了一下，发现解为
$图片说明$
代入 $F$ 可以得到

$F = \frac{\phi}{\sqrt{5}}\frac{1}{(1-\phi z)} - \frac{\hat{\phi}}{\sqrt{5}}\frac{1}{(1-\hat{\phi}z)}$

那么运用知识略作整理就可以达到通项公式啦：

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

其实更像是具体数学学习笔记（雾

斐波那契数列

举报

收藏

赞

评论加载中...