第7章　いろいろな漸化式

足す数が $n$ の 1 次式のとき

第6章の最後に予告した漸化式から始めましょう。

$\displaystyle a_1$$\displaystyle {}= 1,$$\displaystyle a_{n+1}$$\displaystyle {}= 2a_n$$\displaystyle {}+ n$

項を書き出すと $1,$$\ 3,$$\ 8,$$\ 19,$$\ 42,$$\ \ldots$ です。「2 倍して足す」形は第6章の $a_{n+1}$${}= pa_n$${}+ q$ に似ていますが、足す数が $1,$$\ 2,$$\ 3,$$\ \ldots$ と番号によって変わるので、落ち着き先 $\alpha$ を 1 つの数として見つけることができません。

そこで、落ち着き先のほうも番号とともに動かしてみます。$n$ の 1 次式 $g(n)$${}= \alpha n$${}+ \beta$ で、もとの漸化式と同じ関係

$\displaystyle g(n + 1)$$\displaystyle {}= 2g(n)$$\displaystyle {}+ n$

を満たすものを探すのです。左辺は $\alpha n$${}+ \alpha$${}+ \beta$、右辺は $(2\alpha + 1)n$${}+ 2\beta$ なので、$n$ の係数と定数項を比べて $\alpha$${}= 2\alpha$${}+ 1$，$\alpha$${}+ \beta$${}= 2\beta$。これを解くと $\alpha$${}= -1,$$\beta$${}= -1$ で、$g(n)$${}= -n$${}- 1$ が見つかります。

$a_{n+1}$${}= 2a_n$${}+ n$ から $g(n + 1)$${}= 2g(n)$${}+ n$ を辺々引くと、$n$ の部分がきれいに消えて

$\displaystyle a_{n+1}$$\displaystyle {}- g(n + 1)$$\displaystyle {}= 2\{a_n - g(n)\}$

となります。$\{a_n - g(n)\}$、つまり $\{a_n + n + 1\}$ は公比 $2$ の等比数列です。

公式1：$a_{n+1}$${}= pa_n$${}+ (n \text{ の 1 次式})$ 型の漸化式

$p,$$\ c,$$\ d$ を定数とし、$p$${}\neq 1$ とする。漸化式 $a_{n+1}$${}= pa_n$${}+ cn$${}+ d$ に対して、$n$ の 1 次式 $g(n)$${}= \alpha n$${}+ \beta$ を

$\displaystyle g(n + 1)$$\displaystyle {}= pg(n)$$\displaystyle {}+ cn$$\displaystyle {}+ d$

がすべての $n$ で成り立つように定める（両辺の $n$ の係数と定数項を比べる）。すると

$\displaystyle a_{n+1}$$\displaystyle {}- g(n + 1)$$\displaystyle {}= p\{a_n - g(n)\}$

となり、数列 $\{a_n - g(n)\}$ は初項 $a_1$${}- g(1)$、公比 $p$ の等比数列である。よって

$\displaystyle a_n$$\displaystyle {}= g(n)$$\displaystyle {}+ \{a_1 - g(1)\}p^{n-1}$

第6章の $\alpha$ は「その場に止まっている落ち着き先」でした。公式1の $g(n)$ は「動いていく落ち着き先」です。

散歩中の犬と飼い主を思い浮かべてください。飼い主は一定の歩幅で道を進み、犬はそのまわりを行ったり来たりしています。道の起点から犬までの距離だけを記録すると、動きは複雑に見えます。ところが、飼い主を基準にして「飼い主から犬までの距離」を測ると、「毎回半分になる」のような単純な規則が見えることがあります。飼い主にあたるのが $g(n)$、飼い主からのずれが $a_n$${}- g(n)$ です。

図は $a_1$${}= 4,$$a_{n+1}$${}= \dfrac{1}{2}a_n$${}+ n$ の例です（例題1(2)）。数列そのものは増えたり減ったりしますが、直線 $g(n)$${}= 2n$${}- 4$ からのずれだけを見ると、毎回ちょうど半分になっています。

$g(n)$ の代わりに、階差をとる方法もあります。$a_{n+2}$${}= pa_{n+1}$${}+ c(n + 1)$${}+ d$ から $a_{n+1}$${}= pa_n$${}+ cn$${}+ d$ を引くと、$b_n$${}= a_{n+1}$${}- a_n$ について $b_{n+1}$${}= pb_n$${}+ c$ となり、第6章の $pa_n$${}+ q$ 型に帰着します（実践 j16）。計算は少し長くなりますが、1 次式を探す必要がありません。

