センター試験・2010年(平成22年)の追試に出題された、漸化式を使って場合の数を求める問題。
問題の前半が場合の数の部分で、後半はただの漸化式の計算になっている。
場合の数の部分のルールが単純なので、考え方をつかむにはいい問題だと思う。後半の計算は面倒だけど。
この手の問題に慣れておくために、前半部分（ア～サ）だけでも解いておこう。
なお、このページで類題を解説してある。

まず樹形図を描いてみよう。
目的は、作業をしながら規則性を見つけるため。なので、下に載せた図は見ずに、まずは自分で描いてみてほしい。その方が理解が早いと思う。

図Ａを見ると、例えば$b_{4}$は４文字目がbである文字列の個数なので、４段目のbの数と言いかえることができる。
この考え方から、以下の解説では
$a_{n}$は$n$段目のaの数 $b_{n}$は$n$段目のbの数 $c_{n}$は$n$段目のcの数 とする。

図Ａより、
$a_{3}$は、３段目のaの数なので、$2$ $b_{3}$は、３段目のbの数なので、$1$ $c_{3}$は、３段目のcの数なので、$1$ $a_{4}$は、４段目のaの数なので、$2$ である。

解答ア：２, イ：１, ウ：１, エ：２

図Ａを作っていると気づくのは、
aの次の段は、bとcひとつずつに分岐 bの次の段は、aとcひとつずつに分岐 cの次の段は、aとbひとつずつに分岐 することだ。当然と言えば当然だけど。

ということは、ある段の
aの数は、一つ上の段のbとcの数の和 bの数は、一つ上の段のaとcの数の和 cの数は、一つ上の段のaとbの数の和 だといえる。

なので、
$a_{n+1}=b_{n}+c_{n}$式Ａ である。

解答オ：２

また、各段のbとcの数は等しいので、
$b_{n}=c_{n}$式Ｂ
より
$b_{n}-c_{n}=0$
とかける。

解答カ：０

次に求めるキクの式
$b_{n}=\displaystyle \frac{\text{キ}}{\text{ク}}a_{n+1}$式Ｃ
は、$a_{n+1}$と$b_{n}$の式だ。
これまでに出てきた式で$a_{n+1}$と$b_{n}$が含まれているのは式Ａなので、これを使う。
だけど、式Ａの項のうち$c_{n}$は式Ｃにないので、式Ｂを使って消そう。

式Ｂを式Ａに代入して、
$a_{n+1}=b_{n}+b_{n}$
より
$a_{n+1}=2b_{n}$式Ａ'
$b_{n}=\displaystyle \frac{1}{2}a_{n+1}$
となる。

解答キ：１, ク：２

さらに、
$d_{n}=a_{n}+b_{n}+c_{n}$式Ｄ
とおくと、右辺は$n$段目のaの数$+$bの数$+$cの数なので、$d_{n}$は$n$段目の文字の個数にあたる。

図Ａより、各段の文字の個数は、
１個からはじまって 次の段は前の段の２倍 である。

よって、$\{d_{n}\}$は、
$d_{1}=1$ $d_{n+1}=2d_{n}$ の等比数列なので、一般項は
$d_{n}=1\cdot 2^{n-1}$
$d_{n}$$=2^{n-1}$式Ｅ
である。

解答ケ：１, コ：２, サ：１

次は$r$だ。
問題文の$r$が含まれている式の
$a_{n+1}=ra_{n}+d_{n}$式Ｆ
は$a_{n+1}$と$d_{n}$の式なので、式Ａ'と式Ｄを使って式Ｆの形をつくって $r$を求める。

式を見比べると、式Ｄの$c_{n}$が邪魔なので、さっきと同じように式Ｂを代入して消そう。
式Ｂを式Ｄに代入して、
$d_{n}=a_{n}+b_{n}+b_{n}$
より
$2b_{n}=-a_{n}+d_{n}$
とかける。

これを式Ａ'に代入して、
$a_{n+1}=-a_{n}+d_{n}$
となる。

解答シ：－, ス：１

ここで、
$A_{n}=r^{-n}a_{n}$式Ｇ
とおいて、式Ｆの$\{a_{n}\}$の漸化式を$\{A_{n}\}$の漸化式にする。
今回は問題文中に$\{A_{n}\}$の漸化式が書いてあるので、この部分は計算しなくていい。
けれど、自分で計算しないといけないこともあるから、解説しておく。

$\{a_{n}\}$の漸化式を$\{A_{n}\}$の漸化式にするということは、式Ｆの
$a_{n+1}$，$a_{n}$を消して $A_{n+1}$，$A_{n}$をつくる ということだ。
こういうときは、代入するのが楽。
$a_{n}$を消して$A_{n}$をつくるから、$a_{n}$と$A_{n}$が含まれている式を使う。
つまり、式Ｇだ。

$r^{-n}$をそのまま使ってもいいんだけど、$-n$乗ってのは混乱する人もいるだろうから、ここでは式Ｇを
$A_{n}=\displaystyle \frac{a_{n}}{r^{n}}$
と変形してから計算する。

この式の両辺に$r^{n}$をかけて、
$a_{n}=r^{n}A_{n}$式Ｇ'
$n$に$n+1$を代入して、
$a_{n+1}=r^{n+1}A_{n+1}$式Ｇ''

式Ｇ'，式Ｇ''を式Ｆに代入して、
$r^{n+1}A_{n+1}=r\cdot r^{n}A_{n}+d_{n}$
より
$r^{n+1}A_{n+1}=r^{n+1}A_{n}+d_{n}$
とかける。

