【標準】数学的帰納法と等式の証明

ここでは、数学的帰納法を使った等式の証明について見ていきます。

数学的帰納法を使った等式の証明

例題
n が自然数のとき、次の等式が成り立つことを示しなさい。
\begin{eqnarray}
& &
(n+1)(n+2)(n+3)\cdots(2n) \\[5pt] &=&
2^n\cdot1\cdot3\cdot5\cdots(2n-1)
\end{eqnarray}

直接示すこともできます(後で見ます)が、ここではまず、すべての自然数に対して成り立つ等式なので、数学的帰納法を使って示せないかを考えてみます。【基本】数学的帰納法で見たように、2つのステップで示せばいいのでしたね。

後で呼びやすいように、自然数 n に対して
\begin{eqnarray}
f(n)
&=&
(n+1)(n+2)(n+3)\cdots(2n) \\[5pt] g(n)
&=&
2^n\cdot1\cdot3\cdot5\cdots(2n-1)
\end{eqnarray}とおきましょう。すべての自然数 n について、 $f(n)=g(n)$ が成り立つことを示していきます。

(i) $n=1$ のとき、\[ f(1)=2 \]であり、\[ g(1)=2^1\cdot 1=2 \]なので、 $f(1)=g(1)$ が成り立ちます。

(ii) 2つ目のステップでは、「 $n=k$ のときに成り立てば、 $n=k+1$ のときも成り立つ」ことを示すのでしたね。つまり、「 $f(k)=g(k)$ が成り立つなら、 $f(k+1)=g(k+1)$ も成り立つ」ことを示します。

具体的に書けば、
\begin{eqnarray}
f(k)
&=&
(k+1)(k+2)(k+3)\cdots(2k) \\[5pt] g(k)
&=&
2^k\cdot1\cdot3\cdot5\cdots(2k-1)
\end{eqnarray}となります。仮定から、この2つが等しいことを利用できます。また、
\begin{eqnarray}
f(k+1)
&=&
(k+2)(k+3)(k+4)\cdots(2k)(2k+1)(2k+2) \\[5pt] g(k+1)
&=&
2^{k+1}\cdot1\cdot3\cdot5\cdots(2k-1)(2k+1)
\end{eqnarray}となります。仮定を使って、この2つが等しいことを示すことが目標です。

$f(k)$ と $f(k+1)$ はよく似ていますね。いくつか項が違うだけです。この違いを $g(k)$ に反映させれば、 $g(k+1)$ と等しいことが導けるのではないか、という発想で、式変形をしてみましょう。
\begin{eqnarray}
& &
f(k+1) \\[5pt] &=&
(k+2)(k+3)\cdots(2k)(2k+1)(2k+2) \\[5pt] &=&
(k+1)(k+2)(k+3)\cdots(2k)\times \frac{(2k+1)(2k+2)}{k+1} \\[5pt] &=&
f(k)\times 2(2k+1) \\[5pt] &=&
g(k)\times 2(2k+1) \\[5pt] &=&
2^k\cdot1\cdot3\cdot5\cdots(2k-1) \times 2(2k+1) \\[5pt] &=&
2^{k+1}\cdot1\cdot3\cdot5\cdots(2k-1)(2k+1) \\[5pt] &=&
g(k+1) \\[5pt] \end{eqnarray}となります。前半部分では、 $f(k+1)$ を $f(k)$ とそれ以外の部分で分けています。次に、仮定である $f(k)=g(k)$ が成り立つことを用いています。後半では、 $g(k)$ に残っていた部分を加味して、 $g(k+1)$ になるように式変形をしています。

このことから、「 $f(k)=g(k)$ が成り立つなら、 $f(k+1)=g(k+1)$ も成り立つ」ことが示せました。

以上より、(i)(ii)から、数学的帰納法より、すべての自然数 n について $f(n)=g(n)$ が成り立つことが示せました。

例題を数学的帰納法を使わずに示す

少し気づきにくいですが、例題の等式は、両辺とも $\dfrac{(2n)!}{n!}$ を表していることに気づけば、数学的帰納法を使わなくても示すことができます。
\begin{eqnarray}
& &
(n+1)(n+2)(n+3)\cdots(2n) \\[5pt] &=&
\frac{1\cdot2\cdots n(n+1)(n+2)\cdots(2n)}{1\cdot2\cdots n} \\[5pt] &=&
\frac{1\cdot3\cdot5\cdots (2n-1)\times 2\cdot4\cdot6\cdots 2n}{1\cdot2\cdots n} \\[5pt] &=&
\frac{1\cdot3\cdot5\cdots (2n-1)\times 2^n\cdot1\cdot2\cdot3\cdots n}{1\cdot2\cdots n} \\[5pt] &=&
2^n\cdot1\cdot3\cdot5\cdots(2n-1)
\end{eqnarray}$1$ から $2n$ までの積を、奇数だけの積と偶数だけの積に分けます。偶数だけの積の部分を、 $2k=2\cdot k$ のように2とそれ以外に分けます。こうした変形を組み合わせれば、上のように直接示すこともできます。

気付ければこちらの方が短く示せるかもしれませんが、難易度はだいぶ高くなります。

おわりに

ここでは、数学的帰納法を使った等式の証明を見ました。 k のときと $k+1$ のときの違いに注目して、どのように仮定を使うかがポイントです。