足す数が $n$ の 1 次式のときは、同じ漸化式を満たす 1 次式 $g(n)$（動く落ち着き先）を係数比較で見つけ、$a_n$${}- g(n)$ が等比数列になることを使って解くということです。

例題1：$pa_n$${}+ (n \text{ の 1 次式})$ 型

次の漸化式で定まる数列 $\{a_n\}$ の一般項を求めなさい。

(1) $a_1$${}= 1,$$a_{n+1}$${}= 2a_n$${}+ n$

(2) $a_1$${}= 4,$$a_{n+1}$${}= \dfrac{1}{2}a_n$${}+ n$

---

【解答】

(1) 上で見たとおり、$g(n)$${}= -n$${}- 1$ は $g(n + 1)$${}= 2g(n)$${}+ n$ を満たします。漸化式から辺々引くと

$\displaystyle a_{n+1}$$\displaystyle {}+ (n + 1)$$\displaystyle {}+ 1$$\displaystyle {}= 2(a_n + n + 1)$

数列 $\{a_n + n + 1\}$ は初項 $a_1$${}+ 2$${}= 3$、公比 $2$ の等比数列なので、$a_n$${}+ n$${}+ 1$${}= 3 \cdot 2^{n-1}$ より

$\displaystyle \underline{\rule[-0.15em]{0em}{1.0141em}a_n = 3 \cdot 2^{n-1}}$$\displaystyle \underline{\rule[-0.15em]{0em}{1.0141em}{}- n}$$\displaystyle \underline{\rule[-0.15em]{0em}{1.0141em}{}- 1}$

（$a_2$${}= 3$，$a_3$${}= 8$、式でも $6$${}- 3$${}= 3$，$12$${}- 4$${}= 8$。）

(2) $g(n)$${}= \alpha n$${}+ \beta$ とおき、$g(n + 1)$${}= \dfrac{1}{2}g(n)$${}+ n$ に代入すると

$\displaystyle \alpha n$$\displaystyle {}+ \alpha$$\displaystyle {}+ \beta$$\displaystyle {}= \left(\frac{1}{2}\alpha + 1\right)n$$\displaystyle {}+ \frac{1}{2}\beta$

係数を比べて $\alpha$${}= \dfrac{1}{2}\alpha$${}+ 1$，$\alpha$${}+ \beta$${}= \dfrac{1}{2}\beta$ より $\alpha$${}= 2,$$\beta$${}= -4$、$g(n)$${}= 2n$${}- 4$ です。よって

$\displaystyle a_{n+1}$$\displaystyle {}- \{2(n + 1) - 4\}$$\displaystyle {}= \frac{1}{2}\{a_n - (2n - 4)\}$

数列 $\{a_n - (2n - 4)\}$ は初項 $4$${}- (-2)$${}= 6$、公比 $\dfrac{1}{2}$ の等比数列なので

$\displaystyle \underline{\rule[-0.95em]{0em}{2.6040em}a_n = 2n}$$\displaystyle \underline{\rule[-0.95em]{0em}{2.6040em}{}- 4}$$\displaystyle \underline{\rule[-0.95em]{0em}{2.6040em}{}+ 6\left(\frac{1}{2}\right)^{n-1}}$

（$a_2$${}= 2$${}+ 1$${}= 3$，$a_3$${}= \dfrac{3}{2}$${}+ 2$${}= \dfrac{7}{2}$、式でも $0$${}+ 3$${}= 3$，$2$${}+ \dfrac{3}{2}$${}= \dfrac{7}{2}$。）

足す数が指数のとき：$pa_n$${}+ q^n$ 型

今度は、足す数が $3^n$ のように指数で増えていく場合です。

$\displaystyle a_1$$\displaystyle {}= 2,$$\displaystyle a_{n+1}$$\displaystyle {}= 2a_n$$\displaystyle {}+ 3^n$

1 次式を探す方法は使えません。代わりに、両辺を $3^{n+1}$ で割ってみます。

$\displaystyle \frac{a_{n+1}}{3^{n+1}}$$\displaystyle {}= \frac{2}{3} \cdot \frac{a_n}{3^n}$$\displaystyle {}+ \frac{1}{3}$

$b_n$${}= \dfrac{a_n}{3^n}$ とおくと、これは $b_{n+1}$${}= \dfrac{2}{3}b_n$${}+ \dfrac{1}{3}$ で、第6章の $pa_n$${}+ q$ 型そのものです。割ったことで、邪魔だった $3^n$ が定数 $\dfrac{1}{3}$ に変わりました。

公式2：$a_{n+1}$${}= pa_n$${}+ q^n$ 型の漸化式

