漸化式の母関数解法

初めに

$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$は定数)