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

方針：漸化式の右辺は、数列 $b_k=k$（$k\ge 1$）と $\{a_n\}$ の畳み込みです。そこで母関数の積で書き直します。

1. 母関数を定める
$$A(x)=\sum _{n=0}^{\infty }{a}_n{x}^n,B(x)=\sum _{k=1}^{\infty }k{x}^k$$
とおきます。$B(x)$ は、$\frac{1}{1-x}={\sum }_{k\ge 0}{x}^k$ を項別微分した $\frac{1}{(1-x{)}^2}={\sum }_{k\ge 1}k{x}^{k-1}$ の両辺に $x$ を掛けて
$$B(x)=\frac{x}{(1-x{)}^2}(|x|<1)$$
です。

2. 漸化式を母関数の積で表す
積 $B(x)A(x)$ の $x^n$ の係数は ${\sum }_{k=1}^{n}k{a}_{n-k}$ です（$B$ に定数項がないので $k=0$ の項はありません）。これは $n\ge 1$ のとき $a_n$ に等しく、$n=0$ のときは $0$ です。一方 $A(x)$ の定数項は $a_0=1$ なので、
$$A(x)=1+B(x)A(x).$$
よって
$$A(x)=\frac{1}{1-B(x)}=\frac{1}{1-\frac{x}{(1-x{)}^2}}=\frac{(1-x{)}^2}{1-3x+x^2}.$$

（確認：$a_1=1,a_2=1\cdot a_1+2a_0=3,a_3=3+2+3=8$ であり、右辺を展開した係数 $1,1,3,8,\dots$ と一致します。）

3. 代入する点が収束の範囲にあることの確認
分母 $1-3x+x^2=0$ の解は $x=\frac{3\pm \sqrt{5}}{2}$ で、原点に近いほうは $\frac{3-\sqrt{5}}{2}\approx 0.382$ です。したがって $A(x)$ の収束半径は $\frac{3-\sqrt{5}}{2}$ 以上であり、$x_0=\frac{1}{4}<0.382$ は収束半径の内側です。また $B\left(\frac{1}{4}\right)=\frac{1/4}{9/16}=\frac{4}{9}<1$ なので $1-B\left(\frac{1}{4}\right)\ne 0$ です。

4. $x=\frac{1}{4}$ を代入する
$$\sum _{n=0}^{\infty }\frac{a_n}{4^n}=A\left(\frac{1}{4}\right)=\frac{{\left(\frac{3}{4}\right)}^2}{1-\frac{3}{4}+\frac{1}{16}}=\frac{\frac{9}{16}}{\frac{5}{16}}=\frac{9}{5}.$$

よって求める値は $\frac{9}{5}$ です。

$A(x)={\sum }_{n\ge 0}{a}_n{x}^n$ とおく。漸化式は $n\ge 1$ で $a_n={\sum }_{k=1}^{n}k{a}_{n-k}$ なので、$B(x)={\sum }_{k\ge 1}k{x}^k=\frac{x}{(1-x{)}^2}$ との積（コーシー積）として $A(x)-1=B(x)A(x)$ と書ける。

よって
$$A(x)=\frac{1}{1-B(x)}=\frac{(1-x{)}^2}{(1-x{)}^2-x}=\frac{(1-x{)}^2}{1-3x+x^2}.$$

分母の零点は $x=\frac{3\pm \sqrt{5}}{2}$ で、最小の絶対値は $\frac{3-\sqrt{5}}{2}\approx 0.382$ である。これは収束半径にあたり、$x=\frac{1}{4}$ はその内側なので収束する。

$x=\frac{1}{4}$ を代入すると
$$A\left(\frac{1}{4}\right)=\frac{(3/4{)}^2}{1-3/4+1/16}=\frac{9/16}{5/16}=\frac{9}{5}.$$

検算: $a_0,\dots ,a_5=1,1,3,8,21,55$ で、部分和は $1+0.25+0.1875+0.125+0.082+0.0537\approx 1.698$ となる。残りの項は公比約 $0.654$ の等比級数で近似でき、約 $0.10$ なので、合計は約 $1.80$ となり $\frac{9}{5}$ と一致する。