1. 遞推關系建立

給定一個數的序列 $f(0),f(1),...,f(n),...,$ 若存在整數 $n_0$ ，使當 $n\ge n_0$ 時,可以用等號（或大于號、小于號）將 $f(n)$ 與前面的某些項 $f(i)(0\le i<n)$ 聯系起來，這樣的式子稱作遞推關系
建立遞推關系的步驟如下:

1. 找第 n 項與其前面最近幾項的關系
2. 獲得最前面幾項的具體值，即初值

習題1、 n 位四進制數中，有偶數個 0 的序列共有多少個？
解: 設 $f(n)$ 表示 n 位四進制數中有偶數個 0 的序列，它可由兩部分生成:
(1) 在 n ?1位四進制數中有偶數個 0 的序列上再添一位非 0（即 1,2,3）的數，可產生$3f(n?1)$ 個
(2) 在 n ?1位四進制數中有奇數個 0 的序列上再添一位 0，可產生 $4^{n?1}?f(n?1)$ 個
由加法原則$$f(n)=3f(n?1)+4^{n?1}?f(n?1)=4^{n?1}+2f(n?1)$$顯然 $f(1)=3$ 所以構成帶初值的遞推關系$\{\begin{array}{c}f(n)=4^{n?1}+2f(n?1)\\ f(1)=3\end{array}$

習題2、 1×n 棋盤用紅、白、藍 3 種顏色著色，不允許相鄰兩格都著紅色，求著色方案數
解: 設 $f(n)$ 表示滿足條件的著色方案數。在該棋盤上著色，其方案可分成如下 2 類
(1) 第一個格子著白/藍色，余下的是1x(n-1)的棋盤，它所滿足條件的著色方案數是:$2f(n?1)$
(2) 第一個格子著紅色，第二個格子著白/藍色，余下1x(n-2)的棋盤，著色方案數是:$2f(n?2)$

故總的著色方案數為$\{\begin{array}{c}f(n)=2f(n?1)+2f(n?2)\\ f(1)=3,f(2)=8\end{array}$

給定遞推關系：$$f(n)=c_1(n)f(n?1)+c_2(n)f(n?2)+...+c_k(n)f(n?k)+g(n)$$其中 $c_k(n)\ne 0$，則稱該關系為 { f ( n ) } \{ f(n)\} {f(n)} 的 k 階線性遞推關系
如果 $g(n)=0$ ， 則稱之為齊次

2. 常系數齊次遞推關系的求解

$$f(n)=c_1(n)f(n?1)+c_2(n)f(n?2)+...+c_k(n)f(n?k)$$
方程$$x^k?c_1{x}^{k?1}?c_2{x}^{k?2}?...?c_k=0$$是上述遞推關系的的特征方程，它的 $k$ 個根 $q_1,q_2,...,q_k$（可能有重根）叫作該遞推關系的特征根，其中 $q_i(i=1,2,...,k)$是復數。

定理 2.1：設 $q$ 是非零復數，當且僅當 q 是它的特征根， $f(n)=q^n$ 是遞推關系的解

定理 2.2：如果 $h_1(n),h_2(n)$都是遞推關系的解，$b_1$，$b_2$是常數，則$b_1{h}_1(n)+b_2{h}_2(n)$也是遞推關系的解

定理 2.3：設$q_1,q_2,...,q_k$是遞推關系的 k 個互不相等的特征根，$b_1$，$b_2$是常數，則 $f(n)=b_1{q}_1^n+b_2{q}_2^n+...+b_k{q}_k^n$ 是遞推關系通解

習題3、 求解遞推關系 $\{\begin{array}{c}f(n)=7f(n?1)?12f(n?2)\\ f(0)=2,f(1)=7\end{array}$

解: 先求這個遞推關系的通解。其特征方程為 $x^2?7x+12=0$，解這個方程得 $$x_1=4,x_2=3$$所以通解為 $f(n)=c_1?4^n+c_2?3^n$
帶入初值確定 $c_1,c_2$，得$\{\begin{array}{c}{c}_1+c_2=2\\ 4c_1+3c_2=7\end{array}$
得 $c_1=1,c_2=1$
所以通解為 $f(n)=4^n+3^n$

習題4、 求解遞推關系 $\{\begin{array}{c}f(n)=f(n?1)+9f(n?2)?9f(n?3)\\ f(0)=0,f(1)=1,f(2)=2\end{array}$

解: 先求這個遞推關系的通解。其特征方程為 $x^3?x^2?9x+9=0$，解這個方程得 $$x_1=1,x_2=3,x_3=?3$$所以通解為 $f(n)=c_1?1^n+c_2?3^n+c_3?(?3{)}^n$
帶入初值確定 $c_1,c_2,c_3$，得$?\begin{array}{c}{c}_1+c_2+c_3=0\\ c_1+3c_2?3c_3=1\\ c_1+9c_2+9c_3=2\end{array}$
得 $c_1=?\frac{1}{4},c_2=\frac{1}{3},c_3=?\frac{1}{12}$

所以通解為 $f(n)=?\frac{1}{4}?1^n+\frac{1}{3}?3^n?\frac{1}{12}?(?3{)}^n$

定理 2.4：設$q_1,q_2,...,q_k$是遞推關系的全部不同的特征根，其重數分別為 $e_1,e_2,...,e_t$$(e_1+e_2+...+e_t=k)$，則遞推關系的通解為$$f(n)=f_1(n)+f_2(n)+...f_t(n)$$其中$$f_i(n)=(b_{i_1}+b_{i_2}n+...+b_{i_{e_i}}{n}^{e_i?1})?q_i^n(1\le i\le t)$$

習題5、 求解遞推關系 $\{\begin{array}{c}f(n)=3f(n?2)?2f(n?3)(n\ge 3)\\ f(0)=1,f(1)=0,f(2)=0\end{array}$

解: 先求這個遞推關系的通解。其特征方程為 $x^3?3x+2=0$，解這個方程得 $$x_1=1,x_2=1,x_3=?2$$所以通解為 $f(n)=c_1?1^n+c_{2}n?1^n+c_3?(?2{)}^n$
帶入初值確定 $c_1,c_2,c_3$，得$?\begin{array}{c}{c}_1+c_3=1\\ c_1+c_2?2c_3=0\\ c_1+2c_2+4c_3=0\end{array}$
得 $c_1=\frac{8}{9},c_2=?\frac{2}{3},c_3=\frac{1}{9}$

所以通解為 $f(n)=\frac{8}{9}?1^n?\frac{2}{3}n?1^n+\frac{1}{9}?(?2{)}^n=\frac{8}{9}?\frac{2}{3}n+\frac{1}{9}?(?2{)}^n$

3. 常系數非齊次遞推關系的求解

$$f(n)=c_1(n)f(n?1)+c_2(n)f(n?2)+...+c_k(n)f(n?k)+g(n)$$對應的齊次遞推關系為$$f(n)=c_1(n)f(n?1)+c_2(n)f(n?2)+...+c_k(n)f(n?k)$$

定理 3.1：k 階常系數線性非齊次遞推關系的通解是遞推關系的特解加上其相應的齊次遞推關系的通解。即非齊次遞推關系的解 = 特解 + 齊次方程通解

習題6、 求解遞推關系 $\{\begin{array}{c}f(n)=4f(n?1)?3f(n?2)+3^n(n\ge 2)\\ f(0)=1,f(1)=2\end{array}$

解: 先求這個遞推關系的通解。其特征方程為 $x^2?4x+3=0$，解這個方程得 $$x_1=1,x_2=3$$因為3是特征方程的一重根，所以該遞推關系的非齊次特解為 $an{3}^n$。將其代入遞推關系，得$$an{3}^n=4a(n?1)3^{n?1}?3a(n?2)3^{n?2}+3^n$$化簡得 $a=\frac{3}{2}$，特解為 $f^{\prime }(n)=\frac{3}{2}n{3}^n$

而相應齊次遞推關系的通解為 $f^{\prime \prime }(n)=c_1?1^n+c_{2}n?3^n$

通解為$$f(n)=f^{\prime }(n)+f^{\prime \prime }(n)=c_1+c_2?3^n+\frac{3}{2}n{3}^n$$帶入初值確定 $c_1,c_2$，得$\{\begin{array}{c}{c}_1+c_2=1\\ c_1+3c_2+\frac{9}{2}=2\end{array}$

得 $c_1=\frac{11}{4},c_2=?\frac{7}{4}$

所以通解為 $f(n)=\frac{11}{4}?\frac{7}{4}?3^n+\frac{3}{2}n{3}^n$

習題7、 求解遞推關系 $\{\begin{array}{c}f(n)=f(n?1)+n^2\\ f(1)=1,f(2)=5,f(3)=14\end{array}$

解: 先求這個遞推關系的通解。其特征方程為 $x?1=0$，解這個方程得 $$x=1$$因為1是特征方程的一重根，所以該遞推關系的非齊次特解為 $n^1(b_2{n}^2+b_1{n}^1+b_0)$。將其代入遞推關系，得$$n^1(b_2{n}^2+b_1{n}^1+b_0)=(n?1)(b_2(n?1{)}^2+b_1(n?1)+b_0)+n^2$$比較系數可得$?\begin{array}{c}{b}_1=?3b_2+b_1+1\\ b_0=3b_2?2b_1+b_0\\ 0=?b_2+b_1?b_0\end{array}$，解得$?\begin{array}{c}{b}_0=1/6\\ b_1=1/2\\ b_2=1/3\end{array}$ 特解為 $$f^{\prime }(n)=n(\frac{1}{3}{n}^2+\frac{1}{2}n+\frac{1}{6})$$而相應齊次遞推關系的通解為 $f^{\prime \prime }(n)=c_1?1^n$

通解為$$f(n)=f^{\prime }(n)+f^{\prime \prime }(n)=c_1?1^n+n(\frac{1}{3}{n}^2+\frac{1}{2}n+\frac{1}{6})$$帶入初值確定 $c_1$，得 $c_1+1?(\frac{1}{3}+\frac{1}{2}+\frac{1}{6})=1$

得 $c_1=0$

所以通解為 $f(n)=n(\frac{1}{3}{n}^2+\frac{1}{2}n+\frac{1}{6})=\frac{1}{6}n(n+1)(2n+1)$

4. 迭代法

但對于某些非線性的遞推關系，不存在求解的公式，因此不能用上述方法。
碰到此類問題，不妨嘗試用迭代歸納法來求解。