$p,$$\ q$ を 0 でない定数とする。漸化式 $a_{n+1}$${}= pa_n$${}+ q^n$ の両辺を $q^{n+1}$ で割り、$b_n$${}= \dfrac{a_n}{q^n}$ とおくと

$\displaystyle b_{n+1}$$\displaystyle {}= \frac{p}{q}\,b_n$$\displaystyle {}+ \frac{1}{q}$

となり、$pa_n$${}+ q$ 型（$p$${}= q$ のときは等差型）に帰着する。また、両辺を $p^{n+1}$ で割り、$c_n$${}= \dfrac{a_n}{p^n}$ とおくと

$\displaystyle c_{n+1}$$\displaystyle {}= c_n$$\displaystyle {}+ \frac{1}{p}\left(\frac{q}{p}\right)^n$

となり、階差型に帰着する。

割り算の意味は、値段の比べ方にたとえられます。物価が毎年 $3$ 倍になる国で、ある人の貯金額を 10 年分並べても、増えたのか減ったのかは分かりにくいでしょう。そこで、各年の金額をその年の物価で割って「今の値段に直すといくら分か」（実質の価値）を見ると、動きが素直に見えてきます。$3^n$ で割るのは、物価の上がり分をならして、数列の本当の動きを取り出すことにあたります。

足す数が $q^n$ のときは、両辺を $q^{n+1}$（または $p^{n+1}$）で割って $\dfrac{a_n}{q^n}$ を新しい数列とみると、$pa_n$${}+ q$ 型（または階差型）になるということです。

例題2：$pa_n$${}+ q^n$ 型

$a_1$${}= 2,$$a_{n+1}$${}= 2a_n$${}+ 3^n$ で定まる数列 $\{a_n\}$ の一般項を求めなさい。

---

【解答】

両辺を $3^{n+1}$ で割り、$b_n$${}= \dfrac{a_n}{3^n}$ とおくと

$\displaystyle b_{n+1}$$\displaystyle {}= \frac{2}{3}b_n$$\displaystyle {}+ \frac{1}{3},$$\displaystyle b_1$$\displaystyle {}= \frac{a_1}{3}$$\displaystyle {}= \frac{2}{3}$

$\alpha$${}= \dfrac{2}{3}\alpha$${}+ \dfrac{1}{3}$ を解くと $\alpha$${}= 1$ で、$b_{n+1}$${}- 1$${}= \dfrac{2}{3}(b_n - 1)$ と変形できます。数列 $\{b_n - 1\}$ は初項 $\dfrac{2}{3}$${}- 1$${}= -\dfrac{1}{3}$、公比 $\dfrac{2}{3}$ の等比数列なので

$\displaystyle b_n$$\displaystyle {}= 1$$\displaystyle {}- \frac{1}{3}\left(\frac{2}{3}\right)^{n-1}$

$a_n$${}= 3^n b_n$ で、$3^n \cdot \dfrac{1}{3}\left(\dfrac{2}{3}\right)^{n-1}$${}= 3^{n-1} \cdot \dfrac{2^{n-1}}{3^{n-1}}$${}= 2^{n-1}$ なので

$\displaystyle \underline{\rule[-0.15em]{0em}{1.0141em}a_n = 3^n}$$\displaystyle \underline{\rule[-0.15em]{0em}{1.0141em}{}- 2^{n-1}}$

（$a_2$${}= 4$${}+ 3$${}= 7$，$a_3$${}= 14$${}+ 9$${}= 23$、式でも $9$${}- 2$${}= 7$，$27$${}- 4$${}= 23$。）

同じ問題を、$2^{n+1}$ で割って解くこともできます。$c_n$${}= \dfrac{a_n}{2^n}$ とおくと $c_{n+1}$${}= c_n$${}+ \dfrac{1}{2}\left(\dfrac{3}{2}\right)^n$、$c_1$${}= 1$ で、階差型です。$n$${}\geqq 2$ のとき

$\displaystyle c_n$$\displaystyle {}= 1$$\displaystyle {}+ \sum_{k=1}^{n-1} \frac{1}{2}\left(\frac{3}{2}\right)^k$$\displaystyle {}= 1$$\displaystyle {}+ \frac{3}{2}\left\{\left(\frac{3}{2}\right)^{n-1} - 1\right\}$$\displaystyle {}= \left(\frac{3}{2}\right)^n$$\displaystyle {}- \frac{1}{2}$

（$n$${}= 1$ でも $\dfrac{3}{2}$${}- \dfrac{1}{2}$${}= 1$）。$a_n$${}= 2^n c_n$${}= 3^n$${}- 2^{n-1}$ と、同じ答えになります。「等比に帰着させるか、階差に帰着させるか」は、第6章と同じく好みで選べます。

分数の形の漸化式

