累乗をm個足す漸化式

205

はじめに

　こんにちは、最近漸化式ガチャをやっているn=1です。今回は累乗をm個足す漸化式についてやっていきます。

2,3個の場合

　2個の時は $a_{n + 1} = A a_{n} + p X^{n}$ であれば $X^{n + 1}$ で割り $b_{n} = \frac{a_{n}}{X^{n}}$ とすれば $b_{n + 1} = \frac{A}{X} b_{n} + \frac{p}{X}$ となり解けます。3個の時も同じようにして $a_{n + 1} = A a_{n} + p_{1} X_{1}^{n} + p_{2} X_{2}^{n} ⟺ b_{n + 1} = \frac{A}{X_{1}} b_{n} + \frac{p_{1}}{X_{1}} + \frac{p_{2}}{X_{1}} (\frac{X_{2}}{X_{1}})^{n}$ で2個に定数を足しただけなので $b_{n}$ に $\frac{p_{1}}{A - X_{1}}$ をつければ2個の時と同じになり解けます。

本題

　それでは早速本題に入ります。累乗の和の漸化式は $a_{n + 1, 1} = A_{1} a_{n, 1} + c_{1, 1} X_{1, 1}^{n} + c_{2, 1} X_{2, 1}^{n} + \dots + c_{m, 1} X_{m, 1}^{n}$ とします。これも2,3この場合のように
$\frac{a_{n + 1, 1}}{X_{1, 1}^{n + 1}} = \frac{A_{1}}{X_{1, 1}} \frac{a_{n, 1}}{X_{1, 1}^{n}} + \frac{c_{1, 1}}{X_{1, 1}} + \frac{c_{2, 1}}{X_{1, 1}} (\frac{X_{2, 1}}{X_{1, 1}})^{n} + \dots + \frac{c_{m, 1}}{X_{1, 1}} (\frac{X_{m, 1}}{X_{1, 1}})^{n}$
$\frac{a_{n + 1, 1}}{X_{1, 1}^{n + 1}} + \frac{c_{1, 1}}{A_{1} - X_{1, 1}} = \frac{A_{1}}{X_{1, 1}} (\frac{a_{n, 1}}{X_{1, 1}^{n}} + \frac{c_{1, 1}}{A_{1} - X_{1, 1}}) + \frac{p_{2, 1}}{X_{1, 1}} (\frac{X_{2, 1}}{X_{1, 1}})^{n} + \dots + \frac{c_{m, 1}}{X_{1, 1}} (\frac{X_{m, 1}}{X_{1, 1}})^{n}$
これを
$a_{n + 1, 2} = A_{2} a_{n, 2} + c_{2, 2} X_{2, 2}^{n} + \dots + c_{m, 2} X_{m, 2}^{n}$
とすると最初の式の累乗の和を1つ減らしたようなだけでほぼ同じ形になり、つまり $j$ 回目では $X_{j, j}^{n + 1}$ で割っていて $a_{n, j}$ に $\frac{c_{j, j}}{A_{j} - X_{j, j}}$ を足すことで $a_{n, j + 1}$ にできます。これを繰り返していると毎回 $X_{j, j}^{n + 1}$ で割っているので $X_{j, j}$ は(見やすさのため $X_{j, 1} = X_{j}$ とする)常に分母は $X_{j - 1, j - 1}$ を割っていて
$X_{j, j} = X_{j} \div X_{j - 1, j - 1}$ となり、これを繰り返すと変な形の割り算でしていた
$X_{j, j} = X_{j} \div (X_{j - 1} \div (\dots (X_{2} \div X_{1}) \dots)) = \underset{k = 1}{\overset{j}{N}} X_{j - k + 1}$
であることが分かります。同様にして
$X_{p, q} = \frac{X_{p}}{X_{q - 1, q - 1}}$
$A_{q} = \frac{A_{1}}{X_{q - 1, q - 1}}$
$c_{p, q} = \frac{c_{p}}{X_{q - 1, q - 1}}$
これより $\frac{c_{j, j}}{A_{j} - X_{j, j}} = \frac{c_{j}}{A_{1} - X_{j}}$ なので
$a_{n, j + 1}$ は
$a_{n, j + 1} = \frac{a_{n, j}}{X_{j, j}^{n}} + \frac{c_{j}}{A_{1} - X_{j}}$
これで準備が整いました。
　最終的に
$a_{n + 1, m} = A_{m} a_{n, m} + c_{m, m} ⟺ a_{n + 1, m + 1} = A_{m + 1} a_{n, m + 1}$
$a_{n, m + 1} = a_{1, m + 1} A_{m + 1}^{n - 1}$
上記のようになるので $a_{n, 1}$ を $a_{n, m + 1}$ によって表したいので $a_{n, j}$ を逆に解いて
$a_{n, j} = X_{j, j}^{n} (\frac{c_{j}}{X_{j} - A_{1}} + a_{n, j + 1})$ なので
$a_{n, 1} = X_{1, 1}^{n} (\frac{c_{1}}{X_{1} - A_{1}} + a_{n, 2}) = X_{1, 1}^{n} (\frac{c_{1}}{X_{1} - A_{1}} + X_{2, 2}^{n} (\frac{c_{2}}{X_{2} - A_{1}} + a_{n, 3})) = \dots = X_{1, 1}^{n} (\frac{c_{1}}{X_{1} - A_{1}} + X_{2, 2} (\dots (\frac{c_{m}}{X_{m} - A_{1}} + a_{n, m + 1}))) = a_{n, m + 1} \prod_{k = 1}^{m} X_{k, k}^{n} + \sum_{k = 1}^{m} \frac{c_{k}}{X_{k} - A_{1}} \prod_{j = 1}^{k} X_{j, j}^{n}$
次は $a_{1, m + 1}$ を求め
$a_{1, m + 1} = \frac{c_{m}}{A_{1} - X_{m}} + \frac{1}{X_{m, m}} a_{1, m} = \frac{c_{m}}{A_{1} - X_{m}} + \frac{1}{X_{m, m}} (\frac{c_{m - 1}}{A_{1} - X_{m - 1}} + \frac{1}{X_{m - 1, m - 1}} a_{1, m - 1}) = \frac{c_{m}}{A_{1} - X_{m}} + a_{1} \prod_{k = 1}^{m} X_{k, k}^{- 1} + \sum_{k = 1}^{m - 1} \frac{c_{m - k}}{A_{1} - X_{m - k}} \prod_{j = 1}^{k} X_{m - j + 1, m - j + 1}^{- 1}$
$\prod_{k = 1}^{n} \underset{j = 1}{\overset{k}{N}} f (k - j + 1) = \prod_{k = 1}^{n} f (k)^{\frac{1 + (- 1)^{n - k}}{2}}$ なので、 $a_{n, 1}$ の答えは
$a_{n, 1} = (\frac{c_{m}}{A_{1} - X_{m}} + a_{1} \prod_{k = 1}^{m} X_{k}^{-^{\frac{1 + (- 1)^{n - k}}{2}}} + \sum_{k = 1}^{m - 1} \frac{c_{m - k}}{A_{1} - X_{m - k}} \prod_{j = 1}^{k} X_{m - j + 1, m - j + 1}^{- 1}) (\frac{A_{1}}{\underset{k = 1}{\overset{m}{N}} X_{m - k + 1}})^{n - 1} \prod_{k = 1}^{m} X_{k}^{\frac{1 + (- 1)^{n - k}}{2} n} + \sum_{k = 1}^{m} \frac{c_{k}}{X_{k} - A_{1}} \prod_{j = 1}^{k} X_{j}^{\frac{1 + (- 1)^{k - j}}{2} n}$
です。