第零篇 数列递推

PartⅠ 一阶常系数线性齐次递推

​ 若数列{an}\{a_n\}满足以下形式：

an+1=pan+q(p≠0)a_{n+1}=pa_n+q\quad(p\neq0)

​ 其中p、qp、q为给定的实数，数列首项为a1a_1。

​ 称这个数列满足一阶常系数线性齐次递推的形式。

​ 这种数列的通项公式很容易求，可以分成两种情况：

​ 1. 若p=1p=1，则an+1=an+qa_{n+1}=a_{n}+q，此时数列为一个公差为qq的等差数列，容易推得：

an=a1+(n−1)qa_n=a_1+(n-1)q

​ 2. 若p≠1p\neq1，则可以通过 待定系数法 来构造等比数列：假设存在一个系数AA，使得an+1=pan+qa_{n+1}=pa_n+q可以写成an+1−A=p(an−A)a_{n+1}-A=p(a_n-A)的形式，这样做的目的是为了转换成一个等比数列的形式，之后就可以进行递推来求解数列通项。

​ 将an+1−A=p(an−A)a_{n+1}-A=p(a_n-A)展开：an+1=pan+(1−p)Aa_{n+1}=pa_n+(1-p)A与an+1=pan+qa_{n+1}=pa_n+q对比，解出系数A=q1−pA=\dfrac{q}{1-p}。

​ 所以{an+1−q1−p}\left\{a_{n+1}-\dfrac{q}{1-p}\right\}是首项为a1−q1−pa_1-\dfrac{q}{1-p}，公比为qq的等比数列，由等比数列递推公式(累乘)：

an=anan−1×an−1an−2×⋯×a2a1×a1a_n=\dfrac{a_n}{a_{n-1}}\times\dfrac{a_{n-1}}{a_{n-2}}\times\cdots\times\dfrac{a_2}{a_{1}}\times{a_1}

​ 可以推出：an−q1−p=(a1−q1−p)qn−1a_n-\dfrac{q}{1-p}=\left(a_1-\dfrac{q}{1-p}\right)q^{n-1}，进而求得：

an=(a1−q1−p)pn−1+q1−pa_n=\left(a_1-\dfrac{q}{1-p}\right)p^{n-1}+\dfrac{q}{1-p}

PartⅡ 二阶常系数线性齐次递推

​ 若数列{xn}\{x_n\}满足以下形式：

xn+1=pxn+qxn−1(p、q≠0)x_{n+1}=px_{n}+qx_{n-1}\quad(p、q\neq0)

​ 其中p、qp、q为给定的实数，数列第一项和第二项分别为x1x_1和x2x_2。

​ 称这个数列满足二阶常系数线性齐次递推的形式。

​ 类比于一阶递推形式中构造等比数列的方法，我们还是尝试待定系数法构造这样的等比数列：

​ 假设存在实数a、ba、b，使得xn+1=pxn+qxn−1x_{n+1}=px_{n}+qx_{n-1}可以写成xn+1−axn=b(xn−axn−1)x_{n+1}-ax_{n}=b(x_{n}-ax_{n-1})，整理一下：xn+1=(a+b)xn−abxn−1x_{n+1}=(a+b)x_{n}-abx_{n-1}，对比系数有：

