離散数学・組合せ論の問題

母関数の関係式. $K(x)={\sum }_{k\ge 1}{k}^2{x}^k$ とおく。${\sum }_{k\ge 0}{x}^k=\frac{1}{1-x}$ に $x\frac{d}{dx}$ を $2$ 回作用させると
$$\sum _{k\ge 1}k{x}^k=\frac{x}{(1-x{)}^2},K(x)=\sum _{k\ge 1}{k}^2{x}^k=\frac{x(1+x)}{(1-x{)}^3}(|x|<1).$$
漸化式は「$n\ge 1$ で $a_n$ は $(k^2)$ と $(a_m)$ のたたみ込み」なので、形式的に $A(x)=\sum a_n{x}^n$ とおくと $A(x)=1+K(x)A(x)$ となる。

$x=\frac{1}{5}$ での値.
$$K\left(\frac{1}{5}\right)=\frac{\frac{1}{5}\cdot \frac{6}{5}}{{\left(\frac{4}{5}\right)}^3}=\frac{6}{25}\cdot \frac{125}{64}=\frac{15}{32}<1.$$

収束の証明. $x=\frac{1}{5}$, $S_N={\sum }_{n=0}^N{a}_n{x}^n$ とおく。$a_n>0$ であり、漸化式から
$$S_N=1+\sum _{n=1}^N\sum _{k=1}^n{k}^2{x}^k{a}_{n-k}{x}^{n-k}\le 1+\left(\sum _{k\ge 1}{k}^2{x}^k\right)S_N=1+\frac{15}{32}{S}_N.$$
よって $S_N\le \frac{32}{17}$ で、$S_N$ は単調増加で有界だから収束する。その極限を $S$ とする。

和の計算. 正項の二重級数なので順序を入れかえてよく、
$$S-1=\sum _{n\ge 1}\sum _{k=1}^n{k}^2{x}^k{a}_{n-k}{x}^{n-k}=\left(\sum _{k\ge 1}{k}^2{x}^k\right)\left(\sum _{m\ge 0}{a}_m{x}^m\right)=\frac{15}{32}S.$$
したがって
$$S=\frac{1}{1-\frac{15}{32}}=\frac{32}{17}.$$

（検算: $a_1=1$, $a_2=1+4=5$, $a_3=5+4+9=18$, $a_4=18+20+9+16=63$ で、部分和 $1+0.2+0.2+0.144+0.1008+\cdots$ は $\frac{32}{17}\approx 1.882$ に近づく。）

答えは $\frac{32}{17}$。

$S(x)={\sum }_{k\ge 1}{k}^2{x}^k=\frac{x(1+x)}{(1-x{)}^3}$ とおく。漸化式より $A(x)=\sum a_n{x}^n$ は $A(x)=1+S(x)A(x)$ を満たすので $A(x)=\frac{1}{1-S(x)}$。$x=1/5$ のとき $S=\frac{(1/5)(6/5)}{(4/5{)}^3}=\frac{6/25}{64/125}=\frac{15}{32}$。よって $A(1/5)=\frac{1}{1-15/32}=\frac{32}{17}$。収束半径は $1-S(x)=0$ すなわち $x^3-2x^2+4x-1=0$ の最小の根の絶対値（約 $0.2956$）で $1/5$ より大きく、収束する。検算: $a_0=1,a_1=1,a_2=1\cdot a_1+4a_0=5,a_3=a_2+4a_1+9a_0=18$ で $1+\frac{1}{5}+\frac{5}{25}+\frac{18}{125}+\cdots =1+0.2+0.2+0.144+\dots$ と増加は緩やかで $32/17\approx 1.882$ に整合する。