Aritalab:Lecture/Basic/Reccurrence

一般解

ここでは以下の漸化式の一般解を考えます。

a_n T_n = b_n T_n-1 + c_n

この式を解くには、邪魔な数列 a_n, b_n を除くため

s_n = (a_n-1 a_n-2 ... a₀) / (b_n b_n-1 ... b₁)

という数列を導入します。これを和の因子 (summation factor) といいます。ここで s₀ = 1 とします。 つまり

s₀ = 1

s₁ = a₀ / b₁

s₂ = s₀ a₁ / b₂ = (a₀ a₁) / (b₁ b₂)

s₃ = s₂ a₂ / b₃ = (a₀ a₁ a₂) / (b₁ b₂ b₃)

です。 漸化式の両辺に s_n をかけてみます。

s_n a_n T_n = s_n b_n T_n-1 + s_n c_n

= s_n-1 a_n-1 T_n-1 + s_n c_n

ここで S_n = s_n a_n T_n とおきます。

S_n = S_n-1 + s_n c_n

= s₀ a₀ T₀ + Σⁿ_k=1 s_k c_k

= s₁ b₁ T₀ + Σⁿ_k=1 s_k c_k

これから、はじめの漸化式は

T_n = (1 / s_n a_n) ( s₁ b₁ T₀ + Σⁿ_k=1 s_k c_k)

と書けることがわかります。

確認のため、 n = 1 を代入してみると

T₁ = (1 / s₁ a₁) ( s₁ b₁ T₀ + s₁ c₁) = (1 / a₁)(b₁ T₀ + c₁)

となり正しい結果になりました。