2.5 文字を使った証明の例
一言に「証明」とは言っても様々な証明法があります。少し挙げてみると、
・背理法 ・対偶証明法 ・数学的帰納法 ・反例を示す …
などが学校で教わる主な証明方法でしょう。
ほぼ全ての証明問題は文字無しでは解答不可能です。数学の世界には様々な証明法がありますが、特に式変形との関わりが深いものは「数学的帰納法」でしょう。
この項では文字を利用した証明の例として「数学的帰納法」と「背理法」をそれぞれ紹介していきます。
《数学的帰納法》(induction)
例題１
$n$を自然数とする。$1$から$2n-1$までの連続する$n$個の奇数の和を、$n$を用いて表せ。
こういうタイプの問題は誰もが一度は練習したことがあるのではないでしょうか。しかし侮ることなかれ。この問題は数列系の問題の基本中の基本であり、「実験」→「予想」→「証明」のプロセスを体験できる優れた問題です。結論が分かっていたり、既に知っていたりする場合は良いのですが、こういった一般的な式を求めさせる問題ではまず「実験」することが肝心です。「実験」では小さい$n$で和がどうなるのかを具体的に書き出していきます。
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 |
| $2n-1$ | 1 | 3 | 5 | 7 | 9 | 11 |
| 和 | 1 | 4 | 9 | 16 | 25 | 36 |
これより、和は$n^2$ではないかと予想できます。この予想を結論に見据え、数学的帰納法で証明してみましょう。
解答例
$1$から$2n-1$までの連続する$n$個の奇数の和を$S_n$と表すことにする。$$S_n=n^2 \ \cdots \cdots (*)$$であることを数学的帰納法により示す。
ⅰ）$n=1$のとき、$S_1=1$であり、$(*)$は成立している。
ⅱ）$n=k \ (k\in\mathbb{N}\geqq 2)$のとき、$(*)$が成立すると仮定する。いま、仮定より$$\begin{align} S_{k+1} &=\color{red}{S_k+(2k+1)} \\ &=\color{red}{k^2+2k+1} \\ &=(k+1)^2 \end{align}$$となるから$(*)$は$n=k+1$のときでも成立している。（赤色部の式変形の際に仮定を用いた）
以上より、$1$から$2n-1$までの連続する$n$個の奇数の和は $$n^2 \ \cdots \cdots (\text{答})$$ である。
$Q.E.D.$
もう一題、よくあるタイプの数学的帰納法の整数問題を紹介しましょう。
例題２
$n$を自然数とするとき$5^n-2^n$が$3$の倍数であることを示せ。
まずは実験です。
小さい方から$5^1-2^1=3$、$5^2-2^2=21$、$5^3-2^3=117$、$5^4-2^4=609$となり、確かに$3$の倍数となっていることが分かります。こういうタイプの問題の場合は$5^n-2^n$という形をどう利用するかがポイントです。
解答例１
$5^n-2^n$が$3$の倍数であることを数学的帰納法により示す。
ⅰ）$n=1$のとき、$5^n-2^n=3$であり、$3$の倍数である。
ⅱ）$n=k \ (k\in\mathbb{N}\geqq 2)$のとき、$5^k-2^k$が$3$の倍数であると仮定する。$$5^{k+1}-2^{k+1}=5(5^k-2^k)+3 \cdot 2^k \ \cdots \cdots (*)$$と変形すると、仮定より$5^k-2^k$は$3$の倍数であるから、$(*)$は$3$の倍数である。故に$n=k+1$のときでも成立している。
以上より、$5^n-2^n$が$3$の倍数であることが示された。
$Q.E.D.$
解答例２
$5^n-2^n$が$3$の倍数であることを数学的帰納法により示す。
ⅰ）$n=1$のとき、$5^n-2^n=3$であり、$3$の倍数である。
ⅱ）$n=k \ (k\in\mathbb{N}\geqq 2)$のとき、$5^k-2^k$が$3$の倍数であると仮定する。このとき自然数$m$を用いて$5^k-2^k=3m$と置けるから$5^k=3m+2^k$である。よって$$\begin{align} 5^{k+1}-2^{k+1} &= 5(3m+2^k)-2 \cdot 2^k \\ &= 3(5m+2^k) \ \cdots \cdots (*) \end{align}$$と変形できる。$5m+2^k$は整数であるから、$(*)$は$3$の倍数である。故に$n=k+1$のときでも成立している。
以上より、$5^n-2^n$が$3$の倍数であることが示された。
$Q.E.D.$
この他にも二項展開を利用した解答例や因数分解を利用した解答例などもありますが、数学的帰納法を学ぶという観点から見ると、やや横道に逸れてしまうのでここでは割愛します。
◎数学的帰納法の用法まとめ
２つの問題を例に見てきましたが、例題１の場合は「答えの『形』を引き継ぐ」タイプの問題であり、例題２の場合は強いて言えば「答えの『性質』を引き継ぐ」タイプの問題です（例題２の解答例２では「$3$で割り切れる」という性質を式化して解答しているので明確には分類できませんが…）。
数学的帰納法を利用して解答する場合は、何を引き継ぐべきなのか、そして何を引き継いでいるのかをしっかり頭で理解しながら答案を書きましょう。この点が曖昧なままだと支離滅裂な答案や何となく誤魔化したような答案になってしまいかねません。
数学的帰納法を使うときは基本的に「実験」→「予想」→「証明」の順で解答を作ります。問題集や模試などの模範解答ではいきなり証明が始まるため「答えありきの答案」に見えてしまうことが多々あります。しかし実際には「実験」→「予想」の手順を計算用紙にやっておいてあるのです。そこから答案を作るのでそういう風に見えてしまうものではあるのですが…。ただ、数学的帰納法こそ「数学的試行錯誤」の末に正答に辿り着く、というまさに数学の王道だと言えるのではないでしょうか。これを使いこなせるようになれば数列と整数の融合問題の半分は解けますよ（笑）。
《背理法》(proof by contradiction)
背理法は整数問題を制覇する上で非常に重要な証明法です。英語名の通り、これは「矛盾による証明」です。要するに、ある集合や状態において$A$であることを示すのに、$\bar{A}$（＝$A$でない）であることを仮定して矛盾を導く、というものです。皆さんも一度くらいはやったことがありますよね？
例題１
$\sqrt{2}$が無理数であることを示せ。
超有名題ですね。色々な証明方法が挙げられますが、ここでは背理法で証明します。「無理数でない」ということは「有理数である」ということを利用します。
解答例
$\sqrt{2}$が有理数であると仮定すると、互いに素な２つの自然数$p、q$を用いて$\sqrt{2}=\dfrac{p}{q}$と表すことができる。両辺に$q$を乗じ、両辺正なので２乗すると$$2q^2=p^2$$となる。左辺は$2$の倍数だから右辺も$2$の倍数でなければならない。よって$p=2r \ (r \in \mathbb{N})$と置けて、これを代入すると$$q^2=2r^2$$となり、同様に$q$も$2$の倍数であることが必要となる。しかし$p、q$がともに偶数となることは$p、q$が互いに素な自然数であることに矛盾する。
したがって$\sqrt{2}$は有理数でない。故に$\sqrt{2}$は無理数である。
$Q.E.D.$
例題２
３つの整数$a、b、c$が等式 $a^2+b^2=c^2$ を満たしているとき、$a、b、c$のいずれか１つは偶数であることを示せ。
これも有名です。背理法で簡潔に証明できます。
解答例
$a、b、c$がいずれも奇数であると仮定すると、自然数$l、m、n$を用いて$a=2l-1、b=2m-1、c=2n-1$と表すことができる。これらを与式に代入すると$$\small \ \ \begin{align} (2l-1)^2+(2m-1)^2 &= (2n-1)^2 \\ \therefore 2(2m^2-2m+2l^2-2l+1) &= 2(2n^2-2n)+1 \end{align}$$となる。しかし左辺が偶数であるのに対して右辺は奇数となり不合理である。
したがって$a、b、c$のすべてが奇数となることはない。故に$a、b、c$のいずれか１つは偶数である。
$Q.E.D.$
例題３
素数が無数に存在することを示せ。
ユークリッドにより背理法を用いた見事な証明が与えられています。
解答例
素数が$n$個しか存在しないとして、それらを$p_1、p_2、\cdots、p_n$と置く。ただし$n$は整数の定数である。ここで、これらすべての積に$1$を加えた数 $N=p_1 p_2 \cdots p_n+1$ を考える。$N$は$p_1、p_2、\cdots、p_n$のいずれの素数とも互いに素であるから、$N$の素因数は$p_1、p_2、\cdots、p_n$のいずれとも等しくない。これは素数が$n$個しか存在しないとした仮定に矛盾する。
したがって素数が有限個であることはない。故に素数は無数に存在する。
$Q.E.D.$
◎背理法の用法まとめ
以上、様々な背理法の使い方を紹介しましたが、使われ方のバリエーションはこんな程度ではありません。背理法は直接証明するのが難しい命題や、あるいは直接証明するとなると場合分けが多くなる命題を証明したいときに有効な手段です。数学的帰納法より使い所の判断が難しい証明法ですが、ハイレベルな整数問題になると使えと言われなくとも使えなければならないので、色々な問題を解いて勘を培ってください。
ここまで見てきた「数学的帰納法」と「背理法」は、問題文に特に指示が無くても、証明のための道具として常に使えるようにしておく必要があります。この他にも「対偶証明法」や「無限降下法」、「部屋割り論法」など様々な証明法があるのですが、とりあえずこの項で扱った２つの方法は特に重要なので、第２節の最後に紹介しておきました。
他の証明法はその都度解説していきます。あとは「習うより慣れろ」の精神でたくさん問題演習を積んでください。受験は「量・質・量」です。