きのうからあしたへ

ex) 次の不等式を数学的帰納法を利用して証明せよ。 (1) ２n+2＋３2n+1は７の倍数である。 (2) ２n＞２ｎ−１

＜先　生＞ところで数学的帰納法ってどんな証明法だったろうか。

＜まなぶ＞自然数に関する命題を証明する場合に、ドミノ倒しの方法を利用して、順番に小さい自然数から成立を倒していくんでしたよね。

＜先　生＞成立を倒すっていいかたは面白いね。もう少し具体的にいうとどうなるのだろう。

＜よしお＞まず、第ｋ番目が成立すると仮定します。次に、それを利用してｋ＋１番目で成立することを証明します。

＜先　生＞そうだね。命題が等式や不等式であれば、仮定したｋ番目を条件式とした場合に、ｋ＋１番目の式を証明ということだ。そして……

＜まなぶ＞最後に１番目を倒すんですね。そうすると、１番目、２番目、３番目、……と次々に倒れていって、ギネスブックに載る。

＜かず子＞それ、何のこと。

＜まなぶ＞テレビの特番で、ときどきやってるだろう。全国から集まった高校生が合宿してドミノを苦労して並べてギネスに挑戦するって番組。

＜先　生＞調子に乗り過ぎだな。でも、苦労して並べるってところは証明の本質をいっている。帰納法は「仮定したものを利用して証明をする」わけで、ドミノ倒しも実際に倒してしまったら大ヒンシュクだね。最後に誰かが１番目のドミノを人差し指でちょこっと押して倒すことで、ドミノが次々に倒れていく様を眺めることに至極の喜びがある。

＜まなぶ＞先生もちょっと、調子に乗り過ぎてない。

＜先　生＞おほん！、じゃ、そろそろ問題を解いていこう。まず(1)だ。よしお、どうする。

＜よしお＞まず、ｎ＝ｋで成立すると仮定します。
　　　「２^k+2＋３^2k+1は７の倍数である」
　これを条件として、ｎ＝ｋ＋１で成立することを証明します。すなわち、
　　　「２^(k+1)+2＋３^2(k+1)+1は７の倍数である」
ことの証明ですね。

＜先　生＞では、証明してごらん。

＜よしお＞………、済みません、先生。どう証明すればいいかヒントをいただけませんか。

＜先　生＞よしおにしては珍しいね。なにも難しく考える必要はない。この命題を式で表現すればいい。そうすると条件式のある式の証明となる。

＜よしお＞そうか。「７の倍数である」を「７の倍数に等しい」とみればいいのですね。だから、
　　　２^k+2＋３^2k+1＝７Ｎ　(Ｎは整数) ……(*)
を仮定して、
　　　２^(k+1)+2＋３^2(k+1)+1＝７Ｎ'　(Ｎ'は整数)
を証明するということですね。

＜先　生＞では、ここら辺でバトンタッチして、後半はかず子にやってもらおうか。

＜かず子＞……先生、私にもヒントをください。

＜先　生＞今日はずいぶんみんなてこずっているね。条件式のある等式の証明だから基本方針は「条件式の邪魔者を消せ」ということだよ。もう少し、分かり易くいうなら、条件式において、
　　　ａ＝２^k+2，ｂ＝３^2k+1
とおいてみればいい。すると、
　　　２^(k+1)+2＝２・２^k+2＝２ａ，３^2(k+1)+1＝３²・３^2k+1 ９ａ
　だから、結局、
　　　ａ＋ｂ＝７Ｎ　⇒　２ａ＋９ａ＝７Ｎ'
の証明ということだ。

＜かず子＞あっ、先生、もういいです。そこからはできます。条件式からａかｂのどちらかを消去すればいいんですね。
　例えば、ｂを消去すると、ｂ＝７Ｎ−ａを等式の左辺に代入して、
　　　２ａ＋９ｂ＝２ａ＋９（７Ｎ−ａ）
　　　　　　　　＝６３Ｎ＋７ａ
　　　　　　　　＝７(９Ｎ＋ａ)
　ここで、Ｎ'＝９Ｎ＋ａとすれば、証明できます。

