数学的帰納法 - 数式で独楽する

全ての自然数 $n$ に対し命題 $P(n)$ が成り立つ

ことを証明する、有力な方法です。

以下のステップで、全ての自然数 $n$ に対して命題 $P(n)$ が

$n=1$ の場合、 $P(1)$ が成り立つことを示す。
$n=k$ の場合に $P(k)$ が成り立つと仮定し、 $n=k+1$ の場合も $P(k+1)$ が成り立つことを示す。

派生型はいろいろあるでしょうが、基本型は上の通りです。

この2つのステップで、
\begin{equation}
P(1) \to P(2) \to P(3) \to \cdots \to P(n) \to \cdots
\end{equation}と芋づる式に全ての自然数 $n$ に対して命題が成り立つことを示すことができるのです。

実例を挙げます。
\begin{equation}
S_n = 1^2 +2^2 + \cdots + n^2 = \frac{1}{6} n(n+1)(2n+1) \tag{1}
\end{equation}を数学的帰納法で示してみます。

$n=1$ の場合、
\begin{equation}
S_1 = 1
\end{equation}なので命題は成り立ちます。

$n=k$ の場合に成り立つと仮定します。
\begin{equation}
S_k = 1^2 +2^2 + \cdots + k^2 = \frac{1}{6} k(k+1)(2k+1)
\end{equation}です。
このとき、
\begin{eqnarray}
S_{k+1} &=& S_k + (k+1)^2 \\
&=& \frac{1}{6} k(k+1)(2k+1) + (k+1)^2 \\
&=& (k+1) \left \{ \frac{1}{6} k(2k+1) + (k+1) \right \} \\
&=& \frac{1}{6} (k+1)(2k^2 + k + 6k +6) \\
&=& \frac{1}{6} (k+1)(2k^2 + 7k + 6) \\
&=& \frac{1}{6} (k+1)(k+2)(2k+3) \\
&=& \frac{1}{6} (k+1) \{(k+1)+1 \} \{ 2(k+1) +1 \}
\end{eqnarray}なので、 $n=k+1$ の場合も成り立ちます。

よって、全ての自然数 $n$ に対して式(1)が成り立ちます。

別の証明は
自然数の2乗の和 - 数式で独楽する
に示しています。