I: an+1 = pan + q; p, q: 定数
i) p = 1 ⇒ 等差数列
ii) p ≠ 1 ⇒ (1) an+1 - k = p(an - k)
となる定数 k を求める (等比数列へ)。
(2) 番号を一つずらしたものと辺々差を取ると
an+1 - an = p(an - an-1)
(等比数列, 階差数列へ).
I': an+1 = pan + qn + r; p, q, r: 定数
i) an+1 + α(n + 1) + β = p(an + αn + β) となる定数 α, β を求める (等比数列へ)。
ii) 差を取って an+1 - an = p(an - an-1) + q → type I へ。
注: type I' i) は更に一般に
an+1 = pan + f(n) ⇒ an+1 + g(n + 1) = p(an + g(n))
となる g(n) を見つける, と拡張できる。
解説
I ii) (1) もとの漸化式で t = an = an+1 と置くと
t = pt + q ⇔ t = q/(1 - p).
又 an+1 - k = p(an - k) ⇔ an+1 = pan + (1 - p)k より k = q/(1 - p). 従って, 上述の k はもとの漸化式で {an} の全ての項を t と置いたときの t の値に等しい。 この値はもとの漸化式の定める 「不動点 fixed point」 と呼ばれるものである。 従ってこの, 「もとの漸化式で {an} の全ての項を t と置いた」 方程式を 「不動点方程式」 と呼んでおくことにする (私の先生はこれを 「特性方程式」 として教えたが, あとでやるものと紛らわしい上に両方とも同時に出てきたりするので名前を変えておくことにする)。
(2)
注:
I ii) (2), I' (2) は煩雑だから例では扱わない。
例題
(1) a1 = 1, an+1 = 2an + 3.
(2) a1 = 1, 2an+1 = an + 2n - 1.
解
(1) 不動点方程式 t = 2t + 3 より t = -3. よって
an+1 + 3 = 2(an + 3).
ここで bn = an + 3 と置くと,
b1 = a1 + 3 = 1 + 3 = 4,
bn+1 = 2bn.
従って {bn} は初項 4, 公比 2 の等比数列である。 故に
bn = 2n-1・b1 = 2n-1・22 = 2n+1.
よって bn = an + 3 = 2n+1. ∴an = 2n+1 - 3.
(2) 2(an+1 + α(n + 1) + β) = an + αn + β と置く。 整理し直すと
2an+1 = an - αn - 2α - β.
これをもとの漸化式 2an+1 = an + 2n - 1 と比較すると
-α = 2,
-2α - β = -1.
従って α = -2, β = 5. よって今 bn = an - 2n + 5 と置くと
b1 = a1 - 2×1 + 5 = 4 = (1/2)-2,
bn+1 = (1/2)bn.
従って {bn} は初項 4, 公比 1/2 の等比数列である。 故に
bn = (1/2)n-1・b1 = (1/2)n-1・(1/2)-2 = 1/2n-3.
よって bn = an - 2n + 5 = 1/2n-3.
∴an = 1/ 2n-3 + 2n - 5.
練習
(1) a1 = 1, 2an+1 = an - 1.
(2) a1 = 1, an+1 = 3an + 4n - 2.
答
(1) an = 1/2n-2 - 1.
(2) an = 3n - 2n.
cf.
定義の例 7 の漸化式 an = 2an-1 + 4n2 - 1 では上記 「注」 によって
an+1 + α(n + 1)2 + β(n + 1) + γ = p(an + αn2 + βn + γ)
と置いて解く。