累乗をm個足す漸化式

はじめに

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

2,3個の場合

　2個の時は$a_{n+1}=Aa_n+pX^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}=Aa_n+p_1X_1^n+p_2X_2^n \Longleftrightarrow 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_1a_{n,1}+c_{1,1}X_{1,1}^n+c_{2,1}X_{2,1}^n+\cdots+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+\cdots+\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+\cdots+\frac{c_{m,1}}{X_{1,1}}(\frac{X_{m,1}}{X_{1,1}})^n$
これを
$a_{n+1,2}=A_2a_{n,2}+c_{2,2}X_{2,2}^n+\cdots+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\divsymbol X_{j-1,j-1}$となり、これを繰り返すと 変な形の割り算 でしていた
$$ X_{j,j}=X_j\divsymbol(X_{j-1}\divsymbol(\cdots(X_2\divsymbol X_1)\cdots))=\underset{k=1}{\overset{j}{\huge 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_ma_{n,m}+c_{m,m} \Longleftrightarrow 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}))=\cdots= X_{1,1}^n(\frac{c_1}{X_1-A_1}+X_{2,2}(\cdots(\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}{\huge 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}{\huge 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}$$
です。

最後に

　以上で累乗をm個足す漸化式は終わりです。投稿を見てくださりありがとうございました。