$r^{n+1} \neq 0$なので、この式の両辺を$r^{n+1}$で割ると、
$A_{n+1}=A_{n}+\displaystyle \frac{d_{n}}{r^{n+1}}$式Ｈ
$A_{n+1}$$=A_{n}+r^{-(n+1)}d_{n}$
$A_{n+1}$$=A_{n}+r^{-n-1}d_{n}$
となって、問題文中の式ができる。

この式Ｈを使って、$\{A_{n}\}$の一般項$A_{n}$を求める。
まず、邪魔な$d_{n}$を消そう。
式Ｅを式Ｈに代入して、
$A_{n+1} \displaystyle=A_{n}+\frac{2^{n-1}}{r^{n+1}}$式Ｈ'
となるけど、これは漸化式の基本の形の３つめだ。

せっかくだから漸化式の基本の形の復習をしよう。

復習

漸化式の基本の形は４つあって、
$a_{n+1}=a_{n}+d$ ： 公差$d$の等差数列 $a_{n+1}=ra_{n}$ ： 公比$r$の等比数列 $a_{n+1}=a_{n}+f(n)$ ： 階差数列の一般項が$f(n)$ $a_{n+1}=pa_{n}+q$ ： 特性方程式を使って解く だった。

式Ｈ'は、復習の３番目のパターン。
なので、$\{A_{n}\}$の階差数列の一般項が
$\displaystyle \frac{2^{n-1}}{r^{n+1}}$
だ。

この式は分母と分子で指数が違って面倒なので、そろえよう。
$\displaystyle \frac{2^{n-1}}{r^{n+1}}=\frac{2^{n-1}}{r^{n-1+2}}$
        $=\displaystyle \frac{2^{n-1}}{r^{n-1}\cdot r^{2}}$式Ｉ
だけど、$r=-1$より$r^{2}=1$なので、この式は
$\displaystyle \frac{2^{n-1}}{r^{n+1}}=\frac{2^{n-1}}{r^{n-1}}$
        $=\displaystyle \left(\frac{2}{r}\right)^{n-1}$
とかける。

アドバイス

作りたいセ～タの式に$r^{n-1}$があるので、式Ｉの$r^{n-1}$の部分には$r=-1$を代入しなかった。

これが$\{A_{n}\}$の階差数列の一般項だ。

また、$A_{1}$は、式Ｇに$n=1$を代入して、
$A_{1}=r^{-1}a_{1}$
となるけど、$r=-1$，$a_{1}=1$なので、
$A_{1}=-1^{-1}\cdot 1$
$A_{1}$$\displaystyle=\frac{1}{-1}$
$A_{1}$$=-1$
である。

ここで、階差数列について復習をしておくと、

復習

$\{a_{n}\}$の階差数列が$\{b_{n}\}$のとき、$\{a_{n}\}$の一般項$a_{n}$は、$\{b_{n}\}$の一般項$b_{n}$を使って、
$a_{n}=a_{1}+\displaystyle \sum_{k=1}^{n-1}b_{k} \hspace{30px} (2\leqq n)$
とかける。

以上から、$2\leqq n$のとき、$\{A_{n}\}$の一般項$A_{n}$は、
$A_{n}=-1+\displaystyle \sum_{k=1}^{n-1}\left(\frac{2}{r}\right)^{k-1}$
となるので、これを式Ｇ'に代入して、$2\leqq n$のとき、$a_{n}$は
$\displaystyle a_{n}=r^{n}\left\{-1+\sum_{k=1}^{n-1}\left(\frac{2}{r}\right)^{k-1}\right\}$
とかける。

あとは計算だ。
Σの公式を使って、
$\displaystyle a_{n}=r^{n}\left\{-1+\frac{1-\left(\frac{2}{r}\right)^{n-1}}{1-\frac{2}{r}}\right\}$

ちょっと式がややこしいので、整理しよう。
さっきと同じように分母の$r$にだけ$r=-1$を代入して、
$\displaystyle a_{n}=r^{n}\left\{-1+\frac{1-\left(\frac{2}{r}\right)^{n-1}}{1-\frac{2}{-1}}\right\}$

途中式

$a_{n}$$\displaystyle =r^{n}\left\{-1+\frac{1-\left(\frac{2}{r}\right)^{n-1}}{3}\right\}$
$a_{n}$$\displaystyle =r^{n}\left\{-1+\frac{1}{3}-\frac{1}{3}\left(\frac{2}{r}\right)^{n-1}\right\}$
$a_{n}$$\displaystyle =r^{n}\left\{-\frac{2}{3}-\frac{1}{3}\cdot\frac{2^{n-1}}{r^{n-1}}\right\}$

$a_{n}$$\displaystyle=-\frac{2}{3}r^{n}-\frac{r}{3}\cdot 2^{n-1}$
となる

けれど、これではセ～タのマスに入らない。
なので、変形して問題文の式の形にしよう。

項の順番を変え、さらに$r^{n}$を$r \cdot r^{n-1}$にする。
$a_{n}=-\displaystyle \frac{r}{3}\cdot 2^{n-1}-\frac{2}{3}r\cdot r^{n-1}$
この式の$r^{n-1}$以外の$r$に$-1$を代入すると、
$a_{n}=-\displaystyle \frac{-1}{3}\cdot 2^{n-1}-\frac{2}{3}\cdot(-1)\cdot r^{n-1}$
$a_{n}$$\displaystyle=\frac{1}{3}\cdot 2^{n-1}+\frac{2}{3}\cdot r^{n-1}$
となって、問題文の式の形ができる。

これは$n=1$のときも成り立つ。

解答セ：３, ソ：２, タ：２, チ：３