第6章で予告した、分数の形の漸化式です。

$\displaystyle a_1$$\displaystyle {}= 1,$$\displaystyle a_{n+1}$$\displaystyle {}= \frac{a_n}{a_n + 1}$

項は $1,$$\ \dfrac{1}{2},$$\ \dfrac{1}{3},$$\ \dfrac{1}{4},$$\ \ldots$ と続き、$a_n$${}= \dfrac{1}{n}$ が見えます。これを導くには、両辺の逆数をとります。

$\displaystyle \frac{1}{a_{n+1}}$$\displaystyle {}= \frac{a_n + 1}{a_n}$$\displaystyle {}= 1$$\displaystyle {}+ \frac{1}{a_n}$

$b_n$${}= \dfrac{1}{a_n}$ とおくと $b_{n+1}$${}= b_n$${}+ 1$ で、等差数列です。$b_1$${}= 1$ なので $b_n$${}= n$、$a_n$${}= \dfrac{1}{n}$ となります。

公式3：$a_{n+1}$${}= \dfrac{a_n}{ra_n + s}$ 型の漸化式

$r,$$\ s$ を定数とし、すべての項が $a_n$${}\neq 0$ であるとする。両辺の逆数をとり、$b_n$${}= \dfrac{1}{a_n}$ とおくと

$\displaystyle b_{n+1}$$\displaystyle {}= \frac{ra_n + s}{a_n}$$\displaystyle {}= sb_n$$\displaystyle {}+ r$

となり、等差型（$s$${}= 1$）または $pa_n$${}+ q$ 型に帰着する。

逆数をとるには、どの項も $0$ でないことが必要です。上の例では $a_1$${}= 1$${}> 0$ で、$a_n$${}> 0$ なら $a_{n+1}$${}= \dfrac{a_n}{a_n + 1}$${}> 0$ なので、すべての項が正です（「1 つ目が正、正なら次も正」という議論で、第8章の数学的帰納法の形です）。答案では、このことを一言書いておきましょう。

逆数をとると話が簡単になる例は、算数の仕事算にもあります。A さん 1 人なら $3$ 日、B さん 1 人なら $6$ 日かかる仕事を、2 人でやると何日かかるか。日数のままでは足せませんが、逆数にして「1 日あたりの仕事量」$\dfrac{1}{3}$ と $\dfrac{1}{6}$ にすれば、足して $\dfrac{1}{2}$、答えは $2$ 日です。分数型の漸化式も、逆数の世界に移ると、割り算が足し算やかけ算に変わるのです。

分母に $a_n$ がある分数型の漸化式は、すべての項が $0$ でないことを確かめてから逆数 $\dfrac{1}{a_n}$ を新しい数列とみると、等差型や $pa_n$${}+ q$ 型になるということです。

例題3：分数型

次の漸化式で定まる数列 $\{a_n\}$ の一般項を求めなさい。

(1) $a_1$${}= 1,$$a_{n+1}$${}= \dfrac{a_n}{a_n + 1}$

(2) $a_1$${}= 1,$$a_{n+1}$${}= \dfrac{a_n}{3a_n + 2}$

---

【解答】

(1) 上で見たとおり、すべての項が正なので逆数をとれて、$b_n$${}= \dfrac{1}{a_n}$ は初項 $1$、公差 $1$ の等差数列です。$b_n$${}= n$ より

$$\underline{a_n = \frac{1}{n}}$$

(2) $a_1$${}= 1$${}> 0$ で、$a_n$${}> 0$ なら $a_{n+1}$${}> 0$ なので、すべての項が正です。逆数をとると

$\displaystyle \frac{1}{a_{n+1}}$$\displaystyle {}= \frac{3a_n + 2}{a_n}$$\displaystyle {}= \frac{2}{a_n}$$\displaystyle {}+ 3$

$b_n$${}= \dfrac{1}{a_n}$ とおくと $b_{n+1}$${}= 2b_n$${}+ 3$，$b_1$${}= 1$ です。$\alpha$${}= 2\alpha$${}+ 3$ を解くと $\alpha$${}= -3$ で、$b_{n+1}$${}+ 3$${}= 2(b_n + 3)$。数列 $\{b_n + 3\}$ は初項 $4$、公比 $2$ の等比数列なので、$b_n$${}+ 3$${}= 4 \cdot 2^{n-1}$${}= 2^{n+1}$ より

$$\underline{a_n = \frac{1}{2^{n+1} - 3}}$$

（$a_2$${}= \dfrac{1}{3 + 2}$${}= \dfrac{1}{5}$、式でも $\dfrac{1}{8 - 3}$${}= \dfrac{1}{5}$。）

