1-前言

        2021年5月20号的那天，有对象的都忙着约会秀恩爱，而我这样的单身狗，只能自己学习沉淀自己，为梦想而奔波，仿佛是在向世界宣布，520与我无关。这不，那天我在写一篇关于时间复杂度的博客，其中递归的时候遇到了一个数列：1, 1, 3, 5, 9, 15, 25, 41, 67，我想着求出第n项的通项公式，于是当晚发了朋友圈向圈内的朋友么请教一下，521那天也连续发了3条，而且是有偿。

        但是大多数的人都只能得出这个结论：
$$f(n+2)=f(n+1)+f(n)+1，n\in N^{\ast }，n\ge 3$$
        也就是从从第3项开始，每一项都是前2项之和，再加上1，也许是大家那天都很忙，也许是大家都没有头绪证明，对此，我还是决定写篇博客，把这个通项公式求出来，分享到朋友圈，一个是记录自己的成长，一个是也让不会并且很感兴趣的人去了解，朋友圈本就是记录分享一些情绪，有趣，感人，美好与学术知识的圣地。

2-斐波那契

2-1-什么是斐波那契

        记得小学的时候数学课本上有过一个兔子的故事，简单来说就是一对小兔子（一公一母）一个月后长成一对大兔子，大兔子接下来下个月能生下一对小兔子（也是一公一母），第三个月原本的大兔子再生一对，同时那对小兔子长大了，第四个月……
把上面的故事里的每个月的（包括第一个月）兔子对数写下来便得到了一个数列：
$$1，1，2，3，5，8，13，21...$$
        这其中的规律很明显：
$$a_1=a_2=1$$$$a_{n+2}=a_{n+1}+a_n$$
        这样的一个数列{an}就是著名的斐波那契数列。

        但问题在于这仅仅是它的递推公式，而且还有三个递推变量，怎么看都不爽。这时候就不禁让人想研究它的通项公式了。不急，一步一步来看它通项公式到底长什么样。

2-2-通项公式的证明

        要解决一道数列的题目，三个递推变量怎么看都不顺眼，第一想法看看能不能干掉一个变量。简而言之，就是把两个变量看作一个整体，看看有没有相邻变量之间的关系。

        首先是这个式子：

1式：$a_{n+2}=a_{n+1}+a_n$

        我们把它定为1式，试一试能不能把 $a_{n+1}$ 拆成两部分给等式两边构成一个形如这样的式子：

2式：$a_{n+2}+\lambda a_{n+1}=\upsilon (a_{n+1}+\lambda a_n)$

        这样 {$a_{n+1}+\lambda a_n$}这个数列就应该满足一种等比数列的性质，也就是公比为$\upsilon$等比数列。其中每一项为：
$$a_{n+1}+\lambda a_n，当n=1时，首项为a_2+\lambda a_1$$
        由于 $a_1=a_2=1$得到首项应为：

$首项：(1+\lambda )$

        我们把2式展开：
