第216回 シーズン22 エピソード6

プラスワンでどこまで行くの（後編）

数学的帰納法と累積帰納法

テトラ「《ステップA》と《ステップB》の二つのことをしっかり理解していれば、 数学的帰納法は恐くないですねっ！」

僕「……数学的帰納法といえば、思い出したことがあるよ。 せっかくテトラちゃんは二つのステップといってくれたけれど、 これを一つのステップにする方法もあるんだ」

テトラ「はい？」

僕「いまのテトラちゃんなら混乱しないと思うから話すけど、 累積帰納法（るいせききのうほう）という証明法もあるんだよ」

テトラ「累積帰納法……」

僕「うん、累積帰納法はこういう形をした証明法」

テトラ「……む、難しいですね」

僕「慣れないとややこしく感じるよね」

テトラ「これは《ステップA,B,C》の三つが必要という意味ではなく、 《ステップC》一つだけを証明すればいいということですか？」

僕「そういうことだよ。対比のために《ステップC》なんていっちゃったけど、 たった一つしかないからステップでもなんでもない。 ただこの一つだけ証明できればいい、というのが累積帰納法」

テトラ「$n$ や $m$ や $k$ という文字がちらちらして、 考えがまとまらないんですが、 これは $m$ より小さい数で成り立つかどうかを調べようとしているのでしょうか？」

僕「うん、誤解がないように文字を分けて書いているから、 わかりにくいかもしれないね。少し噛み砕いて説明するよ」

テトラ「飲み込みが悪くてすみません……」

累積帰納法をざっくりと

僕「まずはざっくりとした説明をするね。 テトラちゃんも言ってくれたけど、 数学的帰納法はドミノ倒しみたいだったよね。 特に《ステップB》は」

テトラ「そうですね。ドミノが一つ倒れたら、 必ず次のドミノが倒れるという証明法」

僕「うん。数学的帰納法の《ステップB》は、 《$k$ 番目のドミノが倒れたら、 $k+1$ 番目のドミノが倒れる》 ということだった」

テトラ「はい」

僕「それと比較すると、累積帰納法の《ステップC》は、どんな $m$ についても、 《$1,2,3,\ldots,m-1$ 番目のドミノがすべて倒れたら、 $m$ 番目のドミノが倒れる》を証明しようということ。 それさえ証明できればいい」

テトラ「ははあ……なるほど。ドミノ一つで次が倒れるんじゃなく、 そこまでのドミノがぜんぶ倒れるなら、次が倒れることが証明できればいい？」

僕「そうそう、そういうこと。 $1$ から $m$ 未満のドミノが累積している感じだね。 だから累積帰納法」

テトラ「そういうお話なら、なんとなくわかるような気がします。 でも、先ほど書いてくださった累積帰納法の説明からそれを読み取るのは難しいです……」

僕「そう？　ざっくりとイメージをつかめたところで、 もう一度《ステップC》を読んでごらんよ。これが証明すべきこと」

テトラ「ははあ……確かに、先ほどよりはわかりますね。 この《$k < m$ であるすべての正の整数 $k$ について》 というところがポイントでしょうか……」

僕「まあ、そうだね」

テトラ「あたしの敗因は、 $k < m$ であるすべての正の整数 $k$ というところで、具体的に想像しなかったところにありそうです。 先ほど先輩は、 $1,2,3,\ldots,m-1$ と説明してくださいました。 これはスッと理解できました。 $k < m$ と同じことをおっしゃっていますよね。 $k < m$ で $k$ は正の整数なんですから、 $k = 1,2,3,\ldots,m-1$ ということ。具体的でわかりやすいです」

僕「うんうん」

テトラ「あ、あのう……自分のトロさを棚に上げるようで申し訳ないんですが、 どうして最初から $k = 1,2,3,\ldots,m-1$ となさらないんでしょうか。 ずっと具体的でわかりやすいのに」

僕「テトラちゃんはトロくなんかないよ。 テトラちゃんの気持ちはよくわかる。 $k$ が正の整数なんだから、 $k < m$ なんて回りくどいこと書かずに、 $k = 1,2,3,\ldots,m-1$ と書けばいいじゃないか……ということだよね」

テトラ「はい……」

僕「でもね、このテンテンがくせものなんだよ。 たとえば、 $m = 4$ のときは、 $k < m$ というのは $k = 1,2,3$ ということだよね」

テトラ「そうですね」

僕「$k = 1,2,3$ という並びなのに、 $k = 1,2,3,\ldots,m-1$ と書いていいのかどうか……」

テトラ「ああ、テンテンのところには何も入らず、 しかも $m - 1$ は $3$ になってしまうからですね。 つまり $k = 1,2,3,\ldots,3$ という変な形になってしまうと。 でも……そのくらいは想像で補えます」

僕「だったら、 $m = 3$ のときはどうだろう。 $k < m$ は $k = 1,2$ だよね」

テトラ「なるほどです。 今度は、 $k = 1,2$ を $k = 1,2,3,\ldots,m-1$ と書くことになる……」

僕「そうだね。 $k = 1,2$ に $3$ は出てこないのに、 $k = 1,2,3,\ldots,m-1$ なんて書いていいんだろうか」

テトラ「そ、そのくらいは想像で……あっ、最初と最後だけ書けばいいんですよ。 $k = 1,\ldots,m-1$ にして！」

僕「うーん、それだと列挙してわかりやすくするメリットがなくなるし、 $m = 2$ のときは、 $k < m$ は $k = 1$ だけになっちゃうから、同じことだよね」