2 つ前の項まで使う 3 項間漸化式

次は、2 つ前の項まで使う漸化式です。たとえば

$\displaystyle a_1$$\displaystyle {}= 1,$$\displaystyle a_2$$\displaystyle {}= 1,$$\displaystyle a_{n+2}$$\displaystyle {}= a_{n+1}$$\displaystyle {}+ a_n$

では、$1,$$\ 1,$$\ 2,$$\ 3,$$\ 5,$$\ 8,$$\ 13,$$\ \ldots$ と、前の 2 つを足して次の項を作ります。項が 3 つ登場するので 3 項間漸化式 といいます。次の項を作るのに 2 つの項が要るので、初めに $a_1$ と $a_2$ の 2 つを与えます。

この形を解く鍵は、うまい定数 $\alpha,$$\ \beta$ を選んで

$\displaystyle a_{n+2}$$\displaystyle {}- \alpha a_{n+1}$$\displaystyle {}= \beta(a_{n+1} - \alpha a_n)$

と書きかえることです。こうできれば、数列 $\{a_{n+1} - \alpha a_n\}$ が公比 $\beta$ の等比数列になります。右辺を移項して整理すると $a_{n+2}$${}= (\alpha + \beta)a_{n+1}$${}- \alpha\beta a_n$ なので、$a_{n+2}$${}= pa_{n+1}$${}+ qa_n$ と比べて

$\displaystyle \alpha$$\displaystyle {}+ \beta$$\displaystyle {}= p,$$\displaystyle \alpha\beta$$\displaystyle {}= -q$

であればよいことが分かります。解と係数の関係から、$\alpha,$$\ \beta$ は 2 次方程式 $x^2$${}- px$${}- q$${}= 0$、つまり $x^2$${}= px$${}+ q$ の 2 つの解です。この式は、漸化式の $a_{n+2},$$\ a_{n+1},$$\ a_n$ を $x^2,$$\ x,$$\ 1$ に置きかえた形をしています。

公式4：3 項間漸化式 $a_{n+2}$${}= pa_{n+1}$${}+ qa_n$

$p,$$\ q$ を定数とし、2 次方程式 $x^2$${}= px$${}+ q$ の 2 つの解を $\alpha,$$\ \beta$ とする。漸化式 $a_{n+2}$${}= pa_{n+1}$${}+ qa_n$ は

$\displaystyle a_{n+2}$$\displaystyle {}- \alpha a_{n+1}$$\displaystyle {}= \beta(a_{n+1} - \alpha a_n),$$\displaystyle a_{n+2}$$\displaystyle {}- \beta a_{n+1}$$\displaystyle {}= \alpha(a_{n+1} - \beta a_n)$

の 2 通りに変形できる。よって

$\displaystyle a_{n+1}$$\displaystyle {}- \alpha a_n$$\displaystyle {}= (a_2 - \alpha a_1)\beta^{n-1},$$\displaystyle a_{n+1}$$\displaystyle {}- \beta a_n$$\displaystyle {}= (a_2 - \beta a_1)\alpha^{n-1}$

(i) 解の 1 つが $1$ のとき（$\alpha$${}= 1$）：1 つ目の式は $a_{n+1}$${}- a_n$${}= (a_2 - a_1)\beta^{n-1}$ で、階差数列が等比数列になる。

(ii) $\alpha$${}\neq \beta$ のとき：2 つの式を辺々引いて $a_{n+1}$ を消すと、$(\beta - \alpha)a_n$${}= (a_2 - \alpha a_1)\beta^{n-1}$${}- (a_2 - \beta a_1)\alpha^{n-1}$ から $a_n$ が求まる。

$x^2$${}= px$${}+ q$ を、この漸化式の特性方程式と呼ぶことがある。

しゃくとり虫の歩き方を思い浮かべてください。しゃくとり虫は、前足と後ろ足の 2 か所で体を支えながら進みます。次にどこへ足を下ろすかは、今の 2 か所の位置で決まります。前足の位置だけを追いかけても動きは読みにくいのですが、2 か所を組み合わせた量、たとえば「前足と後ろ足の間隔」に目をつけると、単純な規則が見えてくることがあります。3 項間漸化式で $a_{n+1}$${}- \alpha a_n$ という組み合わせを考えるのは、この「うまい組み合わせ」に目をつけることにあたります。

(ii) で $\alpha$${}= \beta$（重解）のときは、2 つの式が同じになってしまうので、別の工夫が要ります（実践 j10）。

3 項間漸化式は、特性方程式 $x^2$${}= px$${}+ q$ の解 $\alpha,$$\ \beta$ を使って $a_{n+1}$${}- \alpha a_n$ が等比数列になる形に変形し、解に $1$ があれば階差数列で、$\alpha$${}\neq \beta$ なら 2 式から $a_{n+1}$ を消して解くということです。

