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

$A(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n$ とおく（形式的べき級数として扱う）。漸化式の両辺に $x^n$ を掛けて $n\ge 1$ について和をとると
$$\sum _{n=1}^{\infty }{a}_n{x}^n=3\sum _{n=1}^{\infty }{a}_{n-1}{x}^n+\sum _{n=1}^{\infty }{2}^n{x}^n.$$
左辺は $A(x)-a_0=A(x)-2$、右辺第 1 項は $3xA(x)$、第 2 項は $\frac{1}{1-2x}-1=\frac{2x}{1-2x}$ である。よって
$$A(x)-2=3xA(x)+\frac{2x}{1-2x}$$
となり、
$$(1-3x)A(x)=2+\frac{2x}{1-2x}=\frac{2-2x}{1-2x},A(x)=\frac{2-2x}{(1-3x)(1-2x)}.$$
部分分数に分解して $\frac{2-2x}{(1-3x)(1-2x)}=\frac{\alpha }{1-3x}+\frac{\beta }{1-2x}$ とおくと、$2-2x=\alpha (1-2x)+\beta (1-3x)$ である。
- $x=\frac{1}{3}$ を代入すると $\frac{4}{3}=\frac{1}{3}\alpha$ より $\alpha =4$。
- $x=\frac{1}{2}$ を代入すると $1=-\frac{1}{2}\beta$ より $\beta =-2$。

したがって
$$A(x)=\frac{4}{1-3x}-\frac{2}{1-2x}=\sum _{n=0}^{\infty }\left(4\cdot 3^n-2\cdot 2^n\right)x^n$$
となり、係数を比較して
$$a_n=4\cdot 3^n-2^{n+1}.$$
確認: $a_0=4-2=2$、$a_1=3\cdot 2+2=8=12-4$、$a_2=3\cdot 8+4=28=36-8$ で一致する。

$A(x)=2+{\sum }_{n\ge 1}(3a_{n-1}+2^n)x^n=2+3xA(x)+\frac{2x}{1-2x}$。よって $A(x)(1-3x)=2+\frac{2x}{1-2x}=\frac{2}{1-2x}$、すなわち $A(x)=\frac{2}{(1-2x)(1-3x)}$。部分分数分解して $\frac{2}{(1-2x)(1-3x)}=\frac{6}{1-3x}-\frac{4}{1-2x}$。$x^n$ の係数は $a_n=6\cdot 3^n-4\cdot 2^n$。$a_n=2\cdot 3^{n+1}-2^{n+2}$ である。検算: $a_0=6-4=2$、$a_1=18-8=10$。しかし漸化式から $a_1=3\cdot 2+2=8$ となり不一致なので計算を見直す。$\frac{2x}{1-2x}$ は $n\ge 1$ の $2^n{x}^n$ の和であり正しい。$A(1-3x)=2+\frac{2x}{1-2x}=\frac{2(1-2x)+2x}{1-2x}=\frac{2-2x}{1-2x}$ が正しい。よって $A(x)=\frac{2(1-x)}{(1-2x)(1-3x)}=\frac{4}{1-3x}-\frac{2}{1-2x}$（$4(1-2x)-2(1-3x)=2-2x$ で一致）。したがって $a_n=4\cdot 3^n-2\cdot 2^n=4\cdot 3^n-2^{n+1}$。検算: $a_0=4-2=2$、$a_1=12-4=8=3\cdot 2+2$、$a_2=36-8=28=3\cdot 8+4$。