递推关系求数列通项公式
1. 一阶线性递推
一阶线性递推指$a_{n+1}=f(a_n)$，其中$f$是线性函数的递推关系，可以用待定系数法转化为相关的等比数列，从而求通项公式。
待定系数法
设数列$\{a_n\}$满足$a_{n+1}=pa_n+q$，其中$pq(p-1)\not=0$。
假设递推公式可写成$a_{n+1}+t=p(a_n+t)$的形式，解得$t=q/(p-1)$，于是可知数列$\{a_n+\frac{q}{p-1}\}$是等比数列，写出该数列的通项公式，即可得到原数列通项公式。
不动点法
这种方法也可理解为寻找不动点的方法。
图为递推数列$\{a_n\}$的直观表示，图中折线为从点$(a_1,0)$开始的迭代，其与$f$交点的纵坐标恰为$a_2,a_3,a_4,\cdots,a_n$，$A$点是$f$与$y=x$的交点，这点的特殊之处是其在迭代之后仍是自身，因此被称为不动点，而不动点外的任一点在迭代后都是发散的。
解方程$px+q=x$即可得到不动点的值，恰为$q/(p-1)$，与待定系数法中的$t$值相等，而之后的处理方法可以理解为将图像整体向右上移动，使不动点与原点重合，得到的新数列$\{b_n\}$为等比数列，且$b_n=a_n+q/(p-1)$。显然，只要$f(x)=px+q$，且$pq(p-1)\not=0$，则不动点必然存在。
若将递推式稍加改动，变为$a_{n+1}=pa_n+qn+r$，不动点法就不适用了。但此数列显然能表示为等比数列与一个确定的等差数列之和，可以使用待定系数法(本质其实差不多，可以认为存在一个规律变化的”不动点”)。
设$a_{n+1}+k(n+1)+l=p(a_n+kn+l)$，即：
$$
\begin{cases}
(p-1)k=q\\
pl-k-l=r
\end{cases}
$$
解得$k=q/(p-1)$，$l=r/(p-1)+q/(p-1)^2$，于是可知数列
$$\{a_n+\frac{q}{p-1}n+(\frac{r}{p-1}+\frac{q}{(p-1)^2})\}$$
是等比数列，之后的步骤同上。
2. 二阶线性递推
二阶线性递推指$a_{n+2}=f(a_{n+1})+g(a_n)$，其中$f,g$是线性函数的递推关系，可以用待定系数法得到两个相关的等比数列，原数列的每一项是两个等比数列中对应项的线性组合。
待定系数法
先考虑最基本的情况，即$a_{n+2}=pa_{n+1}+qa_n$
假设$a_{n+2}-sa_{n+1}=t(a_{n+1}-sa_n)$，这样设的目的是构造${a_n}$减去一个等比数列仍得到等比数列的形式。同时发现此式为对称式，即可以改写为$a_{n+2}-ta_{n+1}=s(a_{n+1}-ta_n)$的形式。
展开与原式比较可得方程组：
$$
\begin{cases}
s+t=p\\
st=-q
\end{cases}
$$
特征方程与特征根
根据韦达定理，$s,t$对应二次方程$x^2-px-q=0$的两个根，该二次方程即数列的特征方程，$s,t$为特征根，因此该方法也被称为特征根法。
接下来分两种情况考虑。
若$s=t$，即$a_{n+2}-sa_{n+1}=s(a_{n+1}-sa_n)$，直接用累乘得$a_{n+2}=s^n(a_2-sa_1)+sa_{n+1}$，同理可得：
$$
\begin{align*}
sa_{n+1}&=s^n(a_2-sa_1)+s^2a_n\\
s^2a_n&=s^n(a_2-sa_1)+s^3a_{n-1}\\
&\cdots\cdots\\
s^{n-1}a_3&=s^n(a_2-sa_1)+s^na_2
\end{align*}
$$
于是再用累加，得到：
$$a_{n+2}=n\cdot s^n(a_2-sa_1)+s^na_2$$
即：
$$a_{n}=(n-2)\cdot s^{n-2}(a_2-sa_1)+s^{n-2}a_2$$
若$s\not=t$，将解得的$s,t$代回原式，并累乘(随便改一下下标)：
$$
\begin{align*}
a_{n+1}-sa_n&=t^{n-1}(a_2-sa_1)\\
a_{n+1}-ta_n&=s^{n-1}(a_2-ta_1)
\end{align*}
$$
两式相减可得：
$$(t-s)a_n=t^{n-1}(a_2-sa_1)-s^{n-1}(a_2-ta_1)$$
于是得到通项公式：
$$a_n=\frac{1}{t-s}[t^{n-1}(a_2-sa_1)-s^{n-1}(a_2-ta_1)]$$
特别地，当$p=q=a_1=a_2=1$时，该数列为斐波那契数列，其特征根为：
$$
\begin{cases}
s=\frac{1-\sqrt{5}}{2}\\
t=\frac{1+\sqrt{5}}{2}
\end{cases}
$$
代入上式可得斐波那契数列通项公式：
$$a_n=\frac{1}{t-s}(t^{n}-s^{n})=\frac{\sqrt{5}}{5}\left[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n\right]$$
复数根与周期性
若不存在实根，则必存在两个不同的复根$s,t$，把它们代入上述公式，同样能得到结果(上述推导过程换成复数也成立)。例如$a_{n+2}=a_{n+1}-a_n,a_1=1,a_2=2$，其特征方程为$x^2-x+1=0$，解得$s,t=(1\pm\sqrt3\mathrm{i})/2$，代入得：
$$a_n=-\frac{\sqrt3\mathrm{i}}{3}\left[(\frac{1+\sqrt3\mathrm{i}}{2})^{n-1}(\frac{3+\sqrt{3}\mathrm{i}}{2})-(\frac{1-\sqrt3\mathrm{i}}{2})^{n-1}(\frac{3-\sqrt{3}\mathrm{i}}{2})\right]$$
计算该数列的前几项，发现其为以$1,2,1,-1,-2,-1$为周期的周期性数列，显然这样的性质在特征根为实数的二阶递推数列中是不可能的。那么，满足什么条件的数列有此性质呢？
设$s,t=r(\cos\theta\pm\mathrm{i}\sin\theta)$，代入，使用棣莫弗定理化简得：
$$a_n=\frac{r^{n-2}}{\sin\theta}[a_2\sin(n-1)\theta-ra_1\sin(n-2)\theta]$$
然后一个含复数的式子就直接转换成了一个简单的三角函数，用该式计算$a_n$：
$$
\begin{align*}
a_3&=\frac{r}{\sin\theta}(a_2\sin2\theta-ra_1\sin\theta)\\
a_4&=\frac{r^2}{\sin\theta}(a_2\sin3\theta-ra_1\sin2\theta)\\
a_5&=\frac{r^3}{\sin\theta}(a_2\sin4\theta-ra_1\sin3\theta)\\
&\cdots\cdots
\end{align*}
$$
于是可得，若数列存在周期性，显然必须满足两点：
- 特征根的模长$r=1$
- 辐角$\theta=p\pi/q$，其中$p,q\in\mathbb{Z}\backslash0$
满足这两点后，数列必为周期数列，且可以确定周期长度为$(p+1)\cdot(q,2)$
对于$a_{n+2}=pa_{n+1}+qa_n+r$或$a_{n+2}=pa_{n+1}+qa_n+rn+s$这样更复杂的递推关系，其本质也是两个等比数列的线性组合，只是添加常数项或确定的等差数列项，在此限于篇幅，不多赘述。
3. $k$阶线性递推
对于$k$阶线性递推，即表示为$a_{n+k}=c_1a_{n+k-1}+c_2a_{n+k-2}+\cdots+c_ka_n,k\ge2$的递推关系，情况要复杂很多，很明显初等数学不够用了。
用矩阵来表示递推关系，那么斐波那契数列就可表示为：
$$\begin{bmatrix}a_{n+1}\\a_{n}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}a_{n}\\a_{n-1}\end{bmatrix}$$
则可以直接乘起来得到通项公式：
$$\begin{bmatrix}a_{n+1}\\a_{n}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^n\begin{bmatrix}1\\1\end{bmatrix}$$
同样的，$k$阶线性递推通项公式可用矩阵表示为：
$$\begin{bmatrix}a_{n}\\a_{n-1}\\\cdots\\a_{n-k+2}\\a_{n-k+1}\end{bmatrix}=\begin{bmatrix}c_1&c_2&\cdots&c_{k-1}&c_k\\1&0&\cdots&0&0\\0&1&\cdots&0&0\\\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&\cdots&0&0\\0&0&\cdots&1&0\end{bmatrix}^{n-1}\begin{bmatrix}a_{k}\\a_{k-1}\\\cdots\\a_{2}\\a_{1}\end{bmatrix}$$
理论上求出上式中$k\times k$矩阵的$n$次幂就能得到通项公式，但实际上根本不会算，等我有时间学了线性代数在补吧。
4. 分式递推
取倒
对于分子无常数项的分式递推数列，直接两边取倒数即可。
递推关系(注意递推式函数图像经过原点)
$$a_n=\frac{pa_{n-1}}{qa_{n-1}+r}$$
取倒数得：
$$\frac{1}{a_n}=\frac{q}{p}\cdot\frac{1}{a_{n-1}}+\frac{r}{p}$$
于是得到一阶线性递推数列$\{1/a_n\}$，用待定系数法求出其通项公式，再取其倒数就得到原数列通项公式。
不动点法
对于一般形式的分式递推数列，即$x_n=(ax_{n-1}+b)/(cx_{n-1}+d)$的递推关系，可以使用不动点方法。
有了一阶线性递推的经验，就直接解方程：
$$\frac{ax+b}{cx+d}=x$$
即方程$cx^2+(d-a)x-b$，该方程也称作此分式递推数列的特征方程，其根同样可称为特征根。
解这个二次方程可以得到2个根，分两种情况考虑。
若$x_1=x_2=\alpha$，则数列有一个不动点。在递推式两边同时减去$\alpha$再取倒数，可得到一个相关的等差数列，求出该数列通项公式后稍作处理可得原数列通项公式。这里的一个问题是，为什么得到的是相关的等差数列，而不是一般的一阶线性递推数列？
对于此问题，有一种直观的理解方法。像本文一开始那样用图像表示递推过程：
如图，$A$即为不动点，其坐标$(\alpha,\alpha)$，$f$与$y=x$在$A$点相切。在递推公式两边减去$\alpha$，就相当于将整个图像向右上平移，使$A$与原点重合。于是该数列就转化为一个可以直接取倒数求解的简单分式递推数列(递推式函数图像经过原点)，同时还满足图像在原点处与$y=x$相切。所以只需证满足以上两个条件的函数取倒数后$-1$次项系数为$1$，即：
$$
\begin{cases}
g(x)=\frac{px}{qx+r}\\
g’(0)=1
\end{cases}
\Rightarrow \frac{1}{g(x)}=\frac{1}{x}+\lambda
$$
其中$p,q,r,\lambda$是常数。这是容易证明的，具体过程就不写了。
但这好像有些兜圈子了，更“简单”的方法是直接把$\alpha=(a-d)/2c$代进去计算，这样甚至能把得到的等差数列的公差算出来。懒得计算了，就直接写最终结论吧，该等差数列递推公式为：
$$\frac{1}{x_{n}-\alpha}=\frac{1}{x_{n-1}-\alpha}+\frac{2c}{a+d}$$
例如，$x_n=(x_{n-1}-1)/(x_{n-1}+3)$，其特征方程$x^2+2x+1=0$，解得$x_1=x_2=-1$，于是变换递推式为：
$$x_n+1=\frac{x_{n-1}-1}{x_{n-1}+3}+1=\frac{2x_{n-1}+2}{x_{n-1}+3}$$
两边取倒数得：
$$\frac{1}{x_n+1}=\frac{1}{x_{n+1}+1}+\frac{1}{2}$$
若$x_1=\beta_1\not=x_2=\beta_2$，则数列有两个不动点。分别将递推公式减去两个不动点，得到两个式子：
$$
\begin{align*}
x_n-\beta_1=\frac{ax_{n-1}+b}{cx_{n-1}+d}-\beta_1=\frac{(a-\beta_1c)(x_{n-1}-\beta_1)}{cx_{n-1}+d}\\
x_n-\beta_2=\frac{ax_{n-1}+b}{cx_{n-1}+d}-\beta_2=\frac{(a-\beta_2c)(x_{n-1}-\beta_2)}{cx_{n-1}+d}
\end{align*}
$$
两式相除得到：
$$\frac{x_n-\beta_1}{x_n-\beta_2}=\frac{a-\beta_1c}{a-\beta_2c}\cdot\frac{x_{n-1}-\beta_1}{x_{n-1}-\beta_2}$$
得到一个相关的等比数列，略加处理即可得到原数列通项公式。
例如，$x_n=(x_{n-1}-2)/(x_{n-1}+4)$，其特征方程$x^2+3x+2=0$，解得$x_1=-1,x_2=-2$，代入得到两个式子：
$$
\begin{align*}
x_n+1=\frac{2x_{n-1}+2}{x_{n-1}+4}\\
x_n+2=\frac{3x_{n-1}+6}{x_{n-1}+4}
\end{align*}
$$
两式相除得到：
$$\frac{x_n+1}{x_n+2}=\frac{2}{3}\cdot\frac{x_{n-1}+1}{x_{n-1}+2}$$
以上就是基本的不动点法，事实上，题目中还可能出现高次的分式递推，本质也是用上述方法，但需要一些额外的处理，具体情况具体分析。
复数根与周期性
如果分式递推数列特征根是复数，那么不动点就不存在了。正如在二阶线性递推部分所讨论的，可以将复根代入公式，不影响最终结果。那么就产生了一个问题：这样的情况下该分式递推数列是否可能是周期数列？
不妨先看一下一些不动点不存在的分式数列迭代图像：
递推公式：$a_n=(a_{n-1}-1)/(a_{n-1}+1)$
特征根：$x_1=\mathrm{i},x_2=-\mathrm{i}$
是周期性数列，其周期是$8$
递推公式：$a_n=(a_{n-1}-2)/(a_{n-1}+2)$
特征根：$x_1=(-1+\sqrt{7}\mathrm{i})/2,x_2=(-1-\sqrt{7}\mathrm{i})/2$
显然不是周期性数列，迭代值不断“震荡”，但不会重复，应该可以迭代到函数上每一点。
递推公式：$a_n=(-a_{n-1}-5)/(a_{n-1}+1)$
特征根：$x_1=-1+2\mathrm{i},x_2=-1-2\mathrm{i}$
是周期性数列，其周期为$4$
看到以上三个例子，就基本能总结规律了。与二阶线性递推中对特征根模长与辐角的要求不同，这里的要求是复根的实部和虚部都为有理数。这样，对初始值进行迭代就终将回归自身，形成周期，否则会会迭代到函数上的每一点。当然，以上仅为猜想，并没有证明，等有时间了再研究一下这个问题。
5. 特殊处理
上面说的全都是套路性的方法，实际的数列题当然不可能这么简单，一般需要对非线性的递推式进行特殊处理。下面举两道例题。
例1：$a_1=a_2=1$，$a_n=(a_{n-1}^2+2)/a_{n-2}$，求通项公式。
又是二阶又是分式递推，还是二次的，完全没有头绪。那就凭感觉化简一下，第一步先把分子乘过去，使两边齐次：
$$a_na_{n-2}=a_{n-1}^2+2$$
然后再写一项：
$$a_{n+1}a_{n-1}=a_{n}^2+2$$
两式相减消去常数项：
$$a_{n+1}a_{n-1}-a_na_{n-2}=a_n^2-a_{n-1}^2$$
这样，式子的项数反而增加到了4项，但还是没有明显的规律。继续化简，整理一下，提取公因数：
$$a_n(a_n+a_{n-2})=a_{n-1}(a_{n+1}+a_{n-1})$$
居然直接就配成常数列了，但下标不连续很不方便，于是把括号除到另一半得到：
$$\frac{a_n}{a_{n+1}+a_{n-1}}=\frac{a_{n-1}}{a_n+a_{n-2}}=\frac{a_2}{a_3+a_1}=\frac{1}{4}$$
于是可知$4a_n=a_{n+1}+a_{n-1}$，接下来按照二阶线性递推的方法计算即可。
例2：$x_0=0$，$x_{n+1}=3x_n+\sqrt{8x_n^2+1}$，求通项公式。
还是往齐次去凑，把$3x_n$移到左边，两边平方得到方程：
$$x_{n+1}^2-6x_nx_{n+1}+x_n^2-1=0$$
这是个对称式，所以再写一项：
$$x_{n-1}^2-6x_nx_{n-1}+x_n^2-1=0$$
于是可知$x_{n+1},x_{n-1}$恰为$x^2-6x_nx+x_n^2-1=0$的两根，根据韦达定理：
$$x_{n+1}+x_{n-1}=6x_n$$
接下来按照二阶线性递推的方法计算即可。
所有形如$x_{n+1}=ax_n+\sqrt{(a^2-1)x_n^2+b}$的递推数列都可用此方法求通项公式。
这个例题比较有意思的一点是，数列中每一项都是整数。如果递推公式的系数$a,b$发生改变，就不一定存在这样全为整数的数列了，改变迭代的初始值，得到的也不一定是这样的数列。那么整数数列与递推公式的系数和迭代初始值有什么关系呢？这又是一个有意思的问题。(这个形式让我想起了拉马努金恒等式，但也许没什么关联？)