例題4：3 項間漸化式

次の漸化式で定まる数列 $\{a_n\}$ の一般項を求めなさい。

(1) $a_1$${}= 2,$$a_2$${}= 5,$$a_{n+2}$${}= 3a_{n+1}$${}- 2a_n$

(2) $a_1$${}= 1,$$a_2$${}= 5,$$a_{n+2}$${}= a_{n+1}$${}+ 6a_n$

---

【解答】

(1) $x^2$${}= 3x$${}- 2$ を解くと $x$${}= 1,$$\ 2$ です。解の $1$ を使うと、漸化式は

$\displaystyle a_{n+2}$$\displaystyle {}- a_{n+1}$$\displaystyle {}= 2(a_{n+1} - a_n)$

と変形できます。階差数列 $b_n$${}= a_{n+1}$${}- a_n$ は初項 $b_1$${}= 5$${}- 2$${}= 3$、公比 $2$ の等比数列で、$b_n$${}= 3 \cdot 2^{n-1}$ です。$n$${}\geqq 2$ のとき

$\displaystyle a_n$$\displaystyle {}= 2$$\displaystyle {}+ \sum_{k=1}^{n-1} 3 \cdot 2^{k-1}$$\displaystyle {}= 2$$\displaystyle {}+ 3(2^{n-1} - 1)$$\displaystyle {}= 3 \cdot 2^{n-1}$$\displaystyle {}- 1$

$n$${}= 1$ を代入すると $3$${}- 1$${}= 2$ で、$a_1$ と一致します。よって $\underline{\rule[-0.15em]{0em}{0.9641em}a_n = 3 \cdot 2^{n-1}}$$\underline{\rule[-0.15em]{0em}{0.9641em}{}- 1}$。

（$a_3$${}= 15$${}- 4$${}= 11$、式でも $12$${}- 1$${}= 11$。）

(2) $x^2$${}= x$${}+ 6$ を解くと $x$${}= 3,$${}\ -2$ です。漸化式は次の 2 通りに変形できます。

$\displaystyle a_{n+2}$$\displaystyle {}- 3a_{n+1}$$\displaystyle {}= -2(a_{n+1} - 3a_n),$$\displaystyle a_{n+2}$$\displaystyle {}+ 2a_{n+1}$$\displaystyle {}= 3(a_{n+1} + 2a_n)$

$a_2$${}- 3a_1$${}= 2$，$a_2$${}+ 2a_1$${}= 7$ なので

$\displaystyle a_{n+1}$$\displaystyle {}- 3a_n$$\displaystyle {}= 2 \cdot (-2)^{n-1},$$\displaystyle a_{n+1}$$\displaystyle {}+ 2a_n$$\displaystyle {}= 7 \cdot 3^{n-1}$

2 つ目の式から 1 つ目の式を辺々引くと $5a_n$${}= 7 \cdot 3^{n-1}$${}- 2 \cdot (-2)^{n-1}$ で

$$\underline{a_n = \frac{7 \cdot 3^{n-1} - 2 \cdot (-2)^{n-1}}{5}}$$

（$n$${}= 1$ で $\dfrac{7 - 2}{5}$${}= 1$，$n$${}= 2$ で $\dfrac{21 + 4}{5}$${}= 5$。$a_3$${}= 5$${}+ 6$${}= 11$、式でも $\dfrac{63 - 8}{5}$${}= 11$。）

(1) の漸化式は、実は第6章の $pa_n$${}+ q$ 型から生まれたものです。$a_{n+1}$${}= 2a_n$${}+ 1$ の番号を 1 つずらした $a_{n+2}$${}= 2a_{n+1}$${}+ 1$ から、もとの式を引くと $a_{n+2}$${}- a_{n+1}$${}= 2(a_{n+1} - a_n)$、つまり $a_{n+2}$${}= 3a_{n+1}$${}- 2a_n$ になります。第6章で示した「$pa_n$${}+ q$ 型は階差をとると等比数列」という別解は、3 項間漸化式の (i) の場合を先取りしていたわけです。

和 $S_n$ を含む漸化式

最後は、初項から第 $n$ 項までの和 $S_n$ と $a_n$ の関係で数列が決まる場合です。たとえば「すべての $n$ で $S_n$${}= 2a_n$${}- n$」という条件から、$a_n$ を求めます。

使うのは第4章の公式3、$a_1$${}= S_1$ と $a_n$${}= S_n$${}- S_{n-1}$ です。ここでは番号を 1 つずらした形を使います。

