第8章　数学的帰納法

見当を「言い切る」には

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

$\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},$$\ \dfrac{4}{5},$$\ \ldots$ となり、$a_n$${}= \dfrac{n - 1}{n}$ ではないかと見当がつきます。この形は分母に $a_n$ が引き算で入っていて、第7章のように逆数をとってもすぐには等差・等比になりません。そこで、一般項を「導く」代わりに、見当が正しいことを「示す」ことにします。

ここで、次のことに気がつきます。ある番号 $k$ で $a_k$${}= \dfrac{k - 1}{k}$ が正しいとしてみると、漸化式から

$\displaystyle a_{k+1}$$\displaystyle {}= \frac{1}{2 - \dfrac{k - 1}{k}}$$\displaystyle {}= \frac{1}{\dfrac{2k - (k - 1)}{k}}$$\displaystyle {}= \frac{k}{k + 1}$

となり、次の番号 $k$${}+ 1$ でも同じ形 $\dfrac{(k + 1) - 1}{k + 1}$ が出てきます。つまり「ある番号で正しければ、次の番号でも正しい」ことが、$k$ がいくつであっても言えるのです。

一方、$n$${}= 1$ では $a_1$${}= 0$${}= \dfrac{1 - 1}{1}$ で、見当は正しいと確かめられます。すると、$n$${}= 1$ で正しいから $n$${}= 2$ でも正しい、$n$${}= 2$ で正しいから $n$${}= 3$ でも正しい……と、どこまでもたどっていけます。こうして、すべての自然数 $n$ について $a_n$${}= \dfrac{n - 1}{n}$ だと言い切れます。これが 数学的帰納法 の考え方です。

公式1：数学的帰納法

自然数 $n$ についての主張を $P(n)$ とする。次の 2 つを示せば、$P(n)$ はすべての自然数 $n$ について成り立つ。

[1] $n$${}= 1$ のとき、$P(1)$ が成り立つ。

[2] $n$${}= k$ のとき $P(k)$ が成り立つと仮定すると、$n$${}= k$${}+ 1$ のときも $P(k + 1)$ が成り立つ。

答案は次の形で書く。

1. [1] $n$${}= 1$ のとき（両辺の値などを計算して）成り立つ。
2. [2] $n$${}= k$ のとき成り立つと仮定すると（仮定の式を書き）、$n$${}= k$${}+ 1$ のとき（仮定を使って変形し）成り立つ。
3. [1]，[2] より、すべての自然数 $n$ について成り立つ。

[2] で「仮定する」のは、$P(k)$ が正しいと決めつけることではありません。「もし $P(k)$ が正しければ、$P(k + 1)$ も正しい」というつながりを示しているだけです。この仮定を 帰納法の仮定 といいます。仮定を使わずに $P(k + 1)$ を示せてしまったら、それは帰納法ではなく、直接の証明です。

たくさん並べたドミノを思い浮かべてください。全部倒れることを確かめるのに、1 枚ずつ見て回る必要はありません。確かめることは 2 つだけです。1 つは「最初の 1 枚を倒す」こと。もう 1 つは「どの 1 枚も、倒れたら必ず次の 1 枚を倒す間隔で並んでいる」ことです。最初の 1 枚を倒さなければ、間隔がどれだけ正しくても 1 枚も倒れません。逆に、どこか 1 か所でも間隔が広すぎれば、そこで止まってしまいます。[1] が最初の 1 枚を倒すこと、[2] が並べ方の点検にあたります。

第7章で分数型の漸化式を解くとき、「$a_1$${}> 0$ で、$a_n$${}> 0$ なら $a_{n+1}$${}> 0$ なので、すべての項が正」と一言書きました。これは [1]・[2] の 2 段そのもので、実はすでに帰納法を使っていたのです。第6章の小話で紹介したプログラムの再帰で「終わりの条件を忘れると止まらない」と書いたのも、[1] がないと話が始まらないことと対応しています。

数学的帰納法とは、[1] $n$${}= 1$ で成り立つことと、[2] $n$${}= k$ で成り立つと仮定すれば $n$${}= k$${}+ 1$ でも成り立つことの 2 つを示して、すべての自然数 $n$ で成り立つと結論する方法だということです。

