第216回 プラスワンでどこまで行くの(後編)

数学的帰納法に似ている累積帰納法について「僕」がテトラちゃんに説明していくと……「無限を探そう」シーズン第3章後編。
登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。好奇心旺盛で根気強い《元気少女》。
$ \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\FBOX}[1]{\fbox{$#1$}} \newcommand{\LEQ}{\leqq} \newcommand{\ABS}[1]{\bigl|#1\bigr|} \newcommand{\LAND}{\land} \newcommand{\LOR}{\,\lor\,} \newcommand{\SETL}{\bigl\{} \newcommand{\SETM}{\bigm|} \newcommand{\SETR}{\bigr\}} \newcommand{\SETRDOT}{\bigr.} \newcommand{\SETLDOT}{\bigl.} \newcommand{\REAL}{{\mathbb R}} \newcommand{\VECV}[2]{\binom{#1}{#2}} \newcommand{\LOOKSLIKE}{\quad\longleftrightarrow\quad} \newcommand{\ZERO}{\bigl\{\,\bigr\}} \newcommand{\ONE}{\bigl\{\,\{\,\}\,\bigr\}} \newcommand{\TWO}{\Bigl\{\,\bigl\{\,\bigr\},\, \bigl\{\,\{\,\}\,\bigr\}\,\Bigr\}} \newcommand{\THREE}{\biggl\{\,\Bigl\{\,\Bigr\},\, \Bigl\{\,\bigl\{\,\bigr\}\,\Bigr\},\,\Bigl\{\,\bigl\{\,\bigr\},\,\bigl\{\,\{\,\}\,\bigr\}\Bigr\}\,\biggr\}} \newcommand{\BINREP}[1]{{#1}_{(2)}} \newcommand{\SEVENREP}[1]{{#1}_{(7)}} \newcommand{\NATURAL}{{\mathbb N}} $

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

ここは高校の図書室。いまは放課後。

僕は後輩のテトラちゃん数学的帰納法についておしゃべりをしている。
数学的帰納法

$P(n)$は、正の整数$n$についての数学的主張とする。

すべての正の整数$n$について$P(n)$が成り立つことを証明するには、 以下の《ステップA》と《ステップB》を証明すればよい。

《ステップA》 $P(1)$が成り立つ。

《ステップB》 どんな正の整数$k$についても、$P(k)$が成り立つならば$P(k+1)$が成り立つ。

「《ステップA》と《ステップB》を証明することで、 すべての正の整数$n$について$P(n)$が成り立つことが証明できる」 というこの証明法を、数学的帰納法という。

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

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

テトラ「はい?」

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

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

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

累積帰納法

$P(n)$は、正の整数$n$についての数学的主張とする。

すべての正の整数$n$について$P(n)$が成り立つことを証明するには、 以下の《ステップC》を証明すればよい。

《ステップC》どんな正の整数$m$についても 「$k < m$であるすべての正の整数$k$について$P(k)$ならば、$P(m)$が成り立つ」 がいえる。

「《ステップC》を証明することで、 すべての正の整数$n$について$P(n)$が成り立つことが証明できる」 というこの証明法を、累積帰納法という。

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

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

テトラ「これは《ステップ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》を読んでごらんよ。これが証明すべきこと」

累積帰納法の《ステップC》(証明すべきこと)

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

テトラ「ははあ……確かに、先ほどよりはわかりますね。この《$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》をもう一度見てみよう」

累積帰納法の《ステップC》(証明すべきこと)

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

テトラ「はい……」

「《どんな正の整数$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》の誕生

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

テトラ「はい」

累積帰納法の《ステップC》

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

「$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$とする。そして……」

問題

正の整数全体の集合を$\NATURAL$とする。 そして、$A$は$\NATURAL$の部分集合とする。 $A$が空集合でないならば、$A$の要素の中には最小値が存在することを示せ。
この続きは有料会員登録をすると
読むことができます。
cakes・note会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の女子高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わってください。本シリーズはすでに何冊も書籍化されている人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

koushi_1214 累積帰納法の証明がε-n論法に見えるwww https://t.co/Y6LfT6gMHY 6ヶ月前 replyretweetfavorite

koushi_1214 ステップCのP(n)っていうのは、命題関数やから、P(k)が成り立つならば、っている気がする… https://t.co/Y6LfT6gMHY 6ヶ月前 replyretweetfavorite

yiaudy k=1,2,...m-1ではなくk<mの理由はこう説明すればいいのか! 今まで漠然としていたことが鮮明になって嬉しい "例示は理解の試金石" わかっていても難しい。。。 #数学ガール https://t.co/SWalGh8Moa 6ヶ月前 replyretweetfavorite

chibio6 累積帰納法、実際に問題を解けるかはわからないけれど、名前を聞いただけで考えるのをあき… https://t.co/rJD6tYecIV 6ヶ月前 replyretweetfavorite