線性常係數齊次遞推關係

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

基本介紹

• 中文名：線性常係數齊次遞推關係
• 套用學科：組合數學 

定義

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^k+C₁x^k-1+...+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^k-1)α₁ⁿ

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

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

共軛復根情況

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

a_n=Aρⁿcosnθ+Bρⁿsinnθ

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