例題1：漸化式の見当を示す

(1) $a_1$${}= 0,$$a_{n+1}$${}= \dfrac{1}{2 - a_n}$ で定まる数列 $\{a_n\}$ について、$a_n$${}= \dfrac{n - 1}{n}$ であることを数学的帰納法で示しなさい。

(2) $a_1$${}= 2,$$a_{n+1}$${}= a_n^2$${}- na_n$${}+ 1$ で定まる数列 $\{a_n\}$ について、$a_2,$$\ a_3,$$\ a_4$ を求めて一般項を推測し、それが正しいことを数学的帰納法で示しなさい。

---

【解答】

(1) $a_n$${}= \dfrac{n - 1}{n}$ …① とする。

[1] $n$${}= 1$ のとき、$a_1$${}= 0$，$\dfrac{1 - 1}{1}$${}= 0$ なので、① は成り立つ。

[2] $n$${}= k$ のとき ① が成り立つ、つまり $a_k$${}= \dfrac{k - 1}{k}$ と仮定すると

$\displaystyle a_{k+1}$$\displaystyle {}= \frac{1}{2 - \dfrac{k - 1}{k}}$$\displaystyle {}= \frac{k}{2k - (k - 1)}$$\displaystyle {}= \frac{k}{k + 1}$$\displaystyle {}= \frac{(k + 1) - 1}{k + 1}$

よって、$n$${}= k$${}+ 1$ のときも ① は成り立つ。

[1]，[2] より、すべての自然数 $n$ について $a_n$${}= \dfrac{n - 1}{n}$ である。（証明終）

(2) $a_2$${}= 4$${}- 2$${}+ 1$${}= 3$，$a_3$${}= 9$${}- 6$${}+ 1$${}= 4$，$a_4$${}= 16$${}- 12$${}+ 1$${}= 5$ なので、$a_n$${}= n$${}+ 1$ …① と推測できる。

[1] $n$${}= 1$ のとき、$a_1$${}= 2$${}= 1$${}+ 1$ なので、① は成り立つ。

[2] $n$${}= k$ のとき ① が成り立つ、つまり $a_k$${}= k$${}+ 1$ と仮定すると

$\displaystyle a_{k+1}$$\displaystyle {}= (k + 1)^2$$\displaystyle {}- k(k + 1)$$\displaystyle {}+ 1$$\displaystyle {}= (k + 1)\{(k + 1) - k\}$$\displaystyle {}+ 1$$\displaystyle {}= k$$\displaystyle {}+ 2$

よって、$n$${}= k$${}+ 1$ のときも ① は成り立つ。

[1]，[2] より、すべての自然数 $n$ について $\underline{\rule[-0.15em]{0em}{0.7944em}a_n = n}$$\underline{\rule[-0.15em]{0em}{0.7944em}{}+ 1}$ である。（証明終）

(2) の漸化式には $a_n^2$ があり、第6章・第7章のどの型にも当てはまりません。項を計算して見当をつけ、帰納法で確かめる。この「推測して証明する」流れは、形の決まっていない漸化式に対する強力な手段です。

和の等式を示す

第3章では、$1^2$${}+ 2^2$${}+ \cdots$${}+ n^2$${}= \dfrac{n(n + 1)(2n + 1)}{6}$ を、$(k + 1)^3$${}- k^3$ を足し並べる工夫で導きました。帰納法を使えば、公式の形が分かっているとき、それが正しいことをもっと機械的に確かめられます。

鍵になるのは、$n$${}= k$${}+ 1$ のときの左辺が、$n$${}= k$ のときの左辺に 1 項足しただけだということです。

$\displaystyle \underbrace{1^2 + 2^2 + \cdots + k^2}_{n = k \text{ の左辺}}$$\displaystyle {}+ (k + 1)^2$

下線の部分に帰納法の仮定を使うと

