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

母関数の方程式を立てる

漸化式の両辺に $x^n$ を掛けて $n\ge 2$ について和をとると
$$\sum _{n\ge 2}{a}_n{x}^n=4x\sum _{n\ge 2}{a}_{n-1}{x}^{n-1}-4x^2\sum _{n\ge 2}{a}_{n-2}{x}^{n-2}+\sum _{n\ge 2}{2}^n{x}^n$$
となる。各項は
$$\sum _{n\ge 2}{a}_n{x}^n=A(x)-1-3x,$$
$$\sum _{n\ge 2}{a}_{n-1}{x}^{n-1}=A(x)-1,$$
$$\sum _{n\ge 2}{a}_{n-2}{x}^{n-2}=A(x),$$
$$\sum _{n\ge 2}{2}^n{x}^n=\frac{1}{1-2x}-1-2x=\frac{4x^2}{1-2x}$$
である。これらを代入すると
$$A(x)-1-3x=4x(A(x)-1)-4x^{2}A(x)+\frac{4x^2}{1-2x}.$$
整理すると
$$(1-4x+4x^2)A(x)=1-x+\frac{4x^2}{1-2x}.$$
$1-4x+4x^2=(1-2x{)}^2$ なので
$$A(x)=\frac{1-x}{(1-2x{)}^2}+\frac{4x^2}{(1-2x{)}^3}.$$

係数を取り出す

一般二項展開
$$\frac{1}{(1-2x{)}^2}=\sum _{m\ge 0}(m+1)2^m{x}^m,\frac{1}{(1-2x{)}^3}=\sum _{m\ge 0}\left(\genfrac{}{}{0ex}{}{m+2}{2}\right)2^m{x}^m$$
を用いる。

第 1 項 $\frac{1-x}{(1-2x{)}^2}$ の $x^n$ の係数は
$$(n+1)2^n-n{2}^{n-1}=2^{n-1}(2n+2-n)=2^{n-1}(n+2)$$
である（$n=0$ のときは $1$ で、この式に一致する）。

第 2 項 $\frac{4x^2}{(1-2x{)}^3}$ の $x^n$ の係数は、$m=n-2$ として
$$4\left(\genfrac{}{}{0ex}{}{n}{2}\right)2^{n-2}=2^n\cdot \frac{n(n-1)}{2}=2^{n-1}n(n-1)$$
である（$n=0,1$ のときは $0$ で、この式に一致する）。

したがって
$$a_n=2^{n-1}(n+2)+2^{n-1}(n^2-n)=2^{n-1}(n^2+2).$$

検算

• $a_0=\frac{1}{2}\cdot 2=1$
• $a_1=1\cdot 3=3$
• 漸化式より $a_2=4\cdot 3-4\cdot 1+4=12$。式では $2\cdot 6=12$ となり一致する。
• 漸化式より $a_3=4\cdot 12-4\cdot 3+8=44$。式では $4\cdot 11=44$ となり一致する。

よって $a_n=2^{n-1}(n^2+2)$。

漸化式 $a_n=4a_{n-1}-4a_{n-2}+2^n$ を、同次解と特殊解に分けて解く。

特性方程式は $t^2-4t+4=0$ で、重解 $t=2$ をもつ。よって同次解は $(A+Bn)2^n$ である。

非同次項 $2^n$ の底 $2$ は特性方程式の重解と一致するので、特殊解を $C{n}^2{2}^n$ とおく。代入して両辺を $2^n$ で割ると
$C{n}^2=2C(n-1{)}^2-C(n-2{)}^2+1=C(n^2-2)+1$
となる。ゆえに $-2C+1=0$ より $C=\frac{1}{2}$。

一般解は $a_n=(A+Bn+\frac{n^2}{2})2^n$ である。

初期条件から係数を決める。
- $a_0=1$ より $A=1$。
- $a_1=3$ より $2(1+B+\frac{1}{2})=3$ なので $B=0$。

よって $a_n=(1+\frac{n^2}{2})2^n=(n^2+2)2^{n-1}$。

母関数を用いる方法でも、$A(x)$ は $(1-2x{)}^{-3}$ などの形に部分分数分解でき、同じ結果になる。

検算:
- 漸化式から $a_2=4\cdot 3-4\cdot 1+4=12$。公式では $(4+2)\cdot 2=12$ で一致する。
- 漸化式から $a_3=4\cdot 12-4\cdot 3+8=44$。公式では $(9+2)\cdot 4=44$ で一致する。
- $n=0,1$ でも公式は $a_0=1,a_1=3$ となり、初期条件に合う。