next up previous
次: 生成関数 上: 生成関数の方法 前: 生成関数の方法

二つの入試問題

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

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

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

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

例 1.6.1       [00横浜国立大学]

数列 $\{ a_n \}$

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

で定める.次の問いに答えよ.
  1. $a_1,\ a_2,\ a_3$ を求めよ.
  2. $a_n$ を求めよ.

例 1.6.2       [98北大後期理系]

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

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

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

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

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

耕一はい.

解答[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{displaymath}
\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}\end{displaymath}

これから

\begin{displaymath}
a_n=\dfrac{1}{(n-1)!}
\end{displaymath}

と推測される. 数学的帰納法で示す.
$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$ のときも成立し,

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

が示せた.□



Aozora Gakuen