＜先　生＞これで、ｎ＝ｋ＋１で証明されたということになる。そして、最後に……

＜まなぶ＞あっ、僕にやらせてください。ｎ＝１を代入して、
　　　（与式）＝２³＋３³＝３５
　だから、７の倍数です。

＜先　生＞以上より、すべての自然数で命題は成立するということになるね。
　それにしても、まなぶは美味しいところばかりもっていくな。

＜まなぶ＞ちょっと心外だなあ。それじゃ(2)は、僕が解きます。
　まず、ｎ＝ｋで成立すると仮定する。
　　　２^k＞２ｋ−１　……(*)
　これを条件式とみて、ｎ＝ｋ＋１で成立すればいいから、
　　　２^k+1＞２(ｋ＋１)−１
の証明ということです。
　不等式の証明だから左辺から右辺を引いて計算してみればいい。
　左辺は２^k+1＝２・２^kだから、条件式(*)を不等式の形で代入して、邪魔者の２^kを消去すると、
　　　(左辺)−(右辺)＝２・２^k−{２(ｋ＋１)−１}
　　　　　　　　　　＞２(２^k−１)−(２ｋ＋１)
　　　　　　　　　　＝２ｋ−３
　さて、あとは、後は簡単。ｋ≧１だから、２ｋ−３が正の値になっていれば………？？。
　あれ、おかしいな、正にならないよ。どこで間違えたんだろう。ええっと……。
＜よしお＞まなぶ、計算は間違ってないみたいだよ。でも、ｋ≧１ならば、２ｋ−３≧−１だから、これじゃ、証明できない。不思議だなあ。

＜かず子＞邪魔者の扱いがおかしいんじゃないかしら。

＜まなぶ＞どういうこと。

＜かず子＞条件式(*)は、
　　　ａ＝２^k，ｂ＝２ｋ
とおくと、
　　　ａ＞ｂ−１　……(**)
ということよね。そして、これを利用して、
　　　２ａ＞ｂ＋１
を証明すればいいわけだけど、先ほど、まなぶはａを消去したじゃない。
邪魔者をｂとみて消してみたらどうかしら。

＜よしお＞とにかく、やってみようか。
(**)の両辺のａ，ｂを移項して、
　　　−ｂ＞−ａ−１
これを不等式の形で代入してみよう。よって、
　　　２ａ−(ｂ＋１)＝２ａ−ｂ−１
　　　　　　　　　　＞２ａ＋(−ａ−１)−１
　　　　　　　　　　＝ａ−２
なんか、良さそうだよ。
　　　ａ−２＝２^k−２ だから、ｋ≧１より、ａ−２≧０
やった。ｎ＝ｋ＋１で証明できました。

＜先　生＞うん。いいチームワークだったね。じゃあ、ｎ＝１については先生が示そう。
　　　(左辺)−(右辺)＝１＞０
さあ、完成だ。

＜まなぶ＞先生、ちょっとまってよ。なんか仲間外れにされたような気がするんだけど。僕の考えが踏みにじってかってに話を進めているような。

＜かず子＞なに、オーパーなこといってんのよ。被害妄想だわ。

＜まなぶ＞まあ、いいや。でもね、よく考えると僕の解答でも証明は可能だと思うんだけどな。だって、
　　　(左辺)−(右辺)＞２ｋ−３
から、ｋ≧２では２ｋ−３＞０となって、成立することは明らかだよね。

＜よしお＞うん。

＜まなぶ＞ここで、ｎ＝２のときは、
　　　(左辺)−(右辺)＝２²−(２・２−１)＝１＞０
で、確かに成り立つ。
とういうことは、数学的帰納法の原理からｎ≧２では証明ができたということではないだろうか。