$\displaystyle \frac{k(k + 1)(2k + 1)}{6}$$\displaystyle {}+ (k + 1)^2$$\displaystyle {}= \frac{(k + 1)\{k(2k + 1) + 6(k + 1)\}}{6}$$\displaystyle {}= \frac{(k + 1)(2k^2 + 7k + 6)}{6}$$\displaystyle {}= \frac{(k + 1)(k + 2)(2k + 3)}{6}$

で、これは右辺の $n$ に $k$${}+ 1$ を入れた $\dfrac{(k + 1)\{(k + 1) + 1\}\{2(k + 1) + 1\}}{6}$ そのものです。

公式2：和の等式の証明

$a_1$${}+ a_2$${}+ \cdots$${}+ a_n$${}= f(n)$ …① を数学的帰納法で示すときは

[1] $n$${}= 1$ のとき、左辺 $a_1$ と右辺 $f(1)$ が等しいことを確かめる。

[2] $n$${}= k$ のとき ① が成り立つと仮定して、$n$${}= k$${}+ 1$ のときの左辺を

$\displaystyle (a_1 + a_2 + \cdots + a_k)$$\displaystyle {}+ a_{k+1}$$\displaystyle {}= f(k)$$\displaystyle {}+ a_{k+1}$

と変形し、これが $f(k + 1)$ に等しいことを示す。

$f(k + 1)$ は、ゴールとして先に書き出しておくと変形の目標が見やすい。

家計簿の「前月からの繰越」を考えてみましょう。今月末の残高を知りたいとき、1 月から全部を足し直す必要はありません。先月末の残高を繰り越して、今月の収支を足せば済みます。帰納法の仮定は「先月までの帳簿は合っている」ということで、[2] の計算は「繰越 ＋ 今月分」が今月末の正しい残高になっていると確かめる作業です。

和の等式を帰納法で示すときは、$n$${}= k$${}+ 1$ の左辺を「$n$${}= k$ の和 ＋ 第 $k$${}+ 1$ 項」に分け、前半に仮定を使って、右辺の $n$ に $k$${}+ 1$ を入れた式になることを確かめるということです。

例題2：和の等式

すべての自然数 $n$ について、次の等式が成り立つことを数学的帰納法で示しなさい。

(1) $1$${}+ 3$${}+ 5$${}+ \cdots$${}+ (2n - 1)$${}= n^2$

(2) $1 \cdot 2$${}+ 2 \cdot 3$${}+ 3 \cdot 4$${}+ \cdots$${}+ n(n + 1)$${}= \dfrac{n(n + 1)(n + 2)}{3}$

---

【解答】

(1) 等式を ① とする。

[1] $n$${}= 1$ のとき、左辺 $= 1$，右辺 $= 1^2$${}= 1$ なので、① は成り立つ。

[2] $n$${}= k$ のとき ① が成り立つ、つまり $1$${}+ 3$${}+ \cdots$${}+ (2k - 1)$${}= k^2$ と仮定する。$n$${}= k$${}+ 1$ のときの左辺は

$\displaystyle 1$$\displaystyle {}+ 3$$\displaystyle {}+ \cdots$$\displaystyle {}+ (2k - 1)$$\displaystyle {}+ (2k + 1)$$\displaystyle {}= k^2$$\displaystyle {}+ 2k$$\displaystyle {}+ 1$$\displaystyle {}= (k + 1)^2$

となり、右辺に等しい。よって、$n$${}= k$${}+ 1$ のときも ① は成り立つ。

[1]，[2] より、すべての自然数 $n$ について ① は成り立つ。（証明終）

(2) 等式を ① とする。

[1] $n$${}= 1$ のとき、左辺 $= 1 \cdot 2$${}= 2$，右辺 $= \dfrac{1 \cdot 2 \cdot 3}{3}$${}= 2$ なので、① は成り立つ。

[2] $n$${}= k$ のとき ① が成り立つと仮定する。$n$${}= k$${}+ 1$ のときの左辺は

$\displaystyle \frac{k(k + 1)(k + 2)}{3}$$\displaystyle {}+ (k + 1)(k + 2)$$\displaystyle {}= \frac{(k + 1)(k + 2)(k + 3)}{3}$

