摘要訊息 : 使用特徵根法解一個遞迴方程式.

0. 前言

《【遞迴方程式】替代法與歸納法》中, 我們講解了使用替換法, 歸納法和列表法三種方法去解一個遞迴方程式. 但是對於比較複雜的遞迴方程式, 這三種方法可能都難以得到最終的解.

更新紀錄 :

  • 2022 年 6 月 5 日進行第一次更新和修正.

1. 線性遞迴方程式

定義 1. 若遞迴方程式 f(n)f(n) 滿足 f(n)=i=1kgi(n)f(ni)+g(n),          (I)\displaystyle {f(n) = \sum \limits_{i = 1}^{k}g_{i}(n)f(n - i) + g(n), \ \ \ \ \ \ \ \ \ \ (\mathrm {I})} 其中 gi(n)(i=1,2,...,k)g_{i}(n) (i = 1, 2, ..., k)g(n)g(n) 都是關於 nn 的函數, 而不是關於 ff 的函數; kk 為任意正整數; gk(n)0g_{k}(n) \neq 0, 那麼我們稱 f(n)f(n)線性遞迴方程式 (linear recurrence).

根據定義 1, 若 gk(n)=0g_{k}(n) = 0, 則 f(n)=i=1k1gi(n)f(ni)+g(n),\displaystyle {f(n) = \sum \limits_{i = 1}^{k - 1}g_{i}(n)f(n - i) + g(n)}, 其遞迴深度未達到 kk, 不能稱為線性遞迴方程式.

定義 2. 若存在 kk 個整數 a1,a2,...,aka_{1}, a_{2}, ..., a_{k} 使得 g1(n)=a1,g2(n)=a2,...,gk(n)=akg_{1}(n) = a_{1}, g_{2}(n) = a_{2}, ..., g_{k}(n) = a_{k}, 那麼 f(n)=i=1kgi(n)f(ni)+g(n)f(n) = \sum \limits_{i = 1}^{k}g_{i}(n)f(n - i) + g(n) 可以展開為 f(n)=a1f(n1)+a2f(n2)+...+akf(nk)+g(n).          (II)\displaystyle {f(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) + g(n). \ \ \ \ \ \ \ \ \ \ (\mathrm {II})} 其中, ak0a_{k} \neq 0nkn \geq k. 當 g(n)=0g(n) = 0 時, 稱 f(n)f(n)齊次線性遞迴方程式 (homogeneous recurrence); 當 g(n)0g(n) \neq 0 時, 稱 f(n)f(n)非齊次線性遞迴方程式 (non-homogeneous recurrence).

實際上, (II)(\mathrm {II}) 式就是分而治之演算法 (《分而治之演算法》) 時間複雜度的一種表達. 這裡, 我們採用的方式是一分為 kk.

