『数学的帰納法のトリセツ』

締切済

質問者：wonderlasting
質問日時：2022/06/06 07:34
回答数：4件

数学的帰納法。それは強力で美しくさえある証明法でしょう。ある数学者は、数学という宝冠を飾る宝石の一つ、と評しています。しかし、如何に強力でも、自ずと適不適があると思います。問題によっては、向いていない場合もあるでしょう。では、帰納法の取り扱い方とは？
具体的に例え話をしたほうが分かりやすいと思いますので、次に数学のこぼれ話的に一例を紹介したいと思います。なお、長くなりますので、退屈しないよう脚色しております。ご了承ください。

ある街に、GさんとBaさんという二人の数学好きがおりました。ある日、Baさんが洗濯をしようとしているところに、Gさんが息せき切ってやってきました。
「どうしたんだい、Gさん」驚いたBaさんが尋ねますと、「数学の難問の証明に成功したんだよ」
　とＧさん。
「へえ、そうかい」これまで何度もこんなGさんの”驚き話”に付き合わされてきたBaさんです。
「のほほんとしている場合じゃないよ。なんせ、四色問題だぜ」
（四色問題は御存知の方も多いと思いますが、簡単に説明すると、平面上にある地図で、境界線を接して隣り合う国同士が異なる色になるように塗り分けるには四色あれば必要にして十分という予想です）
「なんだ、四色問題ならとっくに解決済みじゃないか」
「それは、コンピュータを使って虱潰しに調べた実証だろ。俺は論理的に証明したんだ。論証だよ！誰も何十年も成功しなかった、さ」
「それで？」
「証明には数学的帰納法を使うんだ。まず、１０とか２０ぐらいの比較的少数の国で四色でできることを示す。コンピュータを使えば可能な配置の仕方全てについて秒殺だろ」
「ふんふん、それで」
「そんで、国の数n=kのとき成り立つと仮定して、n＝k＋１のときにも成り立つと示せればいいんだ」
「そんなにうまくいくのかい？」
「ああ！そもそも四色で足りるってことは、四色が必要な配置になった時、四色のうちの一色が、五色目が必要になるような国の接触から遮断されるように、他の三色の国で囲まれてるってことさ。あるいは、三色で間に合う配置の部分があっても、四色目が必要なように国同士の配置を変えたとき、やはり、囲まれるようになっちまうってことだよ。そうだろ？」
「あ、ああ、まあそうなんだろうな」
「そうなんだよ！それで、まずは少数の場合について、これを実地に確認する。これは、まあ、実証ということになるが」いったん、休んで、また話を続けるGさん。
「次に、n＝kのとき成り立つと仮定して、n＝k＋１のとき、つまり新たに一国を追加した時どうなるか」
「どうなるんだい？」
「今、説明した状況のところに追加することになると、どんな追加、配置の仕方をしても、その一国が置かれる状況は非常に限られたパターンの配置になる。そのため、結局、四色の内の一つは、五色目が要らないよう、遮断された、または、遮断さるようになる状態に置かれるって寸法さ」
満足げに話し終えたGさんでした。が、
「ほんで、その”非常に限られたパターン”てのは、具体的にどんなん？」とBaさんが質問しますと、
「ええっと、それは…」と急に、シドロモドロになって汗を滲ませ始めたGさんは、「あっそうだ！隣の庭の芝刈りをする約束だった。行かなきゃ！」と言ってソソクサと芝刈りに行ってしまいました。
呆気にとられたBaさんは、肩をすくめてやりかけの洗濯に取り掛かりましたとさ。めでたしめでたし。

以上です。ここで語られる”非常に限られたパターン”なるものがいかなるものか、非常に気になるところですが、要点は最初に述べたとおり、数学的帰納法の使い方なのです。このようなグラフ理論（と思いますが）の問題に帰納法をこのように使うのは、いささか乱用というものでしょう。では、グラフ理論に限らず、数学的帰納法を使用するに相応しい問題とは？
熟考を重ねた結果、次の２点になりました。
①問題に出てくるパラメータが自然数、せめて、整数の変化をすること
②証明する関係が定量的に数式、方程式の形をとっていること（例えば、数列の一般項の式）
言われてみれば当たり前ではないか、とも思いますが、ということは、一般的にも言えることだとも思います。他にはないでしょう…（でも、本当に？）。