となり（$(k + 1)(k + 2)$ でくくると $\dfrac{k}{3}$${}+ 1$${}= \dfrac{k + 3}{3}$）、右辺の $n$ に $k$${}+ 1$ を入れた式に等しい。よって、$n$${}= k$${}+ 1$ のときも ① は成り立つ。

[1]，[2] より、すべての自然数 $n$ について ① は成り立つ。（証明終）

(1) の $n$${}= k$${}+ 1$ の左辺で、最後の項を $2k$${}- 1$ としないように注意しましょう。第 $k$${}+ 1$ 項は $2(k + 1)$${}- 1$${}= 2k$${}+ 1$ です。「$n$${}= k$${}+ 1$ のとき最後の項は何か」を一般項に代入して確かめる習慣をつけると、ここでの取り違えが防げます。

出発点を変える：不等式の証明

$2^n$ と $n^2$ の大きさを比べてみます。

$n$${}= 3$ では $n^2$ のほうが大きいのに、$n$${}= 5$ からは $2^n$ が引き離していきます。「$n$${}\geqq 5$ のとき $2^n$${}> n^2$」を示したいのですが、$n$${}= 1$ から始めると $n$${}= 3$ で成り立たないので、[1] を $n$${}= 5$ に置きかえます。

公式3：出発点が $n$${}= m$ の数学的帰納法

$m$ を自然数とする。次の 2 つを示せば、$P(n)$ は $n$${}\geqq m$ のすべての自然数 $n$ について成り立つ。

[1] $n$${}= m$ のとき、$P(m)$ が成り立つ。

[2] $k$${}\geqq m$ として、$n$${}= k$ のとき $P(k)$ が成り立つと仮定すると、$n$${}= k$${}+ 1$ のときも $P(k + 1)$ が成り立つ。

途中の駅から各駅停車に乗る場面にたとえられます。始発駅から乗らなくても、5 番目の駅で乗りさえすれば、その先はすべての駅に止まります。乗る駅が [1]、「各駅に止まる」ことが [2] です。ただし、[2] で使ってよいのは「乗ったあとの駅」についての性質、つまり $k$${}\geqq m$ という条件です。

不等式の証明では、[2] で仮定を使ったあとに「もう一押し」が必要になることがよくあります。$2^k$${}> k^2$ を仮定すると $2^{k+1}$${}= 2 \cdot 2^k$${}> 2k^2$ までは言えますが、ゴールは $2^{k+1}$${}> (k + 1)^2$ です。そこで、$2k^2$${}\geqq (k + 1)^2$ かどうかを、差をとって別に調べます。

$\displaystyle 2k^2$$\displaystyle {}- (k + 1)^2$$\displaystyle {}= k^2$$\displaystyle {}- 2k$$\displaystyle {}- 1$$\displaystyle {}= (k - 1)^2$$\displaystyle {}- 2$

$k$${}\geqq 5$ ならこれは $16$${}- 2$${}= 14$ 以上で正です。こうして $2^{k+1}$${}> 2k^2$${}> (k + 1)^2$ とつながります。

ある番号 $m$ から先で成り立つ主張は、[1] を $n$${}= m$ に置きかえ、[2] で $k$${}\geqq m$ を使えばよく、不等式では仮定を使ったあとに差をとって「もう一押し」の比較をするということです。

例題3：不等式

次の不等式を数学的帰納法で示しなさい。

(1) $n$${}\geqq 3$ のすべての自然数 $n$ について　$2^n$${}> 2n$${}+ 1$

(2) $n$${}\geqq 5$ のすべての自然数 $n$ について　$2^n$${}> n^2$

---

【解答】

(1) 不等式を ① とする。

[1] $n$${}= 3$ のとき、左辺 $= 8$，右辺 $= 7$ なので、① は成り立つ。

[2] $k$${}\geqq 3$ として、$n$${}= k$ のとき ① が成り立つ、つまり $2^k$${}> 2k$${}+ 1$ と仮定すると

$\displaystyle 2^{k+1}$$\displaystyle {}= 2 \cdot 2^k$$\displaystyle {}> 2(2k + 1)$$\displaystyle {}= 4k$$\displaystyle {}+ 2$