對於 f(n)={c1n=12f(n2)+c2nn2,其中 log2n 為整數.\displaystyle {f(n) = \begin {cases} c_{1} ^{n = 1} \\ 2f \left ( \frac {n}{2} \right ) + c_{2}n & {n \geq 2} \end {cases}, \text {其中 } \log_{2}{n} \text { 為整數}}. 由於線性遞迴方程式要求右側的 fff(ni)f(n - i) 的形式, i=1,2,...,ki = 1, 2, ..., k. 而上述遞迴方程式中, f(n2)f \left ( \frac {n}{2} \right ) 不滿足這樣的形式, 因此上述遞迴方程式不是線性遞迴方程式. 但因為 log2n\log_{2}{n} 為整數, 因此 f(n)f(n) 可以寫為 f(2k)={c1k=02f(2k1)+c22kk1.\displaystyle {f(2^{k}) = \begin {cases} c_{1} & {k = 0} \\ 2f(2^{k - 1}) + c_{2}2^{k} & {k \geq 1}. \end {cases}}h(k)=f(2k)h(k) = f(2^{k}), 則有 h(k)={c1k=02h(k1)+c22kk1.\displaystyle {h(k) = \begin {cases} c_{1} & {k = 0} \\ 2h(k - 1) + c_{2}2^{k} & {k \geq 1}. \end {cases}} 顯然, h(k)h(k)f(k)f(k) 等價, 解 h(k)h(k) 實質上就是要解 f(n)f(n). 而 h(k)h(k) 是一個線性遞迴方程式. 根據 kk 的值, 我們稱 (I)(\mathrm {I}) 式為 kk線性遞迴方程式 (linear recurrence of order kk). 因此 h(k)h(k) 是一個一階線性遞迴方程式. 其中, g1(k)=2g_{1}(k) = 2g(k)=c22kg(k) = c_{2}2^{k}. h(k)h(k) 是一個一階非齊次線性遞迴方程式.

再考慮 T(n)={c1n12ni=1n1T(i)+c2nn>1.\displaystyle {T(n) = \begin {cases} c_{1} & {n \leq 1} \\ \frac {2}{n}\sum \limits_{i = 1}^{n - 1}T(i) + c_{2}n & {n > 1}. \end {cases}} 其中, c1c_{1}c2c_{2} 為任意常數. T(n)T(n) 同樣不是線性遞迴方程式, 但是可以通過轉化, 讓其成為線性遞迴方程式. 當 n>1n > 1 時, T(n)=2ni=1n1T(i)+c2n.          (III)\displaystyle {T(n) = \frac {2}{n}\sum \limits_{i = 1}^{n - 1}T(i) + c_{2}n. \ \ \ \ \ \ \ \ \ \ (\mathrm {III})} 等式兩側同時乘以 nn, 可得 nT(n)=2i=1n1T(i)+c2n2nT(n) = 2\sum \limits_{i = 1}^{n - 1}T(i) + c_{2}n^{2}. 使用 n1n - 1 替換 nn, 有 (n1)T(n1)=2i=1n2T(i)+c2(n1)2.          (IV)\displaystyle {(n - 1)T(n - 1) = 2\sum \limits_{i = 1}^{n - 2}T(i) + c_{2}(n - 1)^{2}. \ \ \ \ \ \ \ \ \ \ (\mathrm {IV})} 使用 (III)(\mathrm {III}) 式減去 (IV)(\mathrm {IV}) 式, 得 nT(n)(n1)T(n1)=2i=1n1T(i)2i=1n2T(i)+c2n2c2(n1)2.\displaystyle {nT(n) - (n - 1)T(n - 1) = 2\sum \limits_{i = 1}^{n - 1}T(i) - 2\sum \limits_{i = 1}^{n - 2}T(i) + c_{2}n^{2} - c_{2}(n - 1)^{2}}. 展開之後有 nT(n)nT(n1)+T(n1)=2T(n1)+c2(2n1).\displaystyle {nT(n) - nT(n - 1) + T(n - 1) = 2T(n - 1) + c_{2}(2n - 1)}. 移項得 nT(n)=(n+1)T(n1)+c2(2n1).\displaystyle {nT(n) = (n + 1)T(n - 1) + c_{2}(2n - 1)}. 等式兩側同時乘以 1n\frac {1}{n}, 最終可得 T(n)=n+1nT(n1)+c2(21n).\displaystyle {T(n) = \frac {n + 1}{n}T(n - 1) + c_{2}\left ( 2 - \frac {1}{n} \right )}. 不難看出, T(n)T(n) 是一個一階非齊次線性遞迴方程式. 其中, g1(n)=n+1n,g(n)=c2(21n)g_{1}(n) = \frac {n + 1}{n}, g(n) = c_{2}\left ( 2 - \frac {1}{n} \right ).

2. 特徵根法

對於函數 f(n)=i=1kgi(n)f(ni)+g(n)f(n) = \sum \limits_{i = 1}^{k}g_{i}(n)f(n - i) + g(n) 時需要 kk 個初始值的 : f(0),f(1),...,f(k1)f(0), f(1), ..., f(k - 1), 從而使得 f(k),f(k+1),...f(k), f(k + 1), ... 有惟一值. 此時, f(n)f(n) 可以表示為 f(n)={c1n=0c2n=1ck1n=k1i=1kgi(n)f(ni)+g(n)nk.\displaystyle {f(n) = \begin {cases} c_{1} & {n = 0} \\ c_{2} & {n = 1} \\ \vdots & {\vdots} \\ c_{k - 1} & {n = k - 1} \\ \sum \limits_{i = 1}^{k}g_{i}(n)f(n - i) + g(n) & {n \geq k}. \end {cases}} 對於函數 f(n)=a1f(n1)+a2f(n2)+...+akf(nk)+g(n)f(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) + g(n), 若已知 f(0),f(1),...,f(k1)f(0), f(1), ..., f(k - 1), 則我們可以通過建立方程式組來得到 a1,a2,...,aka_{1}, a_{2}, ..., a_{k} 的值.

在代數學中我們知道, 對於非齊次線性遞迴方程式 f(n)=a1f(n1)+a2f(n2)+...+akf(nk)+g(n)\displaystyle {f(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) + g(n)} 的解是其對應的齊次線性遞迴方程式的通解 fh(n)=a1f(n1)+a2f(n2)+...+akf(nk)          (V)\displaystyle {f_{h}(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) \ \ \ \ \ \ \ \ \ \ (\mathrm {V})} 再加上一個非齊次線性遞迴方程式的一個特解 fp(n)=a1f(n1)+a2f(n2)+...+akf(nk)+g(n).          (VI)\displaystyle {f_{p}(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) + g(n). \ \ \ \ \ \ \ \ \ \ (\mathrm {VI})}f(n)f(n) 的通解可以表示為 fh(n)+fp(n)f_{h}(n) + f_{p}(n).

為了確定 fh(n)f_{h}(n), 我們首先對 (V)(V) 式進行移項, 得 fh(n)a1f(n1)a2f(n2)...akf(nk)=0.\displaystyle {f_{h}(n) - a_{1}f(n - 1) - a_{2}f(n - 2) - ... - a_{k}f(n - k) = 0}. 不妨假設上述方程式可以得到一個解 fh(n)=Axnf_{h}(n) = Ax^{n}, 其中 A0A \neq 0. 將解代入上述方程式, 可以得到 Axna1Axn1a2Axn2...akAxnk=0\displaystyle {Ax^{n} - a_{1}Ax^{n - 1} - a_{2}Ax^{n - 2} - ... - a_{k}Ax^{n - k} = 0} 等式兩側同時乘以 1A\frac {1}{A} 並提取 xnkx^{n - k} 可得到 xnk(xka1xk1a2xk2...ak1xak)=0.\displaystyle {x^{n - k}(x^{k} - a_{1}x^{k - 1} - a_{2}x^{k - 2} - ... - a_{k - 1}x - a_{k}) = 0}. 上式可以簡寫為 xnk(xki=1kaixk1)=0x^{n - k}\left ( x^{k} - \sum \limits_{i = 1}^{k}a_{i}x^{k - 1} \right ) = 0. 顯然這個方程式有 nn 個根, 其中有 nkn - k 個根是 00, 剩下 kk 個根取決於 xka1xk1a2xk2...ak1xak=0.\displaystyle {x_{k} - a_{1}x^{k - 1} - a_{2}x^{k - 2} - ... - a_{k - 1}x - a_{k} = 0}. 這個方程式就是 fh(n)f_{h}(n) 的特徵方程式, 有 kk 個根 : r1,r2,...,rkr_{1}, r_{2}, ..., r_{k}. 當然, 可能存在某個根 rir_{i} (i=1,2,...,ki = 1, 2, ..., k) 重複 jj 次 (jkj \leq k).

定理 1. 若 fh(n)f_{h}(n) 的特徵方程式 xka1xk1a2xk2...ak1xak=0\displaystyle {x_{k} - a_{1}x^{k - 1} - a_{2}x^{k - 2} - ... - a_{k - 1}x - a_{k} = 0}ss 個互異解 t1,t2,...,tst_{1}, t_{2}, ..., t_{s} (sks \leq k). 則通解為 fh(n)f_{h}(n) 可以表示為 fh(n)=u1(n)+u2(n)+...+us(n).\displaystyle {f_{h}(n) = u_{1}(n) + u_{2}(n) + ... + u_{s}(n)}. 其中, ui(n)=(ci0+ci1n+ci2n2+...+ciw1nw1)tinu_{i}(n) = (c_{i_{0}} + c_{i_{1}}n + c_{i_{2}}n^{2} + ... + c_{i_{w - 1}}n^{w - 1})t_{i}^{n}, ww 是根 tit_{i} 的重複次數, i=1,2,...,si = 1, 2, ..., s.

這個定理我們暫時不進行證明.

例題 1. 解二階齊次線性遞迴方程式 F(n)={0n=01n=1F(n1)+F(n2)n>1.\displaystyle {F(n) = \begin {cases} 0 & {n = 0} \\ 1 & {n = 1} \\ F(n - 1) + F(n - 2) & {n > 1}. \end {cases}} 這個遞迴方程式是非常有名的費氏數列 (Fibonacci number sequence).

:

設其通解為 Fh(n)=AxnF_{h}(n) = Ax^{n}, 其中 A0A \neq 0, 將 Fh(n)F_{h}(n) 代入上式得到其特徵方程式 x2x1=0.\displaystyle {x^{2} - x - 1 = 0}. 解得 x1=52+12,x2=52+12x_{1} = -\frac {\sqrt {5}}{2} + \frac {1}{2}, x_{2} = \frac {\sqrt {5}}{2} + \frac {1}{2}. 每個根僅重複一次, 則 w=1w = 1. 故 u1(n)=c1(52+12)n,u2(n)=c2(52+12)n.\displaystyle {u_{1}(n) = c_{1}\left ( -\frac {\sqrt {5}}{2} + \frac {1}{2} \right )^{n}, u_{2}(n) = c_{2}\left ( \frac {\sqrt {5}}{2} + \frac {1}{2} \right )^{n}}. 因此, F(n)=F(n1)+F(n2)F(n) = F(n - 1) + F(n - 2) 的通解為 Fh(n)=u1(n)+u2(n)=c1(52+12)n+c2(52+12)n.\displaystyle {F_{h}(n) = u_{1}(n) + u_{2}(n) = c_{1}\left ( -\frac {\sqrt {5}}{2} + \frac {1}{2} \right )^{n} + c_{2}\left ( \frac {\sqrt {5}}{2} + \frac {1}{2} \right )^{n}}. 考慮 F(0)=0,F(1)=1F(0) = 0, F(1) = 1, 得到一個方程式組並解這個方程式組可以得到 {F(0)=c1+c2=0F(1)=c1(52+12)+c2(52+12)=1,      {c1=15c2=15.\displaystyle {\begin {cases} F(0) = c_{1} + c_{2} = 0 \\ F(1) = c_{1}\left ( -\frac {\sqrt {5}}{2} + \frac {1}{2} \right ) + c_{2}\left ( \frac {\sqrt {5}}{2} + \frac {1}{2} \right ) = 1, \end {cases} \ \ \ \Rightarrow \ \ \ \begin {cases} c_{1} = -\frac {1}{\sqrt {5}} \\ c_{2} = \frac {1}{\sqrt{5}}. \end {cases}}

故費氏數列的通項公式可以表示為 F(n)=15(1+52)n15(152)n\displaystyle {F(n) = \frac {1}{\sqrt {5}}\left ( \frac {1 + \sqrt {5}}{2} \right )^{n} - \frac {1}{\sqrt {5}}\left ( \frac {1 - \sqrt {5}}{2} \right )^{n}}

\blacksquare

目前, 我們僅得到了齊次線性遞迴方程式的求解方法, 對於 g(n)0g(n) \neq 0 的情況, 我們還需要得到一個特解 fp(n)f_{p}(n). 對於任意 g(n)=0g(n) = 0, 目前還沒有一個適用於任意 g(n)g(n) 的特解 fp(n)f_{p}(n). fp(n)f_{p}(n) 的形式取決於 g(n)g(n). 然而 g(n)g(n) 的樣式可以是多種多樣的, 此處我們僅考慮兩種形式 : g(n)g(n) 是關於 nn 的多項式及 g(n)g(n) 是關於 nn 的指數函數.

首先, 當 g(n)=0g(n) = 0 時, f(n)f(n) 的特解 fp(n)=0f_{p}(n) = 0; 當 g(n)=i=0deinig(n) = \sum \limits_{i = 0}^{d}e_{i}n^{i}, 其中 ed0e_{d} \neq 0, 那麼特解 fp(n)f_{p}(n) 有如下形式 fp(n)=p0+p1n+p2n2+...+pd+mnd+m.\displaystyle {f_{p}(n) = p_{0} + p_{1}n + p_{2}n^{2} + ... + p_{d + m}n^{d + m}}. 其中, mm 的值取決於 f(n)f(n) 對應的齊次線性遞迴方程式的特徵方程式的解. 如果 r=1r = 1 時特徵方程式的解, 那麼 mm 的值時根 r=1r = 1 的重複次數; 如果 r=1r = 1 不是特徵方程式的解, 則 m=0m = 0.

由於 fp(n)f_{p}(n)f(n)f(n) 的一個特解, 為了確定 p0,p1,...,pd+mp_{0}, p_{1}, ..., p_{d + m} 的值, 我們將 fp(n)f_{p}(n) 代入 f(n)f(n) 中, 得到 fp(n)=p0+p1n+p2n2+...+pd+mnd+m=a1(p0+p1(n1)+p2(n1)2+...+pd+m(n1)d+m) +     a2(p0+p1(n2)+p2(n2)2+...+pd+m(n2)d+m) +     ... +     ak(p0+p1(nk)+p2(nk)2+...+pd+m(nk)d+m)+g(n).\displaystyle {\begin {aligned} f_{p}(n) &= p_{0} + p_{1}n + p_{2}n^{2} + ... + p_{d + m}n^{d + m} \\ &= a_{1}(p_{0} + p_{1}(n - 1) + p_{2}(n - 1)^{2} + ... + p_{d + m}(n - 1)^{d + m}) \ + \\ &\ \ \ \ \ a_{2}(p_{0} + p_{1}(n - 2) + p_{2}(n - 2)^{2} + ... + p_{d + m}(n - 2)^{d + m}) \ + \\ &\ \ \ \ \ ... \ + \\ &\ \ \ \ \ a_{k}(p_{0} + p_{1}(n - k) + p_{2}(n - k)^{2} + ... + p_{d + m}(n - k)^{d + m}) + g(n). \end {aligned}} 觀察等式兩側, 可以得到共計 d+md + m 個關於 pip_{i} (i=1,2,...,d+mi = 1, 2, ..., d + m) 的方程式. 將這些方程式組成一個方程式組, 解得 p1,p2,...,pd+mp_{1}, p_{2}, ..., p_{d + m} 的值即可.

g(n)=cang(n) = ca^{n}, 其中 aacc 為任意常數, a>0a > 0, 那麼特解 fp(n)f_{p}(n) 有如下形式 fp(n)=(p0+p1n+p2n2+...+pwnw)an.\displaystyle {f_{p}(n) = (p_{0} + p_{1}n + p_{2}n^{2} + ... + p_{w}n^{w})a^{n}}. 其中, ww 的值取決於 f(n)f(n) 對應的齊次線性遞迴方程式的特徵方程式的解. 如果 r=ar = a 是特徵方程式的解, 那麼 ww 的值是根 r=ar = a 的重複次數, 如果 r=ar = a 不是特徵方程式的解, 則 w=0w = 0.

同樣地, 由於 fp(n)f_{p}(n)f(n)f(n) 的一個特解, 為了確定 p1,p2,...,pd+mp_{1}, p_{2}, ..., p_{d + m} 的值, 我們將 fp(n)f_{p}(n) 代入 f(n)f(n) 中, 得到共計 ww 個關於 pip_{i} (i=1,2,...,d+mi = 1, 2, ..., d + m) 的方程式. 將這些方程式組成一個方程式組, 解得 p1,p2,...,pd+mp_{1}, p_{2}, ..., p_{d + m} 的值即可.

自此, 我們得到了使用特徵根法來求解遞迴方程式的過程. 對於線性遞迴方程式 f(n)={c1n=0c2n=1ck1n=k1i=1kgi(n)f(ni)+g(n)nk,\displaystyle {f(n) = \begin {cases} c_{1} & {n = 0} \\ c_{2} & {n = 1} \\ \vdots & {\vdots} \\ c_{k - 1} & {n = k - 1} \\ \sum \limits_{i = 1}^{k}g_{i}(n)f(n - i) + g(n) & {n \geq k}, \end {cases}} 其中 c1,c2,...,ck1,a1,a2,...,akc_{1}, c_{2}, ..., c_{k - 1}, a_{1}, a_{2}, ..., a_{k} 是常數, g(n)g(n) 是關於 nn 的函數而不是關於 ff 的函數. f(n)f(n) 的求解過程如下 :

  1. 對於 nkn \geq k 時的 f(n)f(n), 寫下其特徵方程式 xki=1kaixki=0;\displaystyle {x^{k} - \sum \limits_{i = 1}^{k}a_{i}x^{k - i} = 0};
  2. 求解特徵方程式的互異根 t1,t2,...,tst_{1}, t_{2}, ..., t_{s} (sks \leq k), 並確定任意根 r=tir = t_{i} 的重複次數 jij_{i} (i=1,2,...,s,jiki = 1, 2, ..., s, j_{i} \leq k);
  3. 根據每個根 rir_{i}, 寫下 ui(n)u_{i}(n), 並令 fh(n)=u1(n)+u2(n)+...+us(n).\displaystyle {f_{h}(n) = u_{1}(n) + u_{2}(n) + ... + u_{s}(n)}. 其中, ui(n)=(ci0+ci1n+ci2n2+...+ciw1nw1)tin,i=1,2,...,s,w=jiu_{i}(n) = (c_{i_{0}} + c_{i_{1}}n + c_{i_{2}}n^{2} + ... + c_{i_{w - 1}}n^{w - 1})t_{i}^{n}, i = 1, 2, ..., s, w = j_{i};
  4. 根據給定的 f(0),f(1),...,f(k1)f(0), f(1), ..., f(k - 1) 的值, 計算每一個 ui(n)u_{i}(n) 中的 ci0,ci1,...,ciw1c_{i_{0}}, c_{i_{1}}, ..., c_{i_{w - 1}}. 其中, i=1,2,...,s,w=jii = 1, 2, ..., s, w = j_{i};
  5. 考慮 g(n)g(n) :
    • g(n)=0g(n) = 0, 則 fp(n)=0;\displaystyle {f_{p}(n) = 0};
    • g(n)=i=1deinig(n) = \sum \limits_{i = 1}^{d}e_{i}n^{i}, 其中 ed0e_{d} \neq 0, eie_{i} (i=1,2,...,di = 1, 2, ..., d) 為任意常數. 則 fp(n)=p0+p1n+p2n2+...+pd+mnd+m;\displaystyle {f_{p}(n) = p_{0} + p_{1}n + p_{2}n^{2} + ... + p_{d + m}n^{d + m}};
    • g(n)=cang(n) = ca^{n}, 其中 aacc 為任意常數, a>0a > 0, 則 fp(n)=(p0+p1n+p2n2+...+pwnw)an.\displaystyle {f_{p}(n) = (p_{0} + p_{1}n + p_{2}n^{2} + ... + p_{w}n^{w})a^{n}}. 其中, ww 的值取決於 r=ar = a 是否為特徵方程式的根;
  6. g(n)0g(n) \neq 0, 則將 fp(n)f_{p}(n) 代入 f(n)f(n) 中, 求得 p0,p1,...,pd+mp_{0}, p_{1}, ..., p_{d + m}p0,p1,...,pwp_{0}, p_{1}, ..., p_{w} 的值;
  7. 最終, 線性遞迴方程式 f(n)f(n) 的解為 f(n)=fh(n)+fp(n).\displaystyle {f(n) = f_{h}(n) + f_{p}(n)}.

這七個步驟稱為求解線性遞迴方程式 f(n)f(n)特徵根法 (characteristic root method).

斷言 1. 通過特徵根法的七個步驟找到的 f(n)=fh(n)+fp(n)f(n) = f_{h}(n) + f_{p}(n) 是線性遞迴方程式 f(n)f(n) 的惟一解.

這個斷言我們暫時不進行證明.

3. 一些非線性情形

某些非線性遞迴方程式也可以通過適當的變換, 將其轉化為線性遞迴方程式, 再利用特徵根法進行求解. 考慮 fc(n)=i=1kaifc(ni)+g(n),\displaystyle {f^{c}(n) = \sum \limits_{i = 1}^{k}a_{i}f^{c}(n - i) + g(n),} 其中 nkn \geq k, cc 為任意常數. 我們記 q(n)=fc(n)q(n) = f^{c}(n), 則有 q(n)=i=1kaiq(ni)+g(n).\displaystyle {q(n) = \sum \limits_{i = 1}^{k}a_{i}q(n - i) + g(n)}. 此時, 非線性的 fc(n)f^{c}(n) 就轉化為了線性的 q(n)q(n).

另外, 某些線性遞迴方程式可能具有非恆定的係數 : nf(n)=i=1kaif(ni)+g(n),\displaystyle {nf(n) = \sum \limits_{i = 1}^{k}a_{i}f(n - i) + g(n)}, 其中 nkn \geq k. 我們無法直接使用特徵根法進行求解, 但也可以作適當的變換, 使其具有恆定係數. 記 q(n)=nf(n)q(n) = nf(n), 則有 q(n)=i=1kaiq(ni)+g(n).\displaystyle {q(n) = \sum \limits_{i = 1}^{k}a_{i}q(n - i) + g(n)}. 在這樣的情況下, 我們得到的是關於 q(n)q(n) 的通解, 此時只需將 q(n)q(n) 使用 f(n)f(n) 進行替換, 即可得到原遞迴方程式的通解.