次： 生成関数 上： 生成関数の方法 前： 生成関数の方法

二つの入試問題

耕一 2000年の横浜国立大学の入試問題の別解を見ました.

南海　　 生成関数で解くというものだな.

耕一 はい． それとよく似た問題が98年北海道大学にあります．

南海　　よくしっているな．それぞれを紹介しよう.

例 1.6.1       ［00横浜国立大学］

数列 $\{ a_n \}$ を

$$a_0=1,\ a_n=\sum_{k=1}^n3^ka_{n-k} \quad (n=1,\ 2,\ \cdots)$$

で定める.次の問いに答えよ.

1. $a_1,\ a_2,\ a_3$ を求めよ.
2. $a_n$ を求めよ.

例 1.6.2       ［98北大後期理系］

次の条件で定まる 数列 $\{ a_n \}$ の一般項を求めよ.

$$a_1=1,\ \dfrac{2^n}{n!}=\sum_{k=1}^{n+1}a_ka_{n+2-k}\ \ (n=1,\ 2,\ 3,\ \cdots)$$

南海　　普通は推測して帰納法で解く．

横国大の解答は問題のところにあるがここに再掲載しておこう．．

北大の普通の解答は耕一君に作ってもらおう．

耕一はい．

解答［00横浜国立大学］

1.  

   $$\begin{eqnarray*} a_1&=&3a_0=3\\ a_2&=&3a_1+3^2a_0=18\\ a_3&=&3a_2+3^2a_1+3^3a_0=108 \end{eqnarray*}$$

   
   

2. $a_n=3\cdot6^{n-1}(n=1,\ 2,\ \cdots)$ と推測される. これを数学的帰納法で示す.
   1. $n=1$ のとき， $a_1=3$ より成立.
   2. $n=1,\ 2,\ \cdots,\ m$ で成立するとする. このとき
      
      $$\begin{eqnarray*} a_{m+1}&=&\sum_{k=1}^{m+1}3^ka_{m+1-k}\\ &=&\sum_{k=1}^m3^k... ...^{m+1} \left(\dfrac{2^m-1}{2-1}\right)+3^{m+1}\\ &=&3\cdot6^m \end{eqnarray*}$$
      
      
      よって $n=m+1$ でも成立する.
   3. 以上から $n=1,\ 2,\ \cdots$ に対し $a_n=3\cdot6^{n-1}$ が示された.□

解答［98北大］

$$\begin{array}{lll} n=1 で条件式を使う&2=a_1a_2+a_2a_1 &∴ \... ...4+a_2a_3+a_3a_2+a_4a_1 &∴ \quad a_4=\dfrac{1}{6} \end{array}$$

これから

$$a_n=\dfrac{1}{(n-1)!}$$

と推測される. 数学的帰納法で示す.
$n=1,\ 2,\ 3,\ 4$ では成立した.
$1,\ 2,\ \cdots,\ n-1$ のとき成立するとして， $n$ のときに成り立つことを示せばよい． 条件式は等式であるから，結局条件式の右辺に $1,\ 2,\ \cdots,\ n$ のときの $a_n$ を代入 して計算した結果，条件式の左辺になればよい.

$$\begin{eqnarray*} \sum_{k=1}^{n+1}a_ka_{n+2-k} &=&\sum_{k=1}^{n+1}\dfrac{1}{(k... ...frac{1}{n!}\sum_{r=0}^n{}_n \mathrm{C}_r=\dfrac{2^n}{n!}\ (左辺) \end{eqnarray*}$$

ゆえに $n$ のときも成立し,

$$a_n=\dfrac{1}{(n-1)!}\ \ (n=1,\ 2,\ 3,\ \cdots)$$

が示せた.□