ここで $(4k + 2)$${}- \{2(k + 1) + 1\}$${}= 2k$${}- 1$${}> 0$ なので、$2^{k+1}$${}> 2(k + 1)$${}+ 1$。よって、$n$${}= k$${}+ 1$ のときも ① は成り立つ。

[1]，[2] より、$n$${}\geqq 3$ のすべての自然数 $n$ について ① は成り立つ。（証明終）

(2) 不等式を ① とする。

[1] $n$${}= 5$ のとき、左辺 $= 32$，右辺 $= 25$ なので、① は成り立つ。

[2] $k$${}\geqq 5$ として、$n$${}= k$ のとき ① が成り立つ、つまり $2^k$${}> k^2$ と仮定すると、$2^{k+1}$${}= 2 \cdot 2^k$${}> 2k^2$。ここで

$\displaystyle 2k^2$$\displaystyle {}- (k + 1)^2$$\displaystyle {}= (k - 1)^2$$\displaystyle {}- 2$$\displaystyle {}\geqq 4^2$$\displaystyle {}- 2$$\displaystyle {}> 0$

なので、$2^{k+1}$${}> 2k^2$${}> (k + 1)^2$。よって、$n$${}= k$${}+ 1$ のときも ① は成り立つ。

[1]，[2] より、$n$${}\geqq 5$ のすべての自然数 $n$ について ① は成り立つ。（証明終）

倍数であることを示す

「$4^n$${}- 1$ は $3$ の倍数」のような、整数の性質も帰納法で示せます。$4$${}- 1$${}= 3$，$16$${}- 1$${}= 15$，$64$${}- 1$${}= 63$ と、確かに $3$ の倍数が並びます。

「$3$ の倍数である」ことは、そのままでは計算に使えません。「整数 $m$ を用いて $3m$ と表せる」と式に直すのがコツです。仮定 $4^k$${}- 1$${}= 3m$ を $4^k$${}= 3m$${}+ 1$ と書きかえて $4^{k+1}$ に代入すると

$\displaystyle 4^{k+1}$$\displaystyle {}- 1$$\displaystyle {}= 4 \cdot 4^k$$\displaystyle {}- 1$$\displaystyle {}= 4(3m + 1)$$\displaystyle {}- 1$$\displaystyle {}= 12m$$\displaystyle {}+ 3$$\displaystyle {}= 3(4m + 1)$

となり、$4m$${}+ 1$ は整数なので $4^{k+1}$${}- 1$ も $3$ の倍数です。$n$ の多項式の場合は、$n$${}= k$${}+ 1$ の式を展開して「$n$${}= k$ の式 ＋ $3 \times$（整数）」の形を探します。

倍数であることを帰納法で示すときは、仮定を「整数 $m$ を用いて $3m$ と表せる」と式に直し、$n$${}= k$${}+ 1$ の式を「$3 \times$（整数）」の形に変形するということです。

例題4：倍数の証明

すべての自然数 $n$ について、次のことが成り立つことを数学的帰納法で示しなさい。

(1) $4^n$${}- 1$ は $3$ の倍数である。

(2) $n^3$${}+ 2n$ は $3$ の倍数である。

---

【解答】

(1) [1] $n$${}= 1$ のとき、$4$${}- 1$${}= 3$ は $3$ の倍数である。

[2] $n$${}= k$ のとき成り立つ、つまり整数 $m$ を用いて $4^k$${}- 1$${}= 3m$ と表せると仮定すると

$\displaystyle 4^{k+1}$$\displaystyle {}- 1$$\displaystyle {}= 4(3m + 1)$$\displaystyle {}- 1$$\displaystyle {}= 3(4m + 1)$

$4m$${}+ 1$ は整数なので、$n$${}= k$${}+ 1$ のときも成り立つ。

[1]，[2] より、すべての自然数 $n$ について $4^n$${}- 1$ は $3$ の倍数である。（証明終）

(2) [1] $n$${}= 1$ のとき、$1$${}+ 2$${}= 3$ は $3$ の倍数である。

[2] $n$${}= k$ のとき成り立つ、つまり整数 $m$ を用いて $k^3$${}+ 2k$${}= 3m$ と表せると仮定すると