$$a_{n+2}+\lambda a_{n+1}=\upsilon (a_{n+1}+\lambda a_n)$$
        展开$$a_{n+2}+\lambda a_{n+1}=\upsilon a_{n+1}+\upsilon \lambda a_n$$        合并同类项：$$a_{n+2}=(\upsilon -\lambda )a_{n+1}+\upsilon \lambda a_n$$
        与1式相比：$$a_{n+2}=a_{n+1}+a_n$$
        可知：$$\{\begin{array}{l}\upsilon -\lambda =1\\ \upsilon \lambda =1\end{array}$$        得：$$\upsilon =\lambda +1$$
        将$\upsilon =\lambda +1$带入2式，可得：$$a_{n+2}+\lambda a_{n+1}=(\lambda +1)(a_{n+1}+\lambda a_n)$$
        展开，合并同类项：

3式：$a_{n+2}=a_{n+1}+({\lambda }^2+\lambda )a_n$

        与1式相比：$$a_{n+2}=a_{n+1}+a_n$$
        可知：$${\lambda }^2+\lambda =1$$
        那么现在问题就是看看存不存在这个实数 λ，如果有再想办法把它解出来。$${\lambda }^2+\lambda =1$$$${\lambda }^2+\lambda +\frac{1}{4}=\frac{5}{4}$$$$(\lambda +\frac{1}{2}{)}^2=\frac{5}{4}$$$$\{\begin{array}{l}\lambda +\frac{1}{2}=\sqrt[2]{\frac{5}{4}}=\frac{\sqrt[2]{5}}{2}\\ \lambda +\frac{1}{2}=-\sqrt[2]{\frac{5}{4}}=-\frac{\sqrt[2]{5}}{2}\end{array}$$        得出解：$$\{\begin{array}{l}{\lambda }_1=\frac{\sqrt[2]{5}-1}{2}\\ \\ {\lambda }_2=\frac{-\sqrt[2]{5}-1}{2}\end{array}$$
        由等比数列的性质：设等比数列的首项为a1，公比为q，则：$$a_k=a_1\cdot q^{k-1}$$
        {$a_{n+1}+\lambda a_n$}是等比数列，则有：$$a_{n+1}+\lambda a_n=(a_2+\lambda a_1){\upsilon }^{n-1}$$
        首项$(a_2+\lambda a_1)=(1+\lambda )$，公比$\upsilon =\lambda +1$，有：$$a_{n+1}+\lambda a_n=(1+\lambda )(\lambda +1{)}^{n-1}$$
        有：

4式：$a_{n+1}+\lambda a_n=(\lambda +1{)}^n$

        现将第1个解${\lambda }_1=\frac{\sqrt[2]{5}-1}{2}$代入4式后得到：

5式：$a_{n+1}+\frac{\sqrt[2]{5}-1}{2}{a}_n=(\frac{\sqrt[2]{5}+1}{2}{)}^n$

        再将第2个解${\lambda }_2=\frac{-\sqrt[2]{5}-1}{2}$代入4式后得到：

6式：$a_{n+1}+\frac{-\sqrt[2]{5}-1}{2}{a}_n=(\frac{1-\sqrt[2]{5}}{2}{)}^n$

        若要得到 $a_n$ 的通项公式只需5式减去6式，得到：
$$\frac{\sqrt[2]{5}-1}{2}{a}_n-\frac{-\sqrt[2]{5}-1}{2}{a}_n=(\frac{\sqrt[2]{5}+1}{2}{)}^n-(\frac{1-\sqrt[2]{5}}{2}{)}^n$$$$\frac{2\sqrt[2]{5}}{2}{a}_n=(\frac{1+\sqrt[2]{5}}{2}{)}^n-(\frac{1-\sqrt[2]{5}}{2}{)}^n$$$$\sqrt[2]{5}{a}_n=(\frac{1+\sqrt[2]{5}}{2}{)}^n-(\frac{1-\sqrt[2]{5}}{2}{)}^n$$
        可得通项公式为：
$$a_n=\frac{1}{\sqrt[2]{5}}[(\frac{1+\sqrt[2]{5}}{2}{)}^n-(\frac{1-\sqrt[2]{5}}{2}{)}^n]$$
        其线性分布为：

2-3-举一反三

        我们回到朋友圈发的那个数列：1, 1, 3, 5, 9, 15, 25, 41, 67，这其中的规律很明显：
$$a_1=a_2=1$$$$a_{n+2}=a_{n+1}+a_n+1，n\in N^{\ast }，n\ge 1$$
        这其实也是斐波那契数列的特殊形式，我们使用上面推导斐波那契通项公式的方式，推导这个的通项公式，原式等号左右2边加1变一下：$$a_{n+2}=a_{n+1}+a_n+1$$        得到：

a式：$a_{n+2}+1=(a_{n+1}+1)+(a_n+1)$

        同样，试一试能不能把 $a_{n+1}+1$ 拆成两部分给等式两边构成一个形如这样的式子：

b式：$a_{n+2}+1+\lambda (a_{n+1}+1)=\upsilon [a_{n+1}+1+\lambda (a_n+1)]$

        这样 {$(a_{n+1}+1)+\lambda (a_n+1)$}这个数列就应该满足一种等比数列的性质，也就是公比为$\upsilon$等比数列。其中每一项为：
$$(a_{n+1}+1)+\lambda (a_n+1)，当n=1时，首项为a_2+1+\lambda (a_1+1)$$
        由于 $a_1=a_2=1$得到首项应为：

$首项：(2+2\lambda )$

        我们把b式展开：
$$a_{n+2}+1+\lambda (a_{n+1}+1)=\upsilon [a_{n+1}+1+\lambda (a_n+1)]$$
        展开$$a_{n+2}+1+\lambda a_{n+1}+\lambda =\upsilon [a_{n+1}+1+\lambda a_n+\lambda ]$$$$a_{n+2}+1+\lambda a_{n+1}+\lambda =\upsilon a_{n+1}+\upsilon +\upsilon \lambda a_n+\upsilon \lambda$$        合并同类项：$$a_{n+2}=(\upsilon -\lambda )a_{n+1}+\upsilon \lambda a_n+\upsilon \lambda +\upsilon -\lambda -1$$
        与原式相比：$$a_{n+2}=a_{n+1}+a_n+1$$
        可知：$$\{\begin{array}{l}①\upsilon -\lambda =1\\ ②\upsilon \lambda =1\\ ③\upsilon \lambda +\upsilon -\lambda -1=1\end{array}$$
        由①式和②式，带入③式，可见③也符合结果，且从①可得$$\upsilon =\lambda +1$$
        将$\upsilon =\lambda +1$带入b式，可得：$$a_{n+2}+1+\lambda (a_{n+1}+1)=(\lambda +1)[a_{n+1}+1+\lambda (a_n+1)]$$
        展开，合并同类项，可得：

c式：$a_{n+2}=a_{n+1}+({\lambda }^2+\lambda )a_n+({\lambda }^2+\lambda )$

        与1原式相比：$$a_{n+2}=a_{n+1}+a_n+1$$
        可知：$${\lambda }^2+\lambda =1$$
        同样得出解：$$\{\begin{array}{l}{\lambda }_1=\frac{\sqrt[2]{5}-1}{2}\\ \\ {\lambda }_2=\frac{-\sqrt[2]{5}-1}{2}\end{array}$$
        由等比数列的性质：设等比数列的首项为a1，公比为q，则：$$a_k=a_1\cdot q^{k-1}$$
        {$(a_{n+1}+1)+\lambda (a_n+1)$}是等比数列，则有：$$a_{n+1}+1+\lambda (a_n+1)=(a_2+1+\lambda (a_1+1)){\upsilon }^{n-1}$$
        首项$(a_2+1+\lambda (a_1+1))=(2+2\lambda )$，公比$\upsilon =\lambda +1$，有：
$$a_{n+1}+1+\lambda (a_n+1)=(2+2\lambda )(\lambda +1{)}^{n-1}$$$$a_{n+1}+\lambda a_n+\lambda +1=2(1+\lambda )(\lambda +1{)}^{n-1}$$
        有：

d式：$a_{n+1}+\lambda a_n=2(\lambda +1{)}^n-\lambda -1$

        现将第1个解${\lambda }_1=\frac{\sqrt[2]{5}-1}{2}$代入d式后得到：

e式：$a_{n+1}+\frac{\sqrt[2]{5}-1}{2}{a}_n=2(\frac{\sqrt[2]{5}-1}{2}+1{)}^n-\frac{\sqrt[2]{5}-1}{2}-1$

        再将第2个解${\lambda }_2=\frac{-\sqrt[2]{5}-1}{2}$代入d式后得到：

f式：$a_{n+1}+\frac{-\sqrt[2]{5}-1}{2}{a}_n=2(\frac{-\sqrt[2]{5}-1}{2}+1{)}^n-\frac{-\sqrt[2]{5}-1}{2}-1$

        若要得到 $a_n$ 的通项公式只需e式减去f式，得到：$$a_{n+1}+\frac{\sqrt[2]{5}-1}{2}{a}_n=2(\frac{\sqrt[2]{5}-1}{2}+1{)}^n-\frac{\sqrt[2]{5}-1}{2}-1$$$$-$$$$a_{n+1}+\frac{-\sqrt[2]{5}-1}{2}{a}_n=2(\frac{-\sqrt[2]{5}-1}{2}+1{)}^n-\frac{-\sqrt[2]{5}-1}{2}-1$$$$=$$$$\sqrt[2]{5}{a}_n=2(\frac{\sqrt[2]{5}-1}{2}+1{)}^n-\frac{\sqrt[2]{5}-1}{2}-(2(\frac{-\sqrt[2]{5}-1}{2}+1{)}^n-\frac{-\sqrt[2]{5}-1}{2})$$$$\sqrt[2]{5}{a}_n=2(\frac{\sqrt[2]{5}-1}{2}+1{)}^n-2(\frac{-\sqrt[2]{5}-1}{2}+1{)}^n-\frac{\sqrt[2]{5}-1}{2}+\frac{-\sqrt[2]{5}-1}{2}$$$$\sqrt[2]{5}{a}_n=2(\frac{\sqrt[2]{5}-1}{2}+1{)}^n-2(\frac{-\sqrt[2]{5}-1}{2}+1{)}^n-\sqrt[2]{5}$$$$\sqrt[2]{5}{a}_n=2[(1+\frac{\sqrt[2]{5}-1}{2}{)}^n-(1-\frac{\sqrt[2]{5}+1}{2}{)}^n]-\sqrt[2]{5}$$$$\sqrt[2]{5}{a}_n=2[(\frac{1+\sqrt[2]{5}}{2}{)}^n-(\frac{1-\sqrt[2]{5}}{2}{)}^n]-\sqrt[2]{5}$$
        可得通项公式为：
$$a_n=\frac{2}{\sqrt[2]{5}}[(\frac{1+\sqrt[2]{5}}{2}{)}^n-(\frac{1-\sqrt[2]{5}}{2}{)}^n]-1$$
        其线性分布为：

        完结撒花