＜先　生＞お見事。ｎ＝１というイレギュラーを外したってことだな。そして、ｎ＝１の場合を単独に証明して合せれば、すべての自然数で成立したといえね。お見事。冴えてるね。

＜まなぶ＞三段論法みたいな数学的帰納法の証明って、なんか僕の性格にフィットするんだよな。

＜かず子＞私は、数学的帰納法ってうさん臭くて嫌だわ。ｎ＝ｋで成立することを仮定して、証明すべきことを証明しているのよ。そしたらその仮定だってあやふやのような気がするわ。白黒はっきりしなさいって感じよ。分かる、まなぶ。

＜まなぶ＞かず子にゃ、永遠と続くドミノ倒しの旅のような、男のロマンは分からないよ。ねっ、先生。

＜先　生＞帰納法にフィットしているまなぶの性格は理解したくないけどね。

あとがき

　条件式が不等式である場合、条件式を消去するということは、原式を別の不等式で近似することですが、その近似が緩ければ証明ができなくなってしまうこともあるわけです。実際、まなぶの方法では、指数関数を直線に近似させるわけですから、随分ゆるい不等式になってしまうことが分かるでしょう。

　そこで、条件式を最大限活かそうとするなら、
　　　Ｐ(ｋ)＞０　⇒　Ｐ(ｋ＋１)＞０
を示すには、
　　　Ｐ(ｋ＋１)＞Ｐ(ｋ)
を証明すると考えてもいいでしょう。

　(2)の場合、Ｐ(ｋ)＝２^k−(２ｋ−１)とおくと、
　　　Ｐ(ｋ＋１)−Ｐ(ｋ)＝２^k+1−(２ｋ＋１)−{２^k−(２ｋ−１)}
　　　　　　　　　　　　＝２^k−２≧０
　　　　∴　Ｐ(ｋ＋１)＞Ｐ(ｋ)＞０
となります。

　また、本文では、命題Ｐ(ｎ)の証明においてＰ(１)が真であることを最後に処理しています。アルゴリズム的にはＰ(１)から証明が出発すべきなのでしょうが、ドミノ倒しとの対比から帰納法の原理を説明するならば、
　　　「次のドミノが倒れるように並べていって、最後に１番目のドミノを倒す」
と考えた方が感覚的には分かり易くなります。帰納法の証明は、かず子が述べているように「仮定したもので証明を試みる」のですが、その違和感は、現実に最後に倒すことで解消できるわけです。

　ところで、数学的帰納法の証明プロセスは証明の状況に合せてデフォルメされます。その幾つかの形態を以下に触れてみましょう。

○ノーマルな数学的帰納法

自然数に関する命題をＰ(ｎ)とするとき、 (�T) Ｐ(１)が真 (�U) Ｐ(ｋ)が真ならばＰ(ｋ＋１)が真 (�V) (�T),(�U)より　すべてのｎに対してＰ(ｎ)は真

　(�T)については、
　　　(�T) Ｐ(ｒ)　（ｒ≧１）
とできます。成立の出発点の問題に過ぎません。

○累積型数学帰納法

自然数に関する命題をＰ(ｎ)とするとき、 (�T) Ｐ(１)が真 (�U) Ｐ(１)，Ｐ(２)，Ｐ(３)，・・・，Ｐ(ｋ)が真ならばＰ(ｋ＋１)が真 (�V) (�T),(�U)よりすべてのｎに対してＰ(ｎ)は真

○並列型数学帰納法

自然数に関する命題をＰ(ｎ)とするとき、 (�T) Ｐ(１)，Ｐ(２)，・・・，Ｐ(ｒ)が真 (�U) Ｐ(ｋ)，Ｐ(ｋ＋１)，Ｐ(ｋ＋２)，・・・，Ｐ(ｋ＋ｒ−１)が真ならばＰ(ｋ＋ｒ)が真 (�V) (�T),(�U)よりすべてのｎに対してＰ(ｎ)は真

ｒ＝２の場合は、この帰納法の証明パターンはよく利用されます。