テトラ「そうですね……やはり $k < m$ の方が正確に表せる？」

僕「そうなんだよ。説明のときは $k = 1,2,3,\ldots,m-1$ は便利なんだけど、 証明のときには $k < m$ と書いた方が正確になる」

テトラ「理解しました」

僕「$k < m$ と書く、もっと大事な理由もあるんだ」

テトラ「大事な理由……？」

空ゆえに真

僕「そうだよ。 それは $m = 1$ のときに $k < m$ が何を意味しているかを考えるとわかる。 $k$ は正の整数として、 $m = 1$ のとき $k < m$ は何を意味すると思う？」

テトラ「$m = 1$ ですから、 $k < m$ は $k < 1$ ということですよね。 $k$ は正の整数ですから……あらら？　 $k < 1$ なんて $k$ はありません」

僕「そうなるね。だから、 $m = 1$ のとき $k < m$ は成り立たない。 $k < m$ を成り立たせるような正の整数 $k$ は存在しない」

テトラ「……」

僕「累積帰納法の《ステップC》をもう一度見てみよう」

テトラ「はい……」

僕「《どんな正の整数 $m$ についても「ナントカ」がいえる》という形になっているから、 $m = 1$ として「ナントカ」の部分を考えてみると、

「$k < 1$ であるすべての正の整数 $k$ について $P(k)$ が成り立つならば、 $P(1)$ が成り立つ」

という形になるよね？」

テトラ「ええと……は、はい」

僕「ここで注目したいのは、ここ。

「$k < 1$ であるすべての正の整数 $k$ について $P(k)$ が成り立つ……」

これは、真だろうか、それとも偽だろうか？」

テトラ「$k < 1$ という正の整数はありませんから……わかりません」

僕「うん。これは真なんだよ」

テトラ「どうしてでしょう。 $P(k)$ が成り立つかどうか調べようがありません！　 偽とまではいえないかもしれませんが、真と言い切れるんですか？」

僕「言い切れるんだ。こんなふうに言い換えてみるよ。

　 $k < 1$ であるすべての正の整数 $k$ について $P(k)$ が成り立つ

　　↓　言い換え

　 $P(k)$ を成り立たなくさせる正の整数 $k < 1$ は存在しない

今度はどう？」

テトラ「むむむむ……少し、わかってきましたよ。 《すべての $k$ について成り立つ》は、《成り立たないような $k$ は存在しない》と同値？」

僕「その通り！　《すべての $k$ について成り立つ》ということは、 《反例になるような $k$ は存在しない》ということ。 そもそもあたえられた条件 $k < 1$ の範囲に正の整数は存在しないんだから、 反例を見つけようがない。だから、

　 $P(k)$ を成り立たなくさせる正の整数 $k < 1$ は存在しない

は真になるし、

　 $k < 1$ であるすべての正の整数 $k$ について $P(k)$ が成り立つ

も真になるということ」

テトラ「反例を見つけようがないから真！　なるほど！」

僕「こういうパターンは《空ゆえに真》と呼ばれることもあるよ。 そしてこれは $A$ が偽のときに《$A$ ならば $B$》が真になるというパターンと似てる」

テトラ「そこまでわかりました……が？ Where were we?（何の話でしたっけ）」

《ステップA》の誕生

僕「累積帰納法だね。もう一度見てみよう」

テトラ「はい」

僕「$m = 1$ のときは、 《$k < m$ であるすべての正の整数 $k$ について $P(k)$》が真になるという話をしてたんだ。 だから、《ステップC》の中で、 $m = 1$ のときは、

　真ならば $P(m)$ が成り立つ

を証明しなくちゃいけない。 $m = 1$ なんだからこれは、

　真ならば $P(1)$ が成り立つ

つまり、

　 $P(1)$ が成り立つ

を証明しなくちゃいけないということ。これは数学的帰納法でいうところの《ステップA》になるんだね」

テトラ「うううう……ちょ、ちょっと待ってください。 たぶん理解したんですが、理解してません。言葉にしますから、もうちょっとお待ちください」

僕「待ってるよ」

テトラ「……これって、累積帰納法って、数学的帰納法を折り畳んでいるみたいです」

僕「なるほど？」

テトラ「《ステップC》ひとつでいいとはいっても、 $m = 1$ のときには結局 $P(1)$ を証明しなくてはいけないわけですから、 《ステップA》と同じことをやらざるを得ないですよね。 《ステップC》ひとつに折り畳んでまとめても、証明はさっぱり楽になっていませんが……」

僕「累積帰納法は数学的帰納法の変形みたいなものだからなあ……でも、 累積帰納法は $P(m)$ の証明をするときに、 $k < m$ のすべての $P(k)$ を使えるという利点はあるかも」

テトラ「むむむ……武器が多いと？」

僕「まあね」

累積帰納法を使う

テトラ「先輩！　何か問題出していただけませんか？」

僕「えっ？」

テトラ「あたし、累積帰納法を使ってみたいです！　テトラはいま、 《すべての正の整数 $n$ についての数学的主張》を切望してます！」

僕「すごいなあ……じゃあね」

テトラ「フィボナッチ数列以外の問題を待望しています！」

僕「え……ええと……」

ミルカ「それなら、これはどうだろう」

僕「うわっ」

テトラ「ミルカさん！」

僕「びっくりするなあ」

ミルカ「正の整数全体の集合を $\NATURAL$ とする。そして……」