\left\{ \begin{array}{2} a+b=p \\ ab=-q \end{array} \right.

​ 这个形式就非常像初中学过的一元二次方程，实数a、ba、b是方程x2−px−q=0x^2-px-q=0的解。

​ 1.方程解不相等(a≠b)(a\neq b)时：

​ 所以{xn+1−axn}\{x_{n+1}-ax_n\}是公比为bb的等比数列，由累乘得到：xn+1−axn=(x2−ax1)bn−1x_{n+1}-ax_n=(x_2-ax_1)b^{n-1}

​ xn+1−axn=b(xn−axn−1)x_{n+1}-ax_{n}=b(x_{n}-ax_{n-1})还可以写成xn+1−bxn=a(xn−bxn−1)x_{n+1}-bx_{n}=a(x_{n}-bx_{n-1})的形式，因此{xn+1−bxn}\{x_{n+1}-bx_n\}是公比为aa的等比数列，累乘得到：xn+1−bxn=(x2−bx1)an−1x_{n+1}-bx_n=(x_2-bx_1)a^{n-1}

​ 将累乘得到的两个式子相减有：

xn=x2−bx1a−b⋅an−1+x2−ax1b−a⋅bn−1x_n=\dfrac{x_2-bx_1}{a-b}\cdot a^{n-1}+\dfrac{x_2-ax_1}{b-a}\cdot b^{n-1}

​ 为了便于记忆，我们令\left\{\begin{array}{2} \alpha=\dfrac{x_2-bx_1}{a-b}\cdot\dfrac{1}{a}\\ \beta=\dfrac{x_2-ax_1}{b-a}\cdot\dfrac{1}{b}\end{array}\right.，所以xn=α⋅an+β⋅bnx_n = \alpha \cdot a^{n}+\beta\cdot b^{n}。

​ 解题时只需要根据数列{xn}\{x_n\}的递推公式写出相应的特征方程，得到解a、ba、b，再根据x1、x2x_1、x_2待定系数求解出α、β\alpha、\beta即可得到该数列通项公式。下面是一个例子：

​ FibonacciFibonacci数列是大家非常熟悉的一个数列，它满足这样的条件：a1=a2=1a_1=a_2=1，an+1=an+an−1a_{n+1}=a_n+a_{n-1}，求FibonacciFibonacci数列的通项公式。

​ 由递推关系式：an+1=an+an−1a_{n+1}=a_n+a_{n-1}得到特征方程：x2−x−1=0x^2-x-1=0。

​ 这个方程的解为：a=5+12a=\dfrac{\sqrt5+1}{2}，b=−5+12b=\dfrac{-\sqrt5+1}{2}

​ 所以他的通项公式可以写成：xn=α⋅(5+12)n−1+β⋅(−5+12)n−1x_n = \alpha \cdot \left( \dfrac{\sqrt{5}+1}{2} \right)^{n-1} + \beta \cdot \left( \dfrac{-\sqrt{5}+1}{2} \right)^{n-1}

​ 代入a1=a2=1a_1=a_2=1，解出α=15\alpha=\dfrac{1}{\sqrt5}，β=−15\beta=-\dfrac{1}{\sqrt5}。

​ 所以FibonacciFibonacci数列的通项为：$ x_n = \dfrac{1}{\sqrt{5}}\left[ \left( \dfrac{\sqrt{5}+1}{2} \right)^{n-1} - \left( \dfrac{-\sqrt{5}+1}{2} \right)^{n-1} \right]$

​

​ 2.方程解相等(a=b)(a=b)时：

​ xn+1=pxn+qxn−1x_{n+1}=px_{n}+qx_{n-1}可以写成xn+1−bxn=b(xn−bxn−1)x_{n+1}-bx_{n}=b(x_{n}-bx_{n-1})，对{xn+1−bxn}\{x_{n+1}-bx_n\}​这个数列进行累乘得：

xn+1−bxn=bn−1(x2−bx1)x_{n+1}-bx_n=b^{n-1}(x_2-bx_1)

​ 两边同时除以bn+1b^{n+1}有：

​

xn+1bn+1−xnbn=x2b2−x1b\dfrac{x_{n+1}}{b^{n+1}}-\dfrac{x_{n}}{b^{n}}=\dfrac{x_{2}}{b^2}-\dfrac{x_1}{b}

​ 这说明数列{xnbn}\left\{\dfrac{x_{n}}{b^{n}}\right\}是一个等差数列，公差为x2b2−x1b\dfrac{x_{2}}{b^2}-\dfrac{x_1}{b}。

​ 由此可以求得：xnbn=(n−1)(x2b2−x1b)+x1b\dfrac{x_{n}}{b^{n}}=(n-1)\left(\dfrac{x_{2}}{b^{2}}-\dfrac{x_{1}}{b}\right)+\dfrac{x_{1}}{b}，

​ 所以：xn=x1⋅bn−1+(x2−bx1)(n−1)⋅bn−2x_n=x_1 \cdot b^{n-1}+(x_2-bx_1)(n-1)\cdot b^{n-2}，

​ 整理一下，xn=[(x1b−x2b2+1b)+(−x1b+−x2b2)n]bnx_n=\left[\left(\dfrac{x_{1}}{b}-\dfrac{x_{2}}{b^2}+\dfrac{1}{b}\right)+\left(\dfrac{-x_{1}}{b}+\dfrac{-x_{2}}{b^2}\right)n\right]b^n。

​ 同理我们可以令\left\{\begin{array}{2} \alpha=\dfrac{x_{1}}{b}-\dfrac{x_{2}}{b^2}+\dfrac{1}{b}\\ \beta=\dfrac{-x_{1}}{b}+\dfrac{-x_{2}}{b^2}\end{array}\right.，所以xn=(α+βn)⋅bnx_n=(\alpha+\beta n)\cdot b^n。

​ 解题时只需要待定系数求出α、β\alpha、\beta即可得到通项公式。

PartⅢ 从递推到矩阵

​ 上面都是低阶的问题，如果碰到更高阶的常系数线性齐次递推式子呢？由于是预备知识，在这里不详述，可以先看下面这一篇知乎上的文章↓：

​ 二阶常系数齐次线性递推数列 - 知乎 (zhihu.com)

​