$\displaystyle (k + 1)^3$$\displaystyle {}+ 2(k + 1)$$\displaystyle {}= k^3$$\displaystyle {}+ 3k^2$$\displaystyle {}+ 5k$$\displaystyle {}+ 3$$\displaystyle {}= (k^3 + 2k)$$\displaystyle {}+ 3(k^2 + k + 1)$$\displaystyle {}= 3(m + k^2 + k + 1)$

$m$${}+ k^2$${}+ k$${}+ 1$ は整数なので、$n$${}= k$${}+ 1$ のときも成り立つ。

[1]，[2] より、すべての自然数 $n$ について $n^3$${}+ 2n$ は $3$ の倍数である。（証明終）

(2) は $n^3$${}+ 2n$${}= n(n^2 + 2)$ として、$n$ を $3$ で割った余りで場合分けしても示せます。帰納法は、場合分けの方法が思いつかないときにも使える、手堅い道具です。

2 つ前まで仮定する帰納法

3 項間漸化式で見当を示そうとすると、困ったことが起こります。

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

項は $1,$$\ 3,$$\ 7,$$\ 15,$$\ 31,$$\ \ldots$ で、$a_n$${}= 2^n$${}- 1$ と見当がつきます。ところが、$a_{k+1}$ を作るには $a_k$ と $a_{k-1}$ の 2 つが必要なので、「$n$${}= k$ で成り立つ」という仮定 1 つだけでは、次の項を計算できません。

そこで、仮定を 2 つに増やします。「$n$${}= k$ と $n$${}= k$${}+ 1$ の両方で成り立つ」と仮定して $n$${}= k$${}+ 2$ を示すのです。このとき、出発点も 2 つ確かめておく必要があります。

公式4：2 つ前まで仮定する数学的帰納法

次の 2 つを示せば、$P(n)$ はすべての自然数 $n$ について成り立つ。

[1] $n$${}= 1,$$\ 2$ のとき、$P(1),$$\ P(2)$ が成り立つ。

[2] $n$${}= k,$$\ k$${}+ 1$ のとき $P(k),$$\ P(k + 1)$ が成り立つと仮定すると、$n$${}= k$${}+ 2$ のときも $P(k + 2)$ が成り立つ。

綱登りを思い浮かべてください。綱を登るとき、両手で 2 か所をつかんでいれば、下の手を離して上へ伸ばすことができます。1 か所しかつかんでいないと、手を離した瞬間に落ちてしまいます。3 項間漸化式の帰納法で「2 つ仮定する」のは、両手でつかんでいる状態にあたり、[1] で $n$${}= 1,$$\ 2$ を確かめるのは、最初に両手で綱を握ることにあたります。

[1] で 1 つしか確かめないのは、よくある失敗です。$n$${}= 1$ だけでは、[2] の $k$${}= 1$ に必要な「$P(1)$ と $P(2)$ の両方」がそろわず、最初の一手が出せません。

次の項を作るのに 2 つ前の項まで要るときは、[1] で $n$${}= 1,$$\ 2$ の 2 つを確かめ、[2] で $n$${}= k,$$\ k$${}+ 1$ の 2 つを仮定して $n$${}= k$${}+ 2$ を示すということです。

例題5：2 つ前まで仮定する帰納法

(1) $a_1$${}= 1,$$a_2$${}= 3,$$a_{n+2}$${}= 3a_{n+1}$${}- 2a_n$ で定まる数列 $\{a_n\}$ について、$a_n$${}= 2^n$${}- 1$ であることを数学的帰納法で示しなさい。

(2) $a_1$${}= 1,$$a_2$${}= 1,$$a_{n+2}$${}= a_{n+1}$${}+ a_n$ で定まる数列 $\{a_n\}$ について、すべての自然数 $n$ で $a_n$${}< 2^n$ であることを数学的帰納法で示しなさい。

---

【解答】

(1) $a_n$${}= 2^n$${}- 1$ …① とする。

[1] $n$${}= 1$ のとき $a_1$${}= 1$${}= 2$${}- 1$，$n$${}= 2$ のとき $a_2$${}= 3$${}= 4$${}- 1$ なので、① は成り立つ。

