$$$$
初めに
$f(x)=\sum_{k=0}^{\infty}A_k x^k$とおくことで色々な漸化式を解くことが出来るらしいです。
z変換チートシート-Qiita
を参考に少し変わった式変形をします。
各項をそれぞれ別々に変換するだけで母関数が得られます。
フィボナッチ数列
$A_{k+2}=A_{k+1}+A_{k}$より、
$\sum_{k=0}^{\infty}A_{k+2}x^k=\sum_{k=0}^{\infty}A_{k+1}x^k+\sum_{k=0}^{\infty}A_{k}x^k$
となるので、
$\frac{f(x)-A_1x-A_0}{x^2}=\frac{f(x)-A_0}{x}+f(x)$
より
$f(x)=\frac{A_0+(A_1-A_0)x}{1-x-x^2}$
邪魔な項を引いてから項数をあわせるだけです。
カタラン数
$A_0=1,A_{k+1}=\sum_{i=0}^kA_iA_{k-i}$
$\frac{f(x)-1}{x}={f(x)}^2$
が成り立つので
$f(x)=\frac{1-\sqrt{1-4x}}{2x}$
参考
一般化
母関数内の各項について、その項を$g(k)$とすると、$\sum_{k=0}^{\infty}g(k)x^k$が求まれば良さそうだとわかります。
これには、テイラー展開や級数の公式が適用できて嬉しいです。
自分が昔書いた記事ですが、
【競技プログラミング】形式的冪級数(多項式)を係数倍するテク-Qiita
も参考にしてみて下さい。
ランベルトのW関数 - wikipedia
Lagrange inversion theorem - wikipedia
なども使えそうです。
これだけで大学入試程度なら瞬殺だと思います。
無限に有る公式の一部
- $\sum_{k=0}^{\infty}A_{k+1} x^k=\frac{(f(x)-A_0)}{x}$
- $\sum_{k=0}^{\infty}A_{k+2} x^k=\frac{f(x)-A_1x-A_0}{x^2}$
- $\sum_{k=0}^{\infty}A_{k+s} x^k=\frac{f(x)-\sum_{i=0}^sA_ix^i}{x^s}$
- $\sum_{k=0}^{\infty}kA_{k} x^k=xf'(x)$
- $\sum_{k=0}^{\infty}k^2A_{k} x^k=xf'(x)+x^2f''(x)$
- $\sum_{k=0}^{\infty}k^sA_{k} x^k=\sum_{t=0}^sS(s,t)x^tf^{(t)}(x)$($S(s,t)$は
第二スターリング数
)
- $\sum_{k=0}^{\infty}x^k=\frac{1}{1-x}$
- $\sum_{k=0}^{\infty}a^k x^k=\frac{1}{1-ax}$
- $\sum_{k=0}^{\infty}k x^k=\frac{x}{(1-x)^2}$
- $\sum_{k=0}^{\infty}k^2 x^k=\frac{x(x+1)}{(1-x)^3}$
- $\sum_{k=0}^{\infty}k^3 x^k=\frac{x(x^2+4x+1)}{(1-x)^4}$
- $\sum_{k=0}^{\infty}k^s x^k=\frac{A_s(x)x}{(1-x)^{n+1}}$(ただし$A_s(x)$は
オイラリアン数
)
- $\sum_{k=0}^{\infty}k^{-1}x^k=-log(1-x)(=Li_1(x))$
- $\sum_{k=0}^{\infty}k^{-s}x^k=Li_s(x)$(ただし、$Li_s(x)$は
多重対数関数
)
- $\sum_{k=0}^{\infty}\frac{1}{k!}x^k=e^x$
- $\sum_{k=0}^{\infty}\frac{k^s}{k!}x^k=\sum_{t=0}^sS(s,t)x^te^x$
etc...
演習問題
- $n$項間漸化式$\sum_{k=0}^{n}C_kA_k=0$の母関数を求めなさい。($C_k$は定数)
- $A_{k+1}=k^2A_k+a^k$の母関数を求めなさい。($a$は定数)