V: 連立漸化式 system of recurrent formulae.
an+1 = pan + qbn … (1)
bn+1 = ran + sbn … (2).
i) 対称形: p = s, q = r の時
辺々の和と差を作る
⇒
an+1 + bn+1 = (p + q)(an + bn),
an+1 - bn+1 = (p - q)(an - bn).
(これらは等比数列)
ii) an+2 - (p + s)an+1 + (ps - qr)an = 0,
bn+2 - (p + s)bn+1 + (ps - qr)bn = 0.
(これらは type III)
iii) {xan + ybn} が公比 t の等比数列になるように, x, y, t を定める。
解説
ii) (1) の番号を 1 上げたものに (2) を代入する
an+2 = pan+1 + qbn+1
= pan+1 + q(ran + sbn)
= pan+1 + qran + sqbn … ここに (1) を qbn
について解いたものを代入
= pan+1 + qran + s(an+1 - pan)
= (p + s)an+1 - (ps - qr)an.
bn の方も同様。
実は ii) は二次正方行列の Cayley-Hamilton (ケーレー・ハミルトン) の公式そのものである。 というのは実は (1), (2) は
と書けるからで, 
と置くと xn+1 = Axn, xn+2
= Axn+1 = A2xn であり, Cayley-Hamilton
の公式から A2 - (p + s)A + (ps - qr)I2 = 0, I2
は二次の単位行列, と書けるから, この式を vector xn
に左から掛ければ
A2xn - (p + s)Axn + (ps - qr)xn = 0
即ち
xn+2 - (p + s)xn+1 + (ps - qr)xn = 0.
成分に分けて書けば上記そのものである。
iii) xan+1 + ybn+1 = t(xan + ybn), x ≠ 0, y ≠ 0 と置く。
lhs = x(pan + qbn) + y(ran + sbn) = (px + ry)an + (qx + sy)bn.
よって
px + ry = tx,
qx + sy = ty
⇔
(t - p)x - ry = 0,
-qx + (t - s)y = 0.
⇔
これが x = y = 0 以外の解を持つための必要十分条件は
であることが知られている (このとき連立している二つの方程式は同じ方程式を表すようになる)。 尚, この方程式を行列 A (上記参照) の固有方程式 proper equation, Eigengleichung といい, その解を固有値 eingenvalue という。
さて, t が求まれば, x, y も適当に定めることが出来ることが知られていて,
xian+1 + yibn+1 = tin-1(xia1 + yib1), i = 1, 2
となる (t が重解の時は i = 1 だけ)。
t が重解でない ⇒ (x1, y1) ≠ (x2, y2)
(ここの表現は一寸ごまかしてある) だから二式から解ける。
t が重解 ⇒ an については (1) より
y1an+1 + (qx1 + py1)an =
tin-1(x1a1 + y1b1)
… type II'
例題
(1) a1 = 1, b1 = 0,
an+1 = 2an + 3bn,
bn+1 = 3an + 2bn.
(2) x1 = 1, y1 = 0,
xn+1 = 2xn + 6yn,
yn+1 = 3xn + 5yn.
解
(1) 辺々の和と差を作ると
an+1 + bn+1 = 5(an + bn),
an+1 - bn+1 = -(an - bn).
従って
an + bn = 5n-1(a1 + b1)
= 5n-1,
an - bn = (-1)n-1(a1 - b1)
= (-1)n-1.
故に
an = (5n-1 + (-1)n-1)/2,
bn = (5n-1 - (-1)n-1)/2.
(2) xn+2 = 2xn+1 + 6yn+1 = 2xn+1 +
6(3xn + 5yn)
= 2xn+1 + 18xn + 5・6yn
= 2xn+1 + 18xn + 5(xn+1 - 2xn)
= 7xn+1 - 8xn.
xn+2 - 7xn+1 + 8xn = 0 … type III.
t2 - 7t + 8 = (t - 8)(t + 1) = 0 より t = 8, -1.
故に先ず
xn+2 - 8xn+1 = -(xn+1 - 8xn).
∴xn+1 - 8xn = (-1)n-1(x2 - 8x1)
= (-1)n-1(2 - 8) = 6・(-1)n … (1)
(∵x2 = 2x1 + 6y1)
次に又
xn+2 + xn+1 = 8(xn+1 + xn)
∴xn+1 + xn = 8n-1(x2 + x1) = 3・8n-1 … (2)
(2) - (1):
9xn = 3・8n-1 - 6・(-1)n.
∴xn = (8n-1 - 2・(-1)n)/3.
∴yn = (xn+1 - 2xn)/6 = (8n -
2・(-1)n+1 - 2・8n-1 + 4・(-1)n)/(6・3)
= (8・8n-1 - 2・8n-1 + 2・(-1)n + 4・(-1)n)/(6・3)
= (6・8n-1 + 6・(-1)n)/(6・3)
= (8n-1 + (-1)n)/3.
[別解]
{αxn + βyn} が公比 k の等比数列になるとする。 即ち
αxn+1 + βyn+1 = k(αxn + βyn), α ≠ 0, β ≠ 0.
lhs = α(2xn + 6yn) + β(3xn + 5yn)
= (2α + 3β)xn + (6α + 5β)yn.
従って
2α + 3β = αk,
6α + 5β = βk.
上の式を β 倍し, 下の式を α 倍すると
αβk = 2αβ + 3β2 = 6α2 + 5αβ.
∴6α2 + 3αβ - 3β2 = 3(2α2 + αβ - β2)
= 3(2α - β)(α + β) = 0.
∴β = 2α, -α.
(比率だけが必要なので) (α, β) = (1, 2), (1, -1) として良い。
i) (α, β) = (1, 2) の場合。
k = 2 + 6 = 8.
∴xn + 2yn = 8n-1(x1 + 2y1) = 8n-1.
ii) (α, β) = (1, -1) の場合。
k = 2 - 3 = -1.
∴xn - yn = (-1)n-1(x1 - y1) = (-1)n-1.
あとは i), ii) の結果を連立させれば
xn = (8n-1 - 2・(-1)n)/3
yn = (8n-1 + (-1)n)/3.
練習
(1) a1 = 1, b1 = 0,
an+1 = (2an + bn)/3,
bn+1 = (an + 2bn)/3.
(2) a1 = 1, b1 = 2,
an+1 = 3an + 4bn,
bn+1 = 2an + bn.
答
(1) an = (1 + 1/3n-1)/2,
bn = (1 - 1/3n-1)/2.
(2) an = 2・5n-1 + (-1)n,
bn = 5n-1 + (-1)n-1.
参考
ここは行列を知らない人は読んでも分からない。
上記 ii) の様にして xn = An-1x1 であるから,
実は行列の n 乗が分かれば連立漸化式はすぐに解ける。
逆に連立漸化式で 
としたものと, 
としたものを考えれば, 
となっている。
今やっていることは 「漸化式→行列の n 乗」 だけれども, 線型代数学としては 「行列の n 乗→漸化式」 である。
又 ii) の逆も言える。 つまり type III → type V. というのは
an+2 = -(r/p)an - (q/p)an+1 だから bn = an+1 と置くことにより
と出来るからである。 このことはもっと一般的に言えるのだが, ここではここまでにしておく。