ex) ２次方程式ｘ2＋ａｘ＋ｂ＝０（ａ，ｂ∈Ｚ）の２解をα，βとするとき、 　　　αn＋βn は整数であることを証明せよ。

証明)
解と係数の関係より、
　　　α＋β＝−ａ，αβ＝ｂ
これから、
　　　α²＋β²＝(α＋β)²−２αβ＝ａ²−２ｂ
よって、ｎ＝１，ｎ＝２のときは成立する。
次に、ｎ＝ｋ，ｎ＝ｋ＋１で成立すると仮定する。
α^k＋β^k，α^k+1＋β^k+1は整数とすると、
　　　α^k+2＋β^k+2＝(α^k+1＋β^k+1)(α＋β)−αβ(α^k＋β^k)
　　　　　　　　　＝−ａ(α^k+1＋β^k+1)−ｂ(α^k＋β^k)
よって、α^k+2＋β^k+2も整数である。
以上より、すべての自然数ｎで成立する。　　　Q.E.D

同様に、ｒ次方程式の解α_k (ｋ＝1,2,…,r)に対して、が整数であることは、並列型の帰納法により証明されます。

　この他のパターンとして、

○二重型数学帰納法

自然数ｍ，ｎに関する命題をＰ(ｍ，ｎ)とするとき、 (�T) Ｐ(ｍ，１)，Ｐ(１，ｎ)が真 (�U) Ｐ(ｍ，ｋ)，Ｐ(ｌ，ｎ)が真ならばＰ(ｍ，ｋ＋１)，Ｐ(ｌ＋１，ｎ)が真 (�V) (�T),(�U)よりすべてのｍ，ｎに対してＰ(ｍ，ｎ)は真

○退行型数学帰納法(backword-induction)

自然数ｎに関する命題をＰ(ｎ)とするとき、 (�T) ある自然数ｎに対してＰ(ｎ)が真 (�U) Ｐ(ｍ)が真ならばＰ(ｍ−１)が真 (�V) (�T),(�U)よりすべてのｍ以下のすべての自然数ｎに対してＰ(ｎ)は真

　この帰納法は、例えば相加・相乗平均の証明に使われます。
ｍ＝２^kの場合については、数学的帰納法により簡単に証明できます。このｍの仮定に対して、ｍ−１を証明することにより、すべての自然数で相加・相乗平均の関係が示されるわけです。

ところで、自然数の集合には

○超限帰納法

整列集合Ｘに関する命題をＰ(Ｘ)とする。 　　　任意のｙ(ｙ＜ｘ)に対して、Ｐ(ｙ)⇒Ｐ(ｘ)が成立する とき、すべてのｘ∈Ｘに対してＰ(ｘ)が成立する

　数学的帰納法はこのように、いろいろなパターンが考えられるわけですが、別の見方をすれば、証明法自体が不安定であるともいえます。
　数学的帰納法は、三段論法を発展されたものです。
　三段論法(カット法)は形式論理によってアリストテレスが考え、その後の数学者によって体系化されます。そして、それを土台にド−モルガンが数学的帰納法を完成させます。さらに、ペアノの公理の無矛盾性からゲンツェンは順序数における超限帰納法の論法に拡張しました。
　数学的帰納法が自然数の最小原理から得られるのなら、超限帰納法は自然数以外に最小原理を満たす集合(整列集合)を作れないかという発想から生まれたわけです。この結果、ゲンツェンは、
　　　三段論法で証明できることは、三段論法を使わなくても証明できる
というカット消去法なる結論にたどり着くのです。
　数学的帰納法はアキレスと亀の話のようにパラドックスの代表例としてよく話題になります。無限回の三段論法と考えれば起こりえるわけです。そういったパラドックスの解消のために、数学的帰納法は拡張されたと考えるべきでしょう。
　なお、今回の小手技は「ポアロの挑戦」なる短編小説と並行してまとめました。よろしければそちらの方もご覧ください。