[2] $n$${}= k,$$\ k$${}+ 1$ のとき ① が成り立つ、つまり $a_k$${}= 2^k$${}- 1$，$a_{k+1}$${}= 2^{k+1}$${}- 1$ と仮定すると

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

よって、$n$${}= k$${}+ 2$ のときも ① は成り立つ。

[1]，[2] より、すべての自然数 $n$ について $a_n$${}= 2^n$${}- 1$ である。（証明終）

(2) 不等式を ① とする。

[1] $n$${}= 1$ のとき $a_1$${}= 1$${}< 2$，$n$${}= 2$ のとき $a_2$${}= 1$${}< 4$ なので、① は成り立つ。

[2] $n$${}= k,$$\ k$${}+ 1$ のとき ① が成り立つ、つまり $a_k$${}< 2^k$，$a_{k+1}$${}< 2^{k+1}$ と仮定すると

$\displaystyle a_{k+2}$$\displaystyle {}= a_{k+1}$$\displaystyle {}+ a_k$$\displaystyle {}< 2^{k+1}$$\displaystyle {}+ 2^k$$\displaystyle {}< 2^{k+1}$$\displaystyle {}+ 2^{k+1}$$\displaystyle {}= 2^{k+2}$

よって、$n$${}= k$${}+ 2$ のときも ① は成り立つ。

[1]，[2] より、すべての自然数 $n$ について $a_n$${}< 2^n$ である。（証明終）

(1) は第7章の公式4でも解けます（特性方程式 $x^2$${}= 3x$${}- 2$ の解が $1,$$\ 2$）。一般項を「導く」なら第7章の方法、答えが分かっていて「確かめる」なら帰納法、と使い分けられます。

[1] を忘れると：見当は証明するまで見当

「すべての自然数 $n$ について、$n^2$${}+ n$${}+ 1$ は偶数である」という主張を考えます。[2] だけを確かめてみましょう。$k^2$${}+ k$${}+ 1$ が偶数だと仮定すると

$\displaystyle (k + 1)^2$$\displaystyle {}+ (k + 1)$$\displaystyle {}+ 1$$\displaystyle {}= (k^2 + k + 1)$$\displaystyle {}+ 2(k + 1)$

で、偶数に偶数を足したものなので、偶数です。[2] は立派に成り立っています。ところが、$n$${}= 1$ を代入すると $1$${}+ 1$${}+ 1$${}= 3$ で奇数です。実は $n^2$${}+ n$${}= n(n + 1)$ は連続する 2 数の積でいつも偶数なので、$n^2$${}+ n$${}+ 1$ はいつも奇数です。主張は正しくありません。

ドミノで言えば、並べ方は完璧でも、最初の 1 枚を誰も倒していない状態です。[2] は「つながり」を保証するだけで、どこかに出発点がなければ何も示せません。

逆に、[1] をいくつ確かめても [2] がなければ証明になりません。第4章の小話で、円周上の点を結んで円を分けると $1,$$\ 2,$$\ 4,$$\ 8,$$\ 16$ と続くのに、次は $32$ ではなく $31$ になる例を紹介しました。数項がそろって見えても、それは見当にすぎません。見当を定理に変えるのが、[1] と [2] の 2 段なのです。

[2] だけでは出発点がなく、[1] だけでは先へ進めないので、帰納法の証明では [1] と [2] の両方を必ず書くということです。

この章のまとめと次の章

これで、数列の基本的な道具がそろいました。最後の第9章では、これまでの道具を、確率や図形などの場面で使います。たとえば、さいころを $n$ 回投げて $6$ の目が出た回数が偶数である確率を $p_n$ とすると、$n$${}+ 1$ 回目に $6$ が出るかどうかで場合分けして

$\displaystyle p_{n+1}$$\displaystyle {}= \frac{5}{6}p_n$$\displaystyle {}+ \frac{1}{6}(1 - p_n)$

という漸化式が立ちます。これは第6章の $pa_n$${}+ q$ 型です。場面から漸化式を立てて解く、数列の総仕上げに進みましょう。