第零篇 数列递推
第零篇 数列递推
PartⅠ 一阶常系数线性齐次递推
若数列\(\{a_n\}\)满足以下形式： \[ a_{n+1}=pa_n+q\quad(p\neq0) \] 其中\(p、q\)为给定的实数，数列首项为\(a_1\)。
称这个数列满足一阶常系数线性齐次递推的形式。
这种数列的通项公式很容易求，可以分成两种情况：
1. 若\(p=1\)，则\(a_{n+1}=a_{n}+q\)，此时数列为一个公差为\(q\)的等差数列，容易推得： \[
a_n=a_1+(n-1)q
\]
2. 若\(p\neq1\)，则可以通过
待定系数法 来构造等比数列：假设存在一个系数\(A\)，使得\(a_{n+1}=pa_n+q\)可以写成\(a_{n+1}-A=p(a_n-A)\)的形式，这样做的目的是为了转换成一个等比数列的形式，之后就可以进行递推来求解数列通项。
将\(a_{n+1}-A=p(a_n-A)\)展开：\(a_{n+1}=pa_n+(1-p)A\)与\(a_{n+1}=pa_n+q\)对比，解出系数\(A=\dfrac{q}{1-p}\)。
所以\(\left\{a_{n+1}-\dfrac{q}{1-p}\right\}\)是首项为\(a_1-\dfrac{q}{1-p}\)，公比为\(q\)的等比数列，由等比数列递推公式(累乘)： \[ a_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} \] 可以推出：\(a_n-\dfrac{q}{1-p}=\left(a_1-\dfrac{q}{1-p}\right)q^{n-1}\)，进而求得： \[ a_n=\left(a_1-\dfrac{q}{1-p}\right)p^{n-1}+\dfrac{q}{1-p} \]
PartⅡ 二阶常系数线性齐次递推
若数列\(\{x_n\}\)满足以下形式： \[ x_{n+1}=px_{n}+qx_{n-1}\quad(p、q\neq0) \] 其中\(p、q\)为给定的实数，数列第一项和第二项分别为\(x_1\)和\(x_2\)。
称这个数列满足二阶常系数线性齐次递推的形式。
类比于一阶递推形式中构造等比数列的方法，我们还是尝试待定系数法构造这样的等比数列：
假设存在实数\(a、b\)，使得\(x_{n+1}=px_{n}+qx_{n-1}\)可以写成\(x_{n+1}-ax_{n}=b(x_{n}-ax_{n-1})\)，整理一下：\(x_{n+1}=(a+b)x_{n}-abx_{n-1}\)，对比系数有： \[ \left\{ \begin{array}{2} a+b=p \\ ab=-q \end{array} \right. \] 这个形式就非常像初中学过的一元二次方程，实数\(a、b\)是方程\(x^2-px-q=0\)的解。
1.方程解不相等\((a\neq
b)\)时：
所以\(\{x_{n+1}-ax_n\}\)是公比为\(b\)的等比数列，由累乘得到：\(x_{n+1}-ax_n=(x_2-ax_1)b^{n-1}\)
\(x_{n+1}-ax_{n}=b(x_{n}-ax_{n-1})\)还可以写成\(x_{n+1}-bx_{n}=a(x_{n}-bx_{n-1})\)的形式，因此\(\{x_{n+1}-bx_n\}\)是公比为\(a\)的等比数列，累乘得到：\(x_{n+1}-bx_n=(x_2-bx_1)a^{n-1}\)
将累乘得到的两个式子相减有： \[ x_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.\)，所以\(x_n = \alpha \cdot a^{n}+\beta\cdot b^{n}\)。
解题时只需要根据数列\(\{x_n\}\)的递推公式写出相应的特征方程，得到解\(a、b\)，再根据\(x_1、x_2\)待定系数求解出\(\alpha、\beta\)即可得到该数列通项公式。下面是一个例子：
\(Fibonacci\)数列是大家非常熟悉的一个数列，它满足这样的条件：\(a_1=a_2=1\)，\(a_{n+1}=a_n+a_{n-1}\)，求\(Fibonacci\)数列的通项公式。
由递推关系式：\(a_{n+1}=a_n+a_{n-1}\)得到特征方程：\(x^2-x-1=0\)。
这个方程的解为：\(a=\dfrac{\sqrt5+1}{2}\)，\(b=\dfrac{-\sqrt5+1}{2}\)
所以他的通项公式可以写成：\(x_n = \alpha \cdot \left( \dfrac{\sqrt{5}+1}{2} \right)^{n-1} + \beta \cdot \left( \dfrac{-\sqrt{5}+1}{2} \right)^{n-1}\)
代入\(a_1=a_2=1\)，解出\(\alpha=\dfrac{1}{\sqrt5}\)，\(\beta=-\dfrac{1}{\sqrt5}\)。
所以\(Fibonacci\)数列的通项为：$ x_n = $
2.方程解相等\((a=b)\)时：
\(x_{n+1}=px_{n}+qx_{n-1}\)可以写成\(x_{n+1}-bx_{n}=b(x_{n}-bx_{n-1})\)，对\(\{x_{n+1}-bx_n\}\)这个数列进行累乘得： \[ x_{n+1}-bx_n=b^{n-1}(x_2-bx_1) \] 两边同时除以\(b^{n+1}\)有：
\[
\dfrac{x_{n+1}}{b^{n+1}}-\dfrac{x_{n}}{b^{n}}=\dfrac{x_{2}}{b^2}-\dfrac{x_1}{b}
\] 这说明数列\(\left\{\dfrac{x_{n}}{b^{n}}\right\}\)是一个等差数列，公差为\(\dfrac{x_{2}}{b^2}-\dfrac{x_1}{b}\)。
由此可以求得：\(\dfrac{x_{n}}{b^{n}}=(n-1)\left(\dfrac{x_{2}}{b^{2}}-\dfrac{x_{1}}{b}\right)+\dfrac{x_{1}}{b}\)，
所以：\(x_n=x_1 \cdot b^{n-1}+(x_2-bx_1)(n-1)\cdot b^{n-2}\)，
整理一下，\(x_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.\)，所以\(x_n=(\alpha+\beta n)\cdot b^n\)。
解题时只需要待定系数求出\(\alpha、\beta\)即可得到通项公式。
PartⅢ 从递推到矩阵
上面都是低阶的问题，如果碰到更高阶的常系数线性齐次递推式子呢？由于是预备知识，在这里不详述，可以先看下面这一篇知乎上的文章↓：
二阶常系数齐次线性递推数列 - 知乎 (zhihu.com)
