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

二つの入試問題

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

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

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

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

例 1.3.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.3.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... ...ac{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)$$

が示せた.□