数学的帰納法・背理法

 --目　次--

∗数学的帰納法
 ∗例題（１）
 ∗例題（２）
∗背理法
 ∗例題

---

数学的帰納法（以後、帰納法という）の説明でよく使う例を用います。

\( P(n):1+2+3+…+n\) \(=\frac{n(n+1)}{2} \cdots(1) \)

がすべての\( n\) において成り立つことを帰納法で証明します。
　この「すべての n がポイントです、n = 10, n = 1,000 で証明できても 「すべての n 」 を証明したことにはなりません。
「すべての n 」について証明できるのが帰納法です。
帰納法では次の2 つを証明できればすべての \(n\) について証明したことになります。

① n=1 のとき P(1) が成り立つことを確認する。

② 任意の \(n\) について P(n) が成り立つと 仮定 します。
その仮定をもとに P（n+1） が成り立つことを確認する。

 （注：n は変数であり、任意の自然数に置き換えられる）

上の①、②を使い次のように展開していく。
・n=1 のとき成り立つ。
・n=2 のときは「②の証明による（n = 1+1= 2）」 が成り立つ。
・n=3 のときは「②の証明による（n = 2+1= 3）」 が成り立つ。
・n=4 のときは「②の証明による（n = 3+1= 4」 が成り立つ。
・\(\qquad \vdots \qquad \vdots\)　　　　　
・n=k-1 のときは「②の証明による（n = k-2+1= k-1」 が成り立つ。
・n=k 　のときは「②の証明による（n =k-1+1= k）」より成り立つ。
・n=k+1のときは「②の証明による（n = k+1 」より成り立つ。
・n=k+2のときは「②の証明による（n =(K+1)+1 ）」より成り立つ。
・\(\qquad \vdots \qquad \vdots\)

このようにして （さらに続き、）いくらでも続けられるのですべて自然数\(n\)に対して P(n) が成り立つわけです。
（ドミノ倒しとか、将棋倒しなと呼ばれるゆえんです）

・n=1のとき上式(1)の両辺:
\( 1=\frac{1}{2}n(n+1)=\frac{1}{2}・1・(2)=1\)

これによりP(1)が証明できた。…上記①の証明。

・次に任意のnに対しP(n)が成り立つとしてP(n+1)を証明する。
（式(1)に(n+1)を加算したものとP(n+1)が等しくなることを示せばよい）
式(1)の左辺 \(=\underline{P(n+1)}\)
\(=1+2+…+n+(n+1)\)　\(= \frac{n(n+1)}{2}+(n+1) \)

\(= \frac{n^2+3n+2}{2}\) \(=\underline{\frac{(n+1)(n+2)}{2}}\)

式(1)の右辺 \(= \underline{\frac{(n+1)(n+2)}{2}} \)

式(1)の左辺=式(1)の右辺 である。
これにより n = n+1 のときも成り立つことが証明できた。（上記②の証明）

よって帰納法によりすべての n についても P(n) が成り立ちます。

\( P(n):\)
\(\quad 1^2+2^2+3^2+…+n^2\) \(= \frac{n(n+1)(2n+1)}{6}…(2) \)

・n=1のとき \( P(1)=1\)（右辺=左辺）である。…上記①の証明。

・次に任意のnに対しP(n)が成り立つとしてP(n+1)を証明する。
すなわち次の式を証明する。
\( 1^2+2^2+ \cdots +n^2+(n+1)^2\) \(=\underline{ \frac{(n+1)(n+2)(2n+3)}{6} }\) :(a)　

式(2)のP(n)は成り立つとするのだから、式(2)の両辺に\( (n+1)^2 \)を加える。
すなわち
\( 1^2+2^2+ \cdots +n^2+(n+1)^2\) \( = \frac{n (n+1)(2n+1)}{6} +(n+1)^2　\)　

となる。　右辺を計算する。
右辺=
\( =(n+1) \underline{ \left( \frac{n(2n+1)}{6}+ n+1 \right) }\) \( =(n+1) \left( \frac{2n^2+7n+6)}{6} \right) \) \(=\underline{\frac{(n+1)(n+2)(2n+3)}{6}}\) :(b)　
（下線部は展開、因数分解して： \( (2n+3)(n+2) \) です。）

\(　\therefore (a)=(b) \)　

これより n+1 のときも成り立ちました。…上記②の証明
よって帰納法によりすべての n についても P(n) が成り立ちます。

---

以下の手順で証明したいこと P の否定からはじまり、これは矛盾があるとして証明したい P が成り立つ。
(1)ある命題に対して、P が成り立たないと仮定します。
(2)そして最後に矛盾を導きだします。
(3)その結果、命題が成り立つことを示す証明です。

まず\( \sqrt 2\ \)が有理数と仮定する。（命題の否定を仮定）
すると\( \sqrt2= \frac{a}{b} \)　と表せる。
(a b は互いに素な自然数（正の整数）です。) 【参考先】　
証明のポイント：
・互いに素とはこれ以上割り切れないことです。
・証明の最終でa,bが偶数となる。偶数ということはまだ割り切れるので互いに素な数ではなくなる。

両辺を2乗して \( \quad 2 a^2=b^2 …(1)\)
左辺は偶数(2の倍数)なので右辺のbの2乗は偶数となる。
b の2乗が偶数なら、b も偶数である。
（このように有理数を仮定して展開していきます）
b はある自然数k に対し\( b=2k \) として
式(1)は：
\(　2a^2=(2k)^2 \rightarrow 2a^2=4k^2 \rightarrow a^2=2k \)
a の2乗は偶数であるから a も偶数である。
a, b が偶数となる。よって、a, b が「互いに素である」ことと矛盾している。
このことははじめの仮定の「有理数」が間違いです。
初めの仮定が矛盾していました。
よって \( \sqrt 2\　\) は無理数であることが証明できたことになります。