[數論] 遞迴數列解法

參考資料：
遞歸數列，凡異出版社，1994年3月初版，ISBN：957694130X
線性遞迴關係之求解(下) - 中研院數學研究所

二階常係數線性齊次遞迴方程的解法(單一方程)
對於 $a_{n}+p_{1}a_{n-1}+p_{2}a_{n-2}=0$, 通解的主要思路是通過用 $a_{n}=x^{n}$ 代換, 把上述方程轉化到特徵方程 $x^{2}+p_{1}x+p_{2}=0$, 解此特徵方程即得原方程的通解. 最後把初始條件帶入通解, 得到特解.

• 當 $\Delta >0$ 時, 有兩相異實根, $x_{1}=q_{1}$, $x_{2}=q_{2}$

        通解為 $a_{n}=c_{1}q_{1}^{n}+c_{2}q_{2}^{n}$.

• 當 $\Delta =0$ 時, 有兩相等實根, $x_{1}=x_{2}=q$

        通解為 $a_{n}=\left ( c_{1}+c_{2}n \right )q^{n}$.

• 當 $\Delta <0$ 時, 有一對共軛複數根, $x_{1}=r\left ( cos\theta +isin\theta  \right )$, $x_{2}=r\left ( cos\theta -isin\theta  \right )$

        通解為 $a_{n}=a_{n}=r^{n}\left ( c_{1}cosn\theta +c_{2}sinn\theta  \right )$.

遞迴方程組的解法
設有兩個數列 $a_{1},a_{2},...a_{n},...$ 和 $b_{1},b_{2},...b_{n},...$ 同時滿足遞迴方程組 $\left\{\begin{matrix}
a_{n+1} =p_{1}a_{n}  +q_{1}b_{n} \\
b_{n+1} =p_{2}a_{n}  +q_{2}b_{n}
\end{matrix}\right.$, 其中 $p_{i}$, $q_{i}(i=1,2)$ 是實常數. 這個遞迴方程組稱為二元遞迴方程組.

• 代入消去法

• 行列式法

        對於方程組 $\left\{\begin{matrix}a_{n+1}=p_{1}a_{n}+q_{1}b_{n}\\ b_{n+1}=p_{2}a_{n}+q_{2}b_{n}\end{matrix}\right.$, 若 $\begin{vmatrix}p_{1} &q_{1} \\ p_{2} &q_{2} \end{vmatrix}=0$, 即 $p_{1}=\lambda p_{2}$, $q_{1}=\lambda q_{2}$.

        對於 $\begin{vmatrix}p_{1} &p_{2} \\ q_{1} &q_{2} \end{vmatrix}\neq 0$, 我們求形如 $a_{n}=Ax^{n}$, $b_{n}=Bx^{n}$ 的解($A$, $B$ 為待定係數).

二階常係數線性非齊次遞迴方程的解法
若存在兩個常數 $p_{1}$, $p_{2}$, 對任意 $n\geq 2$, 有 $a_{n}+p_{1}a_{n-1}+p_{2}a_{n-2}=f(n)$, 其中 $f(n)\neq 0$, 則稱此方程為「二階常係數線性非其次遞迴方程」, 對應之齊次特徵方程為 $x^{2}+p_{1}x+p_{2}=0$

通解 = 對應的齊次方程的通解 + 非齊次方程的任何一個特解

就 $f(n)$ 的幾種特殊類型函數, 我們討論它的特解形式. 以下列出六種：

• $f(n)$ 是 $n$ 的二次多項式, 即 $f(n)=a_{2}n^{2}+a_{1}n+a_{0}$

       (1) 若 $x=1$ 不是特徵方程的根, 則特解為 $a_{n}^{*}=A_{2}n^{2}+A_{1}n+A_{0}$.

       把特解代入特徵方程式, 比較係數得到 $\left\{\begin{matrix}A_{2}\left ( 1+p_{1}+p_{2} \right )=a_{2}\\ A_{1}\left ( 1+p_{1}+p_{2} \right )-2A_{2}\left ( p_{1}+2p_{2} \right )=a_{1}\\ A_{0}\left( 1+p_{1}+p_{2} \right )-A_{1}\left ( p_{1}+p_{2} \right )+A_{2}\left ( p_{1}+4p_{2} \right )=a_{0}\end{matrix}\right.$

       因為 $x=1$ 不是 $x^{2}+p_{1}x+p_{2}=0$ 的根, 即 $1+p_{1}+p_{2}\neq 0$, 故 $A_{2}$, $A_{1}$ 和 $A_{0}$ 都可以確定.

       (2) 若 $x=1$ 是特徵方程式的單根, 則特解為 $a_{n}^{*}=n\left ( A_{2}n^{2}+A_{1}n+A_{0} \right )$.

       (3) 若 $x=1$ 是特徵方程式的重根, 則特解為 $a_{n}^{*}=n^{2}\left ( A_{2}n^{2}+A_{1}n+A_{0} \right )$.

• $f(n)$ 是指數函數, 即 $f(n)=c\cdot k^{n}$

       (1) 若 $x=k$ 不是特徵方程式的根 則特解為 $a_{n}^{*}=Bk^{n}$. ($B$ 是待解係數)

       (2) 若 $x=k$ 是特徵方程式的單根 則特解為 $a_{n}^{*}=nBk^{n}$.

       (3) 若 $x=k$ 是特徵方程式的重根 則特解為 $a_{n}^{*}=n^{2}Bk^{n}$.

• $f(n)$ 是正弦或餘弦函數, 即 $f(n)=c\cdot cosn\theta $ 或 $f(n)=c\cdot sinn\theta $
• $f(n)$ 是一個指數函數與多項式的積, 即 $f(n)=g(n)\cdot k^{n}$, 其中 $k$ 是常數, $g(n)$ 是關於 $n$ 的 $m$ 次多項式
• $f(n)$ 是指數函數與正弦(或餘弦)函數的積, 即 $f(n)=k^{n}cosn\theta $ 或 $f(n)=k^{n}cosn\theta $
• $f(n)$ 是多項式與正弦(或餘弦)函數的積, 即 $f(n)=g(n)cosn\theta $ 或 $f(n)=g(n)sinn\theta $

二階遞迴數列的求和問題

一般來說, 數列 $\left \{ a_{n} \right \}$ 的求和問題, 關鍵是找出其通項公式再求和. 但是, 對於遞迴數列, 我們可以不求出它的通項, 直接從它所適合的遞迴方程中求出這個遞迴數列的前 $n$ 項的和.

假設數列  $\left \{ a_{n} \right \}$ 是二階遞迴列, 所適合的二階線性齊次遞迴方程為 $f(x)=0$(二次多項式), 則 $\left \{ a_{n} \right \}$ 的前 $n$ 項和 $S_{n}$ 對應之特徵方程是 $(x-1)f(x)=0$, 它只比 $\left \{ a_{n} \right \}$ 的特徵方程多了一個特徵根 $x=1$.
(hint: 用 $a_{n}=S_{n}-S_{n-1}(n\geq 2)$ 代換)

遞迴方程的其他各種解法
當特徵方程式的根不易求出, 或遞迴方程不是線性或常係數時, 需要透過其他的途徑求解.

• 數學歸納法
• 迭代法與逐差法
• 變量代換法(換元法) e.g. 非線性轉成線性, 變係數轉為常係數...等
• 母函數解法