如果一个递推关系是非齐次的，形如：
$$
a_n=c_1 \cdot {a}{n-1}+c_2 \cdot {a}{n-2}+c_1 \cdot {a}{n-3} \cdots c_k \cdot {a}{n-k}+F(n) \
且 F(n)只依赖于n，F(n) \neq 0
$$
其中a_n中齐次部分叫做：相伴的齐次递推关系
对于这种递推关系，其解有两部分组成： $$ {a}^{(h)}{n}是相伴的齐次递推关系的一个解。\ {a}^{(p)}{n}是常系数线性非齐次递推关系的一个特解。\ 其解的形式为：\ ({a}^{(h)}{n}+{a}^{(p)}{n}) $$ 啥意思呢？ $$ 简单来说就是首先要找到递推关系的一个特解：{a}^{(p)}{n}，啥叫特解呢？就是在这个解下，递推关系成立。因为解可能不止一个，所以叫做特解。\ 然后就是去找相伴的齐次递推关系的解，两者一组合，就是原本递推关系的解了。 $$ 先看一个例子，然后再说明上面的定理为什么是对的。例子： $$ 求：a_n=3 \cdot {a}{n-1}+2n,a_1=3的解 $$ 解题过程： $$ 这里的 F(n)=2n，于是我们就假设特解的形式为：F(n)=c\cdot n+d，其中c,d \in R。\ 于是：a_n=cn+d=3\cdot (c(n-1)+d)+2n \ 展开化解后：(2+2c)n+(2d-3c)=0。\ 为了使 F(n)=c\cdot n+d 成为递推关系的特解，即真对所有的n都成立。\ 必须：2+2c=0\ \cap\ 2d-3c=0。于是我们求的：{a}^{(p)}{n}=-n-\frac{3}{2}\ 下面再来求解相伴的齐次递推关系的解。根据 a_n=3 \cdot {a}{n-1}可知，其解应该为 {a}^{(h)}{n}=k \cdot 3^n\ 于是我们套用上面的公式：\ a_n={a}^{(p)}{n}+{a}^{(h)}{n}=-n-\frac{3}{2}+k\cdot 3^n \ a_1=3=-1-\frac{3}{2}+k\cdot 3^1 \ 求得：k=\frac{11}{6} \ 于是a_n=-n-\frac{3}{2}+ \frac{11}{6} \cdot 3^n $$ 在借用了这个例子理解了上面各个部分的含义之后，接下来证明为什么上面的解的形式是有效的： $$ 因为 {a}^{(p)}{n} 是递推关系的一个解，所以：\ {a}^{(p)}{n}=c_1 {a}^{(p)}{n-1}+c_2 {a}^{(p)}{n-2} \cdots c_k {a}^{(p)}{n-k}+F(n)\ 同时，设 b_n 为递推关系的另一个解，所以：\ b_n=c_1 {b}{n-1}+c_2 {b}{n-2} \cdots c_k {b}{n-k}+F(n)\ 所以 \ b_n-{a}^{(p)}{n}=c_1 ({b}{n-1}-{a}^{(p)}{n-1})+c_2 ({b}{n-2}-{a}^{(p)}{n-2}) \cdots ({b}{n-k}-{a}^{(p)}{n-k}) \ 可以看到结果是一个常系数线性齐次递推关系，定义其为{a}^{(h)}{n}\ 所以 b_n={a}^{(p)}{n}+{a}^{(h)}_{n} $$
下面就是对于一种特殊情况的F(n)的通用解：
$$
F(n)=(b_t n^t + {b}{n-1} {n}^{t-1} \cdots b_1 n+b_0)\cdot s^n，其中 b_1,b_2 \cdots b_0,s \in R 时,\
当 s 不是相伴齐次递推关系的根时，特解形式为：\
(p_t n^t + {p}{n-1} {n}^{t-1} \cdots p_1 n+p_0)\cdot s^n \
当 s 时相伴齐次递推关系的根，且其重数为m时，特解形式为：\
n^m \cdot (p_t n^t + {p}{n-1} {n}^{t-1} \cdots p_1 n+p_0)\cdot s^n
$$
例子：
$$
a_n=6 {a}{n-1}-9 {a}{n-2}+F(n)的特解，在F(n)=3^n,F(n)=n 3^n,F(n)=n^2 2^n,F(n)=(n^2+1) 3^n时，分别为多少？
$$
解决过程：
$$
相伴的齐次递推关系为：a_n=6 {a}{n-1}-9 {a}_{n-2}，其特征方程为 r^2-6n+9=(r-3)^2=0，其特征根为一个2重根3。\
所以当 F(n)=3^n时，特解形式为 n^2 p_0 3^n \
当 F(n)=n3^n时，特解形式为 n^2 (p_1n+p_0) 3^n \
当 F(n)=n^2 2^n时，特解形式为 (p_2 n^2+p_1n+p_0) 2^n\
当 F(n)=(n^2+1) 3^n时，特解形式为 n^2 (p_2 n^2+p_1n+p_0) 3^n
$$