「複雑⇒簡単」の証明は
対偶法
「～ない」証明は
背理法
「すべての自然数で成り立つ」証明は
数学的帰納法
–証明問題における定石–
数学の証明問題において、特殊な証明方法が「対偶法」「背理法」「数学的帰納法」の 3 個あります。ここでは、それぞれどのようなときに使えばいいのか。その定石をお伝えします。
「複雑⇒簡単」の証明は対偶法
複雑⇒簡単とは
仮定が複雑で結論が簡単な命題のことです。例えば次のような証明問題です。
自然数 $n$ について 「$n^2$ が偶数ならば $n$ は偶数」であることを証明せよ。
| 仮定 | $n^2$ が偶数（複雑） |
| 結論 | $n$ が偶数（簡単） |
仮定を数式で表すと $n^2=2m$ ($m$：自然数) となり、ここから結論の $n$ が偶数を示そうとしても難しい。
仮にもし、仮定と結論が逆であれば
$n=2m$ ($m$：自然数) のとき，
$n^2=2・(2m)^2=2・4m^2=(偶数)$
と簡単に話が進みますね。
しかし、逆（仮定と結論を入れ替えた命題）はもとの命題と真偽が一致するとは限りません。
そこで、対偶をとるという考えに至るわけです。（対偶はもとの命題と真偽が一致する）
対偶「$n$ が奇数ならば $n^2$ は奇数」
| 仮定 | $n$ が奇数（簡単） |
| 結論 | $n^2$ が奇数（複雑） |
となり、仮定が単純になります。この証明は大丈夫かな？（一応、次の例題に入れておきます）
対偶法が有効な例題と解答例
対偶をとることにより仮定を簡単にできるとき対偶法が有効。
$2$ 問目は中級者以上向けの問題です。興味があれば挑戦してみましょう！
自然数 $n$ について 「$n^2$ が偶数ならば $n$ は偶数」であることを証明せよ。【解答】
$n$ が自然数であるとき，$2^n-1$ が素数ならば，$n$ も素数であることを証明しなさい。【京都府立医科大】【解答】
「～ない」証明は背理法
「～ない」証明とは
証明すべきものの語尾が「ない」のもの、もしくは語尾が「ない」に言い換えられるものです。
基本的に「ない」ことを証明するのは困難なので、「ある」と仮定して矛盾を導きます。
・～が存在しないことを証明せよ
・～は無理数であることを証明せよ
・～は互いに素であることを証明せよ
この辺りは、とりあえず背理法で攻めていけば良いでしょう。
…はい、疑問を持ちましたか？後半 2 つは「～ある」証明ですね。これについて触れておきます。
無理数の定義を知っていますか？
無理数の定義は「有理数でない実数」です。
「無理数である」ことの証明は「有理数でない」ことの証明です。だから背理法なんです。
「互いに素」は「共に割り切る整数が 1 以外にない」と言い換えられます。
ちなみに「互いに素」は「最大公約数が1である」を直接証明する選択肢もあります。ケースバイケースですね。
「～ない」「無理数」「互いに素」の証明は背理法
ただし「互いに素」は「最大公約数が 1 」を示しても良い
という感じでしょうか。
背理法が有効な問題と解答例
「～ない」証明、または「～ない」と言い換えられる証明（特に「無理数」「互いに素」）は背理法が有効。
特に、「～ない」と言い換えられる証明は意識しておかないと見落としがちです。
$2$ 問目は中級者以上向けの問題です。興味があれば挑戦してみましょう！
$\sqrt2$ が無理数であることを証明せよ。【解答】
$2$ 以上の自然数 $n$ に対し，$n$ と $n^2+2$ がともに素数となるのは $n=3$ の場合に限ることを示せ。【京都大】【解答】
すべての自然数で成り立つことの証明は数学的帰納法
すべての自然数で成り立つとは
これは分かりやすいから大丈夫ですかね。
「すべての自然数 $n$ について」成り立つことを証明せよ。であればほぼ数学的帰納法ですね。
・$5$ 以上のすべての整数 $n$ で成り立つことを証明せよ
・すべての正の偶数 $n$ で成り立つことを証明せよ
・すべての整数 $n$ で成り立つことを証明せよ
この辺りも数学的帰納法で対応可能です。少し説明しておきます。
＜数学的帰納法＞
次の(ア)，(イ) が成り立つとき，すべての自然数 $n$ で成り立つ。
(ア) $n=1$ のとき成り立つ。
(イ) $n=k$ のとき成り立つと仮定すると，$n=k+1$ のときも成り立つ。
・$5$ 以上のすべての整数 $n$ で成り立つことを証明せよ
これは (ア)において 「$n=5$ のとき成り立つ」に変えるだけですね。
(イ)の $k$ も $k≧5$ となるのを忘れがちなので少し注意しましょう。
・すべての正の偶数 $n$ で成り立つことを証明せよ
これは $n=2m$（$m$：自然数）とおいたあと「すべての自然数 $m$ で成り立つ」ことを数学的帰納法で示せばOK。
・すべての整数 $n$ で成り立つことを証明せよ
これを数学的帰納法で証明するのは少し珍しい。難度の高い問題です。
①「$0$ 以上の整数 $n$ で成り立つ」ことを数学的帰納法で示す
② $n=-m$（$m$：自然数） とおいて「すべての自然数 $m$ で成り立つ」ことを数学的帰納法で示す
このように、$2$ 段階に分ければ対応可能です。実際は問題によるので、あくまで一例です。
数学的帰納法が有効な例題と解答例
数学的帰納法の使いどころは他と比べて分かりやすいでしょう。ただし，入試においては「結果を推測してそれを数学的帰納法で示す」ということも多いです。注意しておきましょう。
$2$ 問目は中級者以上向けの問題です。興味があれば挑戦してみましょう！
$a_{1}=-1$，$a_{n+1}=2a_{n}^2+2na_{n}-2$ $(n=1，2，3，\cdots)$ で定義される数列 $\{a_{n}\}$ の一般項が $a_n=-2n+1$ であることを証明せよ。【解答】
整数 $a_{n}=19^n+(-1)^{n-1}2^{4n-3}$（$n=1，2，3，\cdots$）のすべてを割り切る素数を求めよ。【東工大】【解答】
最後に
定石は重要！しかし、他の可能性も選択肢に入れよう
上記の判断に従えば95%くらいはうまくいきます。ただし、「定石であれば対偶法だけど背理法を選択した方がラク」という場面もたまにあります。あくまでも考え方のとっかかりとしておき、うまくいかなければ別の方法をという選択肢も入れて考えましょう。とは言え、定石に従えば「他の解法の方が解きやすい」ことはあっても「解けなくなる」ということはほとんどないと思って大丈夫です。
まとめ
証明問題に取り組むときは，上記のことを必ず意識しましょう！
