斐波那契数列初探

定义

一些小性质

一些 simple 的运算

运算 1

证明：拆开算就可以了

运算2

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

运算3

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

运算4

证明：
首先验证小范围的 k 发现是正确的。
那么我们设 是正确的，现在尝试证明 是正确的。

一些正常的小性质

性质 1

证明：考虑辗转相减法：

性质 2

我们首先证明从左到右：
我们将 表示为 ，现在需要证明
考虑 的情形：

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

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

引理 1：$$

证明：我们不妨设 ，则 。

所以有 $$

即

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

注意到 ，所以可以得

观察下标由 ，实质是在对下标辗转相减，也就是求下标的 gcd。
现在我们来考虑证明命题

因为整除所以可以得到

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

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

证明：
我们考虑 ，观察什么时候有 。
首先可以知道的是 ，这并不是零。
注意到有 ，所以

类似地，我们对于 还有

通过对于 和 的计算使我们可以计算 和 ：

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

因为 ，所以

说明存在这样的 ，证毕。

斐波那契数系

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

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

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

求斐波那契数列的通项式

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

观察如下级数的系数特点：

于是我们可以发现

可以解出来一个关于 的更紧凑的公式

显然大家都知道生成函数为 表示的序列是 ，考虑尽量表示成类似于这样的形式，这样就能求出一个关于系数的通项公式了。

我们可以将分母的式子 因式分解，变成 。
运用初中知识容易解得：

哎是不是十分像 的形式了？我们考虑把这玩意拆开

为了确定 的值，我们需要解方程

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

这样就列个方程组？

我们写个高斯消元跑一下用计算器算了一下，发现解为

代入 可以得到

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

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