数学で使われる公式の中には、「ある整数nに対して成り立つ公式」というようなものがあります。例えば次のような、高校数学で習う等差級数の公式なんかが有名かと思います。
まだ少年だったころのガウスが見つけた公式なんて話を聞いた方もいるのではないでしょうか？
$$ 1 + 2 + 3 + ・・・ + n = \frac{ n ( n + 1 ) }{ 2 } $$
実際にこの公式は、n=1の場合、次のようになって成り立つことが分かります。
$$ 1 = \frac{ 1 ( 1 + 1 ) }{ 2 } = \frac{ 2 }{ 2 } $$
そして、n=2、3、・・・と続けていくとどの正の整数に対しても成り立つことが確認できます。
世の中には、この等差数列の総和公式以外にも「整数nに対して成り立つ」というものがあります。で、その公式が本当にある整数以上の整数”すべて”に対して正しいかどうかを証明する必要があるんですな。その証明をするときに利用できるのが、数学的帰納法になります。
今回は、そんな数学的帰納法についての話です。
そもそも、”数学的帰納法”って何をしたいの？
数学的帰納法を学校で習った（あるいは、独学してて出てきた）けど、いったい何がしたくてそんなことをするの？って方もいるかと思います（過去の僕です。代数的な式変形で導けるんならそれで十分じゃね？って思ってました）。
なので、数学的帰納法を利用した証明方法とか具体例を説明する前に、まずは数学的帰納法の存在意義をこの節で説明していきます（もう分かってるよーって方は、次の節から読み進めていただければと思います～）。
最初に数学的帰納法の役割を一言で言い表しておきますと、それは「検証」になります。
仮に、さっきの等差級数の公式を導き出さないといけないとします。その場合、2通りの解決策が考えられます。1つは、高校でも習ったように、同じ級数を2つ足し合わせるという方法で式変形をして公式を導き出すという方法です。要するに、代数学的に解くってことですな。
もう1つは、具体例から法則性を見抜くという方法です。等差級数の場合はすでにすべての正の整数に対して成り立つということが分かっているので、当然、具体例からも公式を導くことはできるはずです。まぁ、原理上は可能というだけで、実際に法則性に気付いて式として表すのは結構難しいんですが^^;
ただし、2つ目の方法には問題点があります。
具体例から法則性を見抜いたとしても、その法則が果たしてどこまで続くのかが分からないという点です。というのも、「具体例から法則性を見抜いた」ということは、とりもなおさず「自分の考えた具体例についてはその法則が成り立っている」ということになります。
数学においては、ある具体例については成り立つということが示されただけでは、「ある特殊な条件下においては成り立つ公式」として扱われるだけで、「すべてに対して成り立つ公式」としては認められません。仮にn=0からn=100までの整数に対して確かめたとしても、他のnに対しては成り立つかどうかが証明できていないからです。
この「ある特殊な条件下においては成り立つ公式」を「すべてに対して成り立つ公式」にするためには、具体例を計算する以外の方法が必要です。
要するに、具体例をどれだけ計算したとしても、やはり「特殊な条件下においては成り立つ公式」で留まってしまうから、具体例を計算する以外の方法が必要ってことですな。
言い換えると、本当に「すべてに対して成り立つ公式」なのかどうかを数学的に「検証」する必要があります。で、その「検証」のために使われる方法が、今回のテーマである「数学的帰納法」になります。
※数学的帰納法の本質は「検証」なので、数学的帰納法を利用しようとする場合には、あらかじめ法則性から何らかの式を予想しておく必要があります。
数学的帰納法の原理
数学的帰納法は、すべての整数に対して成り立つかどうかを「検証」するためにあるということを理解していただけたかと思います。
では、実際にどうすれば数学的帰納法により証明（検証）することが出来るのかを説明していきます。
先に証明に必要な2つの手順を書いときます。次の2つです。
- 一般的な方法（要するに式変形）で、n=r+1のときに成り立つことを示す
- n=1のときに成り立つことを示す
これだけで分かったという方は、次の具体例の節まで読み飛ばしていただいても大丈夫です。もうちょっと説明が欲しいよ～って方は、このままもうしばらくお付き合いくださいませ～。
例として、またまた等差級数を考えます。考えるべき問題としては「等差級数の公式はすべての整数nに対して成り立つか？」といった辺りになるかと思います。
一応、公式を再掲しときます。ただし、書くのが面倒なので、1からnまでの総和を\( S_n \)と表します。
$$ S_n = \frac{ n ( n + 1 ) }{ 2 } $$
この公式がすべての正の整数nに対して成り立つかどうかを「検証」していくということになります。この段階では、この公式がすべての正の整数nに対して成り立ってるかどうかは、まだ分からないと考えるってわけですな。
まず、先ほどの節でも説明した通り、具体例を計算するだけでは「すべての整数に対して成り立つ」という主張を証明することはできませんでした。ただし、ある特定の条件（例えば、n=1の場合とか）に関しては証明することできました。
ここで、試しにn=2として確かめてみます（n=1の場合は、この記事の最初ですでに確かめましたので、ここでは割愛します）。n=2の場合、次のように計算できて、公式は成り立ちます。
$$ S_2 = 1 + 2 = \frac{ 2 ( 2 + 1 ) }{ 2 } = \frac{ 6 }{ 2 } $$
n=3の場合は、次のように計算できて、成り立ちます。
$$ S_3 = \frac{ 3 ( 3 + 1 ) }{ 2 } = \frac{ 12 }{ 2 } $$
このまま、n=4、n=5、・・・と順に代入していっても成り立つことが予想できます。
もしも、この公式が正の整数”すべて”に対して成り立っているのであれば、nにある正の整数rの次の整数r+1を代入したとしても成り立つということになります。
そして、nにr+1を代入して一般的な方法（代数学的に正しい式変形）のみを使って公式が成り立つことを示せた場合、それはすべての数の次の数に対して成り立つと示せたことになります。というのも、一般的な方法を利用しているので、nにどんな数が代入されようとも、同じ式変形によって公式が成り立つことを示せます。
つまり、どんなnに対しても、必ずその次のn+1が正しいことを証明できることになります。言い換えると、ある数rに対して公式が成り立つことを、その一つ前の整数r-1が成り立つということを根拠に証明できることになります。
これが数学的帰納法による証明の手順1になります。
この証明は、プログラミングにおける無限ループさながらに、「与えられた数に対して、同じ式変形を次々とこなしていく」という証明になります。よくドミノ倒しなんかに例えられる理論ですな。
要するに、すべての正の整数に対して成り立つことを示せるというわけです。
ところで、こんな疑問を持った方もいらっしゃるかもしれません。「もしも、最初の時点で成り立っていなかった場合はどうなるの？」と。
今までの議論では、「nにr+1を代入して公式が成り立つことを示せたら、r（ある整数）に対しては公式が成り立つことを根拠に、r+1（その次の整数）に対して公式が成り立つことを示せる」というものでした。
もしも、rの取り得る値の範囲で最初の整数に対して公式が成り立っていなかった場合、それ以降の整数に対しても成り立たないということになってしまうからです。
そこで、証明の手順2が必要になってきます。つまり、最初の整数n=1に対して成り立つと証明出来さえすれば、それよりも後ろの整数に関しては正しいことが保証されるわけなので（手順1により）、正の整数すべてに対して成り立つということが示せるということになります。
というわけで、以上2つの手順で正の整数全体に対して成り立つことが証明できます。
これが、数学的帰納法の原理になります。では、次の節から数学的帰納法を利用した具体例を見ていきます。
具体例
この節では2つの具体例に実際に数学的帰納法を適用してみます。長々と説明してきましたが、実際に証明するときにやることは短いです。
まずは、今までさんざん例に挙げてきた等差級数の公式についてです。正の整数すべてに対して成り立つということを、数学的帰納法により根拠を与えてみます。
まずは、手順1（n=r+1のときに成り立つことを示す）です。
公式は次の通りでした。
$$ S_n = \frac{ n ( n + 1 ) }{ 2 } $$
ここで、nがある特定の整数rだとします。つまり、次のようになっていたとします（上の式でnをrに変更しただけです）。
$$ S_r = \frac{ r ( r + 1 ) }{ 2 } $$
そして、この両辺に(r + 1)を足します。すると、次のようになって、r+1に対しても成り立つことが示せます。※\( S_r + ( r + 1 ) \)は\( S_{r + 1} \)と同じです。
$$
\begin{equation}
\begin{split}
S_r + ( r + 1 ) &= \frac{ r ( r + 1 ) }{ 2 } + ( r + 1 ) \\
&= \frac{ r ( r + 1 ) + 2( r + 1 ) }{ 2 } \\
&= \frac{ ( r + 1 )( r + 2 ) }{ 2 }
\end{split}
\end{equation}
$$
で、これは公式にr + 1を代入したものに他なりません。というわけで、最初n=1のときに成り立つことが示せたら、すべての正の整数に対して成り立つことが示せたことになります。ただ、n=1のときに関しては、この記事の冒頭ですでに示しているので割愛します。
ということで、等差級数の公式はすべての正の整数に対して成り立つと証明できたことになります。
等差級数に関しては、「すべての正の整数すべてに対して成り立つ」ということは知られているので、次は数学的帰納法を利用しないと「すべての正の整数すべてに対して成り立つ」ことが分かりづらい例に数学的帰納法を適用してみます。
次のような例になります。
$$ (1 + q) (1 + q^{2}) (1 + q^{4} ) ・・・ (1 + q^{2^n} ) = \frac{ 1 – q^{ 2^{ n + 1 } } }{ 1 – q } $$
等差級数の例ではある数rの次の数を両辺に足していましたが、今回の例では両辺に(r+1)を掛けます。つまり、n=r+1を代入します。すると、次のようになって、成り立つことが示せます。
$$
\begin{equation}
\begin{split}
(1 + q) (1 + q^{2}) (1 + q^{4} ) ・・・\\
・・・(1 + q^{2^r} ) (1 + q^{2^{ ( r + 1 ) } } )
&= \frac{ 1 – q^{ 2^{ ( r + 1 ) } } }{ 1 – q } \times (1 + q^{2^{ ( r + 1 ) } } ) \\
&= \frac{ ( 1 – q^{ 2^{ ( r + 1 ) } } ) (1 + q^{2^{ ( r + 1 ) } } ) }{ 1 – q } \\
&= \frac{ 1 – ( q^{ 2^{ ( r + 1 ) } } )^2 }{ 2 } \\
&= \frac{ 1 – q^{ 2 \times 2^{ ( r + 1 ) } } }{ 2 } \\
&= \frac{ 1 – q^{ 2^{ ( r + 2 ) } } }{ 2 }
\end{split}
\end{equation}
$$
これは、元々の公式にn=r+1を代入したものに他なりません。
そして、n=1のとき、次のようになるので、明らかに成り立ちます。
$$
\begin{equation}
\begin{split}
(1 + q) (1 + q^{2}) &= \frac{ 1 – q^{ 2^{ 1 + 1 } } }{ 1 – q } \\
&= \frac{ 1 – q^{ 4 } }{ 1 – q } \\
&= \frac{ ( 1 + q^{ 2 } ) ( 1 – q^{ 2 } ) }{ 1 – q } \\
&= \frac{ ( 1 + q^{ 2 } ) ( 1 + q ) ( 1 – q ) }{ 1 – q } \\
\end{split}
\end{equation}
$$
以上のことから、数学的帰納法の原理により、正の整数すべてに対して成り立つことが示されます。
終わりに
さて、いかがでしたでしょうか。数学的帰納法を実際に適用するのは割と簡単だったかと思います。
途中にも書きましたが、最初にどんな形の式なら一般法則として成り立つのかを予想しておく必要があるという点にはご注意くださいませ～。