公式5：$S_n$ を含む漸化式

数列 $\{a_n\}$ の初項から第 $n$ 項までの和を $S_n$ とすると

$\displaystyle a_1$$\displaystyle {}= S_1,$$\displaystyle a_{n+1}$$\displaystyle {}= S_{n+1}$$\displaystyle {}- S_n$$\displaystyle (n = 1,\ 2,\ 3,\ \ldots)$

$S_n$ と $a_n$ の関係式が与えられたときは、

1. $n$${}= 1$ を代入して（$S_1$${}= a_1$ を使って）$a_1$ を求める。
2. 関係式の $n$ を $n$${}+ 1$ にした式から、もとの式を辺々引き、$S_{n+1}$${}- S_n$${}= a_{n+1}$ を使って $a_{n+1}$ と $a_n$ の漸化式にする。

$n$ のときの式と $n$${}+ 1$ のときの式は、左右に並べた「間違い探し」の 2 枚の絵のようなものです。ほとんど同じなので、重ねてみると共通の部分は消え、違うところだけが浮かび上がります。$S_{n+1}$ と $S_n$ の違いは最後の 1 項 $a_{n+1}$ だけなので、引き算をすると和 $S$ が姿を消し、項どうしの関係だけが残るのです。

2 の手順で出てくる $a_n$ は $n$${}\geqq 1$ のものなので、$a_1$ は 1 の手順で別に求めておく必要があります。第4章で「$n$${}= 1$ を別に確かめる」としたのと同じ注意です。

$S_n$ を含む式は、$n$${}= 1$ で初項を求めたうえで、$n$${}+ 1$ の式ともとの式を引いて $S$ を消し、$a_{n+1}$ と $a_n$ の漸化式に直して解くということです。

例題5：$S_n$ を含む漸化式

数列 $\{a_n\}$ の初項から第 $n$ 項までの和 $S_n$ が、すべての自然数 $n$ について次の式を満たすとき、一般項 $a_n$ を求めなさい。

(1) $S_n$${}= 3$${}- 2a_n$

(2) $S_n$${}= 2a_n$${}- n$

---

【解答】

(1) $n$${}= 1$ とすると $a_1$${}= 3$${}- 2a_1$ より $a_1$${}= 1$ です。$S_{n+1}$${}= 3$${}- 2a_{n+1}$ から $S_n$${}= 3$${}- 2a_n$ を辺々引くと

$\displaystyle a_{n+1}$$\displaystyle {}= -2a_{n+1}$$\displaystyle {}+ 2a_n$$\displaystyle \text{より}$$\displaystyle a_{n+1}$$\displaystyle {}= \frac{2}{3}a_n$

初項 $1$、公比 $\dfrac{2}{3}$ の等比数列なので $\underline{a_n = \left(\dfrac{2}{3}\right)^{n-1}}$。

（$S_2$${}= 1$${}+ \dfrac{2}{3}$${}= \dfrac{5}{3}$、式でも $3$${}- 2 \cdot \dfrac{2}{3}$${}= \dfrac{5}{3}$。）

(2) $n$${}= 1$ とすると $a_1$${}= 2a_1$${}- 1$ より $a_1$${}= 1$ です。$S_{n+1}$${}= 2a_{n+1}$${}- (n + 1)$ から $S_n$${}= 2a_n$${}- n$ を辺々引くと

$\displaystyle a_{n+1}$$\displaystyle {}= 2a_{n+1}$$\displaystyle {}- 2a_n$$\displaystyle {}- 1$$\displaystyle \text{より}$$\displaystyle a_{n+1}$$\displaystyle {}= 2a_n$$\displaystyle {}+ 1$

$\alpha$${}= 2\alpha$${}+ 1$ より $\alpha$${}= -1$ で、$a_{n+1}$${}+ 1$${}= 2(a_n + 1)$。数列 $\{a_n + 1\}$ は初項 $2$、公比 $2$ の等比数列なので、$a_n$${}+ 1$${}= 2^n$ より

$\displaystyle \underline{\rule[-0.15em]{0em}{0.8644em}a_n = 2^n}$$\displaystyle \underline{\rule[-0.15em]{0em}{0.8644em}{}- 1}$

（$S_2$${}= 1$${}+ 3$${}= 4$、式でも $2 \cdot 3$${}- 2$${}= 4$。）

(2) の答えは、第6章で最初に $pa_n$${}+ q$ 型を考えたときの数列 $1,$$\ 3,$$\ 7,$$\ 15,$$\ \ldots$ と同じです。

場面から 3 項間漸化式を立てる

3 項間漸化式は、「場合の数」を数えるときによく現れます。一般項が分からなくても、漸化式さえ立てれば、項を順に計算して答えにたどり着けます。

例題6：階段の上り方

階段を、1 回に 1 段または 2 段ずつ上ります。$n$ 段の階段を上りきる上り方の数を $a_n$ とします（たとえば 3 段なら「1 段・1 段・1 段」「1 段・2 段」「2 段・1 段」の $3$ 通りで、$a_3$${}= 3$ です）。

(1) $a_1,$$\ a_2$ を求め、$a_{n+2}$ を $a_{n+1}$ と $a_n$ で表しなさい。

(2) $a_{10}$ を求めなさい。

---

【解答】

(1) 1 段の階段は「1 段」の $1$ 通り、2 段の階段は「1 段・1 段」「2 段」の $2$ 通りなので、$\underline{\rule[-0.1944em]{0em}{0.8389em}a_1 = 1,}$$\underline{\rule[-0.1944em]{0em}{0.8389em}\ a_2 = 2}$。

$n$${}+ 2$ 段の上り方を、最後の一歩 で 2 つに分けます。

• 最後が 1 段のとき、その直前には $n$${}+ 1$ 段目にいます。そこまでの上り方は $a_{n+1}$ 通り。
• 最後が 2 段のとき、その直前には $n$ 段目にいます。そこまでの上り方は $a_n$ 通り。

この 2 つは重ならず、ほかの場合もないので

$\displaystyle \underline{\rule[-0.2083em]{0em}{0.7917em}a_{n+2} = a_{n+1}}$$\displaystyle \underline{\rule[-0.2083em]{0em}{0.7917em}{}+ a_n}$

(2) 漸化式で順に計算すると

$\displaystyle 1,$$\displaystyle \ 2,$$\displaystyle \ 3,$$\displaystyle \ 5,$$\displaystyle \ 8,$$\displaystyle \ 13,$$\displaystyle \ 21,$$\displaystyle \ 34,$$\displaystyle \ 55,$$\displaystyle \ 89$

よって $\underline{a_{10} = 89}$。

ポイントは「最後の一歩で場合分けする」ことです。最初の一歩で分けても同じ漸化式になります。この数列は、小話で紹介するフィボナッチ数列の仲間です。

場合の数を数える問題では、最後（または最初）の一歩で場合分けすると、1 つ前・2 つ前の場合の数を使った漸化式が立ち、項を順に計算できるということです。

この章のまとめと次の章

この章の漸化式の形と、ひと工夫、帰着させる先をまとめます。

• $a_{n+1}$${}= pa_n$${}+ (n \text{ の 1 次式})$：1 次式 $g(n)$ を引く（または階差をとる）→ $\{a_n - g(n)\}$ が等比数列
• $a_{n+1}$${}= pa_n$${}+ q^n$：$q^{n+1}$ で割る（または $p^{n+1}$ で割る）→ $pa_n$${}+ q$ 型（または階差型）
• $a_{n+1}$${}= \dfrac{a_n}{ra_n + s}$：逆数をとる（項が $0$ でないことを確かめる）→ 等差型・$pa_n$${}+ q$ 型
• $a_{n+2}$${}= pa_{n+1}$${}+ qa_n$：$x^2$${}= px$${}+ q$ の解 $\alpha,$$\ \beta$ で変形 → $\{a_{n+1} - \alpha a_n\}$ が等比数列
• $S_n$ と $a_n$ の関係式：$n$${}= 1$ で初項、$n$${}+ 1$ の式と引く → $a_{n+1}$ と $a_n$ の漸化式

どの形でも、最後は第1章・第2章・第4章で学んだ等差数列・等比数列・階差数列に戻ってきました。見慣れない漸化式に出会ったら、「何を引けば、何で割れば、何を新しい数列とみれば、知っている形になるか」を考えることが出発点です。

では、次の漸化式はどうでしょう。

$\displaystyle a_1$$\displaystyle {}= 0,$$\displaystyle a_{n+1}$$\displaystyle {}= \frac{1}{2 - a_n}$

項を書き出すと $0,$$\ \dfrac{1}{2},$$\ \dfrac{2}{3},$$\ \dfrac{3}{4},$$\ \ldots$ で、$a_n$${}= \dfrac{n - 1}{n}$ ではないかと見当がつきます。この見当が、$n$${}= 100$ でも $n$${}= 10000$ でも本当に正しいと、どうすれば言い切れるでしょうか。次の第8章では、「$n$${}= 1$ で成り立つ」と「$n$${}= k$ で成り立てば $n$${}= k$${}+ 1$ でも成り立つ」の 2 段で、すべての自然数についての主張を示す方法、数学的帰納法 を学びます。