線性常係數齊次遞推關係

在這裡介紹一下組合數學問題中求解線性常係數齊次遞推關係時的遇到的三種情況。

基本介紹

• 中文名：線性常係數齊次遞推關係
• 適用領域：組合數學 

定義

a_n+c₁a_n-1+c₂a_n-2+...+c_ka_n-k=0

a₀=d₀,a₁=d₁,...,a_k-1=d_k-1

若c₁,c₂,...,c_k,d₀,d₁,...,d_k-1都是常數，則稱之為k階的線性常係數齊次遞推關係.

特徵多項式

C(x)=x+C₁x+...+C_k-1x+C_k

無重根情況

特徵多項式無重根，k個不同的實數解

C(x)=(x-a₁)(x-a₂)...(x-a_k)

a_n=l₁a₂+l₂a₂+...+l_ka_k

其中，l₁,l₂,...,l_k,是待定係數.

重根情況

有k重根，設α是k重根。

a_n=(A₀+A₁n+...+A_k-1n)α₁

其中，A₁,A₂,...,A_k-1,是待定係數.

為了方便計算，也可以使用以下形式。

共軛復根情況

有一對共軛復根α₁=ρe和α₂=ρe時，

a_n=Aρcosnθ+Bρsinnθ

其中，A,B是待定係數.