漸化式の母関数解法

初めに

$f(x)=\sum _{k=0}^{\mathrm{\infty }}{A}_k{x}^k$とおくことで色々な漸化式を解くことが出来るらしいです。
z変換チートシート-Qiita を参考に少し変わった式変形をします。
各項をそれぞれ別々に変換するだけで母関数が得られます。

フィボナッチ数列

$A_{k+2}=A_{k+1}+A_k$より、
$\sum _{k=0}^{\mathrm{\infty }}{A}_{k+2}{x}^k=\sum _{k=0}^{\mathrm{\infty }}{A}_{k+1}{x}^k+\sum _{k=0}^{\mathrm{\infty }}{A}_k{x}^k$
となるので、
$\frac{f(x)-A_{1}x-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}^k{A}_i{A}_{k-i}$
$\frac{f(x)-1}{x}={f(x)}^2$
が成り立つので
$f(x)=\frac{1-\sqrt{1-4x}}{2x}$
参考

一般化

母関数内の各項について、その項を$g(k)$とすると、$\sum _{k=0}^{\mathrm{\infty }}g(k)x^k$が求まれば良さそうだとわかります。
これには、テイラー展開や級数の公式が適用できて嬉しいです。
自分が昔書いた記事ですが、
【競技プログラミング】形式的冪級数(多項式)を係数倍するテク-Qiita
も参考にしてみて下さい。
ランベルトのW関数 - wikipedia
Lagrange inversion theorem - wikipedia
なども使えそうです。
これだけで大学入試程度なら瞬殺だと思います。

無限に有る公式の一部

• $\sum _{k=0}^{\mathrm{\infty }}{A}_{k+1}{x}^k=\frac{(f(x)-A_0)}{x}$
• $\sum _{k=0}^{\mathrm{\infty }}{A}_{k+2}{x}^k=\frac{f(x)-A_{1}x-A_0}{x^2}$
• $\sum _{k=0}^{\mathrm{\infty }}{A}_{k+s}{x}^k=\frac{f(x)-\sum _{i=0}^s{A}_i{x}^i}{x^s}$
• $\sum _{k=0}^{\mathrm{\infty }}k{A}_k{x}^k=x{f}^{\prime }(x)$
• $\sum _{k=0}^{\mathrm{\infty }}{k}^2{A}_k{x}^k=x{f}^{\prime }(x)+x^2{f}^{″}(x)$
• $\sum _{k=0}^{\mathrm{\infty }}{k}^s{A}_k{x}^k=\sum _{t=0}^{s}S(s,t)x^t{f}^{(t)}(x)$($S(s,t)$は 第二スターリング数 )
• $\sum _{k=0}^{\mathrm{\infty }}{x}^k=\frac{1}{1-x}$
• $\sum _{k=0}^{\mathrm{\infty }}{a}^k{x}^k=\frac{1}{1-ax}$
• $\sum _{k=0}^{\mathrm{\infty }}k{x}^k=\frac{x}{(1-x{)}^2}$
• $\sum _{k=0}^{\mathrm{\infty }}{k}^2{x}^k=\frac{x(x+1)}{(1-x{)}^3}$
• $\sum _{k=0}^{\mathrm{\infty }}{k}^3{x}^k=\frac{x(x^2+4x+1)}{(1-x{)}^4}$
• $\sum _{k=0}^{\mathrm{\infty }}{k}^s{x}^k=\frac{A_s(x)x}{(1-x{)}^{n+1}}$(ただし$A_s(x)$は オイラリアン数 )
• $\sum _{k=0}^{\mathrm{\infty }}{k}^{-1}{x}^k=-log(1-x)(=L{i}_1(x))$
• $\sum _{k=0}^{\mathrm{\infty }}{k}^{-s}{x}^k=L{i}_s(x)$(ただし、$L{i}_s(x)$は 多重対数関数 )
• $\sum _{k=0}^{\mathrm{\infty }}\frac{1}{k!}{x}^k=e^x$
• $\sum _{k=0}^{\mathrm{\infty }}\frac{k^s}{k!}{x}^k=\sum _{t=0}^{s}S(s,t)x^t{e}^x$
  etc...

演習問題

• $n$項間漸化式$\sum _{k=0}^n{C}_k{A}_k=0$の母関数を求めなさい。($C_k$は定数)
• $A_{k+1}=k^2{A}_k+a^k$の母関数を求めなさい。($a$は定数)