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

方針 母関数 $A(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n$ と、漸化式の係数 $b_k=k$ の母関数 $B(x)={\sum }_{k=1}^{\infty }k{x}^k$ を使います。漸化式の右辺は畳み込みの形なので、母関数の積で表せます。

1. $B(x)$ を求める $|x|<1$ で $\frac{1}{1-x}={\sum }_{k=0}^{\infty }{x}^k$ です。両辺を項別微分すると $\frac{1}{(1-x{)}^2}={\sum }_{k=1}^{\infty }k{x}^{k-1}$ となり、両辺に $x$ を掛けて $$B(x)=\sum _{k=1}^{\infty }k{x}^k=\frac{x}{(1-x{)}^2}$$ を得ます。

2. 積 $B(x)A(x)$ を計算する 積の $x^n$ の係数は ${\sum }_{k=1}^{n}k{a}_{n-k}$ です（$b_0=0$ なので $k=0$ の項はありません）。$n=0$ の係数は $0$ で、$n\ge 1$ の係数は漸化式から $a_n$ に等しくなります。したがって $$B(x)A(x)=\sum _{n=1}^{\infty }{a}_n{x}^n=A(x)-a_0=A(x)-1$$ です。つまり $A(x)=1+B(x)A(x)$ が成り立ちます。

3. $A(x)$ を解く $A(x)(1-B(x))=1$ より $$A(x)=\frac{1}{1-\frac{x}{(1-x{)}^2}}=\frac{(1-x{)}^2}{(1-x{)}^2-x}=\frac{(1-x{)}^2}{1-3x+x^2}$$ となります。

4. 収束の確認 分母 $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}$ です。$\frac{1}{4}<\frac{3-\sqrt{5}}{2}$ であり、$\frac{1}{4}$ は $B(x)$ の収束域 $|x|<1$ にも入っています。よって $x=\frac{1}{4}$ を代入してかまいません。（参考: $a_0,a_1,a_2,a_3,\cdots =1,1,3,8,21,\dots$ となります。）

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

（別の計算: $B\left(\frac{1}{4}\right)=\frac{1/4}{9/16}=\frac{4}{9}$ なので、$\frac{1}{1-4/9}=\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)$ の積の係数である。したがって $A(x)-1=B(x)A(x)$ が成り立つ。

これより $A(x)=\frac{1}{1-\frac{x}{(1-x{)}^2}}=\frac{(1-x{)}^2}{1-3x+x^2}$。

分母の根は $\frac{3\pm \sqrt{5}}{2}$ で、絶対値が最小の根は $\frac{3-\sqrt{5}}{2}\approx 0.382$ である。これが収束半径なので、$x=\frac{1}{4}<0.382$ では級数は収束する。

$A(1/4)=\frac{(3/4{)}^2}{1-3/4+1/16}=\frac{9/16}{5/16}=\frac{9}{5}$。

検算: $a_0=1$, $a_1=1$, $a_2=1\cdot a_1+2a_0=3$, $a_3=a_2+2a_1+3a_0=8$ と求まり、$a_4=21$ なども続く。部分和は $1+0.25+0.1875+0.125+0.082+0.054+\cdots$ で、約 1.8 に近づく。これは $\frac{9}{5}$ と合う。