1から始める帰納法
真白「何故だかよくわからないけど、数学的帰納法の話をしようと思うのだよ」
蒼井「唐突ですね」
真白「優秀なわたしが、懇切丁寧に授業をしてあげるんだから感謝してね。蒼くん、紅ちゃん、と……だれ？」
山城「山城 新です。中3です(4章 文化祭2日目に登場予定)」
真白「なんで大くんじゃないのー？」
山城「大白先輩は授業で普通に帰納法習ってるはずだから、ここでは別のキャラを出そうって作者が考えたからだそうです」
真白「メタいね！？ いいけどさ。さて、3人は数学的帰納法ってなんだか知ってるのかな？」
蒼井「知っています」
紅林「なんとなくなら」
山城「知りません」
真白「うん。山くん。いて正解だね。てか、蒼くん、いなくていいよね」
蒼井「主人公なので」
真白「メタいよ！ こっちの話ではそういうノリなんだね。わたしがツッコミ役とか、おかしい」
蒼井「本題に戻りますと、数学的帰納法ってのは証明で用いる手法のひとつで、高校では数学Bで習うことになってますね」
真白「あれ、蒼くんが解説していく感じなの？ わたしの役割は？」
山城「そもそも帰納ってなんですか？」
蒼井「それに関しては部長が素晴らしい解説をしてくれます」
真白「ここで丸投げなの！？ いや、いいよ。わたしが解説してあげようじゃあないか！ そもそも、数学的帰納法と普通にいう帰納法ってのは完全に別物。先に普通の帰納法の話をしよっか。帰納と対になる言葉はなんだかわかるかな？」
山城「そもそも帰納ってなんだかわかってないんで」
真白「紅ちゃんは？」
紅林「演繹ですか？」
真白「そう！ 演繹。帰納法と演繹法ってのはどっちも推論の方法なんだよ。演繹法ってのは、いわゆる三段論法からなる推論のこと」
山城「三段論法って、AならばBで、BならばCだったら、AならばCみたいなやつですか？」
真白「そんな感じかな。例えば、人間は死ぬ、ソクラテスは人間である、したがって、ソクラテスは死ぬってやつ」
山城「なんでいきなりソクラテス……」
真白「そういう例が昔から定番なんだよ！ わたしはいきなりソクラテスとか言い出す不思議ちゃんじゃないからね！」
蒼井「対して帰納法は」
真白「対して帰納法は！ 経験則的なやつ。今まで見たカラスは全て黒かった、したがってカラスは黒い的なの」
山城「経験則ですか。なるほど」
真白「そうそう。それが帰納法による推論。でも、この帰納法って結局はたぶんこうだろうなぁっていう予想に過ぎないんだよね。数学の証明で、この帰納法ってOKだと思う？」
山城「ダメですか？」
真白「例えば、奇数+奇数=偶数を証明しろって問題で、1+1=2で偶数、1+3=4で偶数ってのを100個くらい書いて、これで帰納的に証明できたってのはあり？」
山城「ダメですね、それは」
真白「数学では、成り立つ例が無数にあったって、反例が1つでもあればアウトだからね。つまり、帰納法ってのは推論の方法であって、証明の方法ではないってこと」
山城「じゃあ、なんなんですか、数学的帰納法って。それは証明の方法なんですよね？」
真白「その話をしていこう。帰納法ってのは、いくつか具体例を見て結果を予想する方法だったよね」
山城「さっきまで話してた帰納法ですよね。なら、はい、そうです」
真白「具体例を見ていって証明とするためにはどうすればいいか。答えは簡単で、条件に合うものを全部確かめればいい」
山城「えっと？」
真白「例えば、1〜1000までの整数はある性質を持つ、みたいな問題だった時に、1ならOK、2ならOK、ってのをどんどんやっていって、1000まで全部確認すれば、それは証明できたってことになるよね？」
山城「カラスは黒いの例だと、世界中にいるカラスを全部見てきて、黒いのを確認したら、全部見てきたんだから、例外なくカラスは黒いってことが証明できた、みたいな？」
真白「そう。とにかく、考えているものを全部確認すれば、それで証明したことになるよね」
山城「それって、超強引じゃないですか？ 1〜1000までの整数なら1000個確認しないとですよね。やってらんない感じが」
真白「もちろん、馬鹿正直にはやってられない。でも、まず前提として、数学的帰納法ってのは考えるものを全部確認して、これで証明できたぜってやる強引な方法だってこと」
山城「わかりました」
真白「さて、だから、目標は全部確認すること。でも、さっきも言ったように馬鹿正直に全部確認するなんてやってられない。考えているものが有限個ならできなくもないけど、自然数みたいに無限にあるものを考えるから、なおさら本当に全部確認するのは絶対無理」
紅林「それでドミノ倒し」
真白「そうそう。ドミノ倒しー」
山城「ドミノ倒し？」
真白「数学的帰納法はよくドミノ倒しに例えられるんだよ。帰納法が使える相手は色々いるんだけど、わかりやすくするために、調べたいものは自然数ってことにしよう。
問題、すべての自然数nに対して、
2(1+2+…+n)=n(n+1)
を証明せよ」
蒼井「普通に等差数列の和の公式使って1発ですね」
真白「蒼くん、空気読もうね！」
蒼井「部長が空気読めなんて……！？」
真白「わたしの邪魔をするなー！」
蒼井「その言い方だと部長っぽいですね」
山城「さっきの問題、数学的帰納法でやるんですよね？」
真白「そのつもりで言った。蒼くんは放っといてOK」
山城「1とか2だと成り立ってるのはすぐにわかりますけど、これをどこまで？」
真白「調べてるのが自然数全部だから、馬鹿正直に全部確認するのは無理。自然数は無限にあるからね。そこで、ちょっとした工夫をするのだ！」
山城「工夫ですか？」
真白「ドミノ倒しだよ。えっとね、どう説明したらいいかな。1個前のがOKなら、その後のもOKだよって話なんだけど」
蒼井「ネット小説で、1話を読んだなら2話も読む、2話を読んだなら3話も読むみたいに、前の話を読んだなら次の話も読む人がいたとします」
真白「なんかメタい例だなぁ」
蒼井「その人が何話を読めば、必然的に全話を読むことになるのか」
山城「1話ですよね？ 1話を読めば、2話を読むし、それから3話、4話って読むことになります」
蒼井「そのネット小説が仮に無限に続いても、"1話を読む"と"前の話を読んだなら次の話も読む"が成り立つなら、全部読むことになるね？」
山城「続く限りは、読むことになるとは思います」
蒼井「今の話をもう少し数学的帰納法っぽく言うと、"1話を読む"と"k話を読んだならk+1話も読む"が成り立つなら、"すべてのnについて、n話を読む"が成り立つことになる」
山城「なんとなく言いたいことはわかります」
蒼井「これを元の数学の話に戻せば、"n=1で成立すること"と"n=kで成立するならn=k+1でも成立すること"を示せば、"すべての自然数nについて成立する"が言えるってことになる」
山城「ちょっと無理矢理感ありますけど、わかりました。たぶん」
蒼井「整理すると、自然数を相手にする時の数学的帰納法っていうのは2つのステップに分けられて、
1. n=1の場合を示す
2. n=kで成立すると仮定して、n=k+1でも成立することを示す
ってことになる」
真白「実際にはもう少し手の込んだ問題もたくさんあるけどね。とりあえず今は1番単純な例としてこれでいこう。つまり、自然数を相手にする帰納法は、必ず1から始めるってことだね」
紅林「タイトル回収ですね」
真白「1から始める帰納法！」
蒼井「部長のドヤ顔タイムはここまでにして、本題に戻りましょう」
真白「うん。で、さっきの問題」
山城「問題なんでしたっけ？」
真白「すべての自然数nに対して、
2(1+2+…+n)=n(n+1)
を証明せよ」
山城「n=1は明らかに成立してますよね。次は、kまで成立するとしてk+1」
真白「実際に答案を書いてみようか」
『proof)
数学的帰納法によって示す。
1) n=1の場合
(左辺)=2=(右辺)より成立』
真白「ここまではいいよね。そして、次」
『2) n=kで成立するとして、n=k+1の場合 (k≧1)』
真白「左辺を変形して、右辺まで持っていきたい」
山城「今考えているのは、n=k+1なんですよね。だと、
(左辺)=2(1+2+…+k+1)
これ、どうするんですか？」
真白「帰納法の仮定を使うんだよ！ 今、何を仮定してる？」
山城「n=kで成立すること。つまり、
2(1+2+…+k)=k(k+1)
ですね。これを使うとすると、
2(1+2+…+k+(k+1))
=2(1+2+…+k)+2(k+1)
=k(k+1)+2(k+1)
ですか？」
真白「案外すんなりわかったね」
蒼井「ここでわからないと言われると、どう対応したらいいか作者がわからなかったからですね」
真白「だからメタいよ！ 出てきた式を共通因数でくくると？」
山城「(k+1)(k+2)ですね」
真白「右辺のnにk+1を代入すると？」
山城「(k+1)(k+2)ですね。つまり、これで証明終了ってことですね」
蒼井「実際に問題を解く時は、先に右辺がどういう形になっているかを確認して意識していた方がいいですね。目的地が見えている方が、方針が立てやすいので」
真白「そうだね。さて、今のをちゃんと答案にするなら」
『すべての自然数nに対して、
2(1+2+…+n)=n(n+1)
を証明せよ
proof)
数学的帰納法によって示す。
1) n=1の場合
(左辺)=2=(右辺)より成立。
2) n=kで成立するとして、n=k+1の場合 (k≧1)
(左辺)
=2(1+2+…+k+1)
=2(1+2+…+k)+2(k+1)
帰納法の仮定より、
=k(k+1)+2(k+1)
=(k+1)(k+2)
=(右辺)
よって、成立
(1),(2)より、すべての自然数nに対して主張は成り立つ//』
山城「なんとなくわかった気がします、数学的帰納法」
真白「じゃあ、同じ手法だけど、もう少し考えづらい問題。
すべての自然数nに対して、n段のハノイの塔は解答可能であることを証明せよ」
蒼井「最短手数を求めよは定番ですけど、解答可能性を問うのは珍しい気もしますね」
山城「ハノイの塔って、えっと、なんか、小さいのの上に大きいのは乗せられない的な」
真白「うーん、ここでルールの説明をするのは煩雑だから。うん。ググって」
山城「はい」
山城「ルール確認しました」
真白「よし、じゃあ、問題やっていこう」
山城「解答可能であることを示せって、正直どうしたらいいかさっぱりなんですが」
真白「蒼くんと紅ちゃんは？ いや、蒼くんはいいや」
蒼井「あっ、はい」
紅林「数学的帰納法でやるんですよね。なら、まずはn=1のとき、1段のハノイの塔は明らかに解答可能です」
真白「1個動かすだけだからね。当たり前だね」
紅林「次は、n=kで解答可能であると仮定して、n=k+1で解答可能であることを示せばいいってことで」
真白「そうそう」
山城「n=kで解答可能ってことは、k段いっぺんに動かすのはOKってことですか？」
真白「その通り！ そこまでくれば解けたも同然！」
山城「えっと、つまり」
『すべての自然数nに対して、
n段のハノイの塔は解答可能であること
を証明せよ
proof)
数学的帰納法によって示す。
1) n=1の場合は明らか
2) n=kで成立するとして、n=k+1の場合 (k≧1)
n=kで成立するので、k段を任意の柱に移動することは可能。
上からk段を隣の柱に移動する。
残り1段を3つ目柱に移動する。
先に移動させたk段を3つ目の柱に移動する。
上記の手順で、k+1段のハノイの塔は解答可能。
(1),(2)より、すべての自然数nに対して主張は成り立つ//』
山城「こうですか？」
真白「おお！ さすがだね！ わたし、君のこと全然知らないけど」
蒼井「この議論から漸化式が立って、最短手数も求められますね」
真白「そうだけど、今はいいや。帰納法についての理解を深める会だから。それじゃ、ちょっと方法が変わる問題。
あるゲームに関する問題ね。先に決めたある自然数nから順番に降るように2人で数字を言い合うゲーム。それで、1を行った方の勝ちとする。1人が1度に言える数字は3個まで。えっと、ルールわかった？」
山城「えーっと」
蒼井「いわゆるニムゲームってやつですね。部長と僕で1度実演しましょう」
真白「わかった。じゃあ、n=16で蒼くん先行でいい？」
蒼井「……。えっと、僕の負けですね。まぁ、いいですよ。16、15」
真白「14、13」
蒼井「12、11、10」
真白「9」
蒼井「8」
真白「7、6、5」
蒼井「4」
真白「3、2、1！ わたしの勝ち！」
蒼井「ルールはこんな感じです」
山城「わかりました」
紅林「私も大丈夫です」
真白「で、このゲーム、ニムゲームって言うと1言った方が負けって方がメジャーな気もするけど、面倒だからニムゲームって言うよ。
このニムゲームが、nが4の倍数のときに後手必勝であることを証明せよ」
蒼井「その通りではありますけど、それだと解法がわかりづらい気もします。プレミしない前提で、4の倍数を言った方が負けることを示せの方がいいかと」
真白「mを4の倍数とするとき、mを言った方が負けることを証明せよ。そうだね。そこから系として、nが4の倍数のときに後手必勝であり、そうでない時には先手必勝ってのが出てくるね。改めて、問題、
mを4の倍数とするとき、
mを言った方がニムゲームで敗北することを証明せよ」
山城「これも数学的帰納法でできるんですか？ だと、最初はm=1で……ん？」
真白「絵に描いたような反応。完璧だね」
山城「1って4の倍数じゃないですよね。4から始めるんですか、これ？」
真白「察しがいいね！ こういう、〜の倍数系の帰納法を使う問題ってのは結構見るよ。その中で最初のものから始めよう」
蒼井「正確に言うなら、〜の正の倍数系の問題ですね」
真白「そだね」
山城「まず、4の場合ですよね」
真白「そう！ 4から始める帰納法！」
山城「あっ、はい。えっと、4を言った方が負けるのは、4を言った場合、4で終わるか、3で終わるか、2で終わるかしかなくて、相手が次に1を必ず言えるからですよね？」
真白「そうだね。じゃあ、次だ」
山城「m=kで成立と仮定して、m=k+1、これも変ですね。kが4の倍数だと、k+1って4の倍数じゃありませんから」
真白「その通り」
山城「4の倍数にしないといけないので、m=kで成立と仮定して、m=k+4でいいんですか？」
真白「そだよー。m=4kで成立すると仮定して、m=4(k+1)でやることもあるけど、まっ、一緒だよね」
山城「n=kで成立を仮定してるから、kを言ったら負ける。k+4を言うと、k+4、k+3、k+2のどれかで終わって、相手はどの場合でもk+1で終われる。すると、kを言ってしまうことになる？」
真白「証明終了ー！」
山城「答案をどう書けばいいかわからないです」
真白「今言ったことをそのまま書けばいいんだよ。数学の答案なんて、採点者が読んでわかればなんでもいいんだから」
『すべての4の正の倍数mに対して、
mを言った方がニムゲームで敗北することを証明せよ
proof)
数学的帰納法によって示す。
1) m=4の場合
4を言ったプレイヤーは、4,3,2のいずれかで終わることとなり、次の手番で相手が1を言えるため敗北する。よって、成立。
2) m=kで成立するとして、m=k+4の場合 (k≧4で4の倍数)
n=kで成立するので、kを言ったら敗北することはよい。
k+4を言ったプレイヤーは、k+4,k+3,k+2のいずれかで終わることとなり、次の手番で相手はk+1で終わることができる。よって、さらに次の手番でkを言うこととなり敗北する。よって、成立。
(1),(2)より、すべての4の倍数mに対して主張は成り立つ//』
真白「こんなんでいいよ」
山城「なるほど」
真白「さて、次はもう少し変なやつ。
2以上のすべての自然数nに対して、
素因数分解が可能であることを証明せよ(一意性までは示さなくてよい)」
蒼井「整数環はユークリッド整域なので、一意分解整域であることは当たり前で」
真白「いや、そういうのじゃなくてもっと初等的に！ というより、蒼くんはそこまで数学を知ってる設定なの！？」
蒼井「すみません。小説『道徳の解答の作り方』内の蒼井陸斗はここまでの知識は持ってないです」
真白「じゃあ、君は誰なんだよ！！」
蒼井「短編『1から始める帰納法』内の蒼井陸斗ですね」
真白「別人なの？」
蒼井「さぁ、どうでしょうね。それより、素因数分解の存在性でしたね。少し手法を変える必要がありますね」
真白「言っても帰納法だから、まずは手を動かそうか。1の素因数分解については本によるところもあるから、今回は2以上の自然数ね」
山城「まずは確認するもののうち最小のものを見るので、n=2の場合ですよね。えっと、素因数分解が可能って何を言えばいいんですか？」
真白「有限個の素数の積で表せることを言えばいいよ」
山城「n=2の場合は、2自身が素数なんで、それでOKですか？」
真白「うん。それ自身が素数ならもちろんOK」
山城「次は、n=kで成立として、n=k+1の場合ですよね」
真白「そこが問題なんだけど、考えればわかるよ」
山城「考えればですか？ kは有限個の素数の積で書ける。このとき、k+1も有限個の素数の積で書けるか。……何すればいいのかさっぱりなんですが」
真白「蒼くん、ヒント」
蒼井「まず、k+1が素数か否かで場合分けしましょう」
山城「えっと、k+1が素数のときはOKですよね？ 2のときとおなじで」
真白「うん。そうだよ」
山城「k+1が素数じゃないとき。素数じゃない。1とその数自身以外で割れる。えっと」
真白「紅ちゃん、ヒント」
紅林「えっ！？ あ、えっと。そうですね、えっと」
真白「待って、紅ちゃんはこれ解けてる？」
紅林「すみません。わかってません」
真白「謝らなくていいよ。そうだなぁ。合成数ってことは、何かしらの数の積で書けるよね？」
紅林「はい。割れるので。k+1=abとなる自然数a,bがあります」
真白「a,bの範囲は？」
紅林「k+1より小さいです。えっと、あと、1ではありません」
山城「2からkまでですね」
真白「そう！ 2からkまで！ ここで帰納法の仮定を見直そう」
紅林「kでは素因数分解可能。有限個の素数の積で書けるもの2つの積は当然有限個の素数の積で書けるから、aとbが素因数分解可能であることを示せればいい」
山城「a,bがkならOKですけど、今はたぶん違いますよね」
紅林「kとk+1は互いに素なので、間違いなく違う」
真白「そうじゃないの！ 仮定そのものを変えるの！」
蒼井「帰納法はドミノ倒しに例えられるわけですが、今回のドミノは一直線に並んでません。倒れてるドミノは全部使うつもりでいきましょう」
紅林「あぁ、2からkまで」
真白「そう、2からkまで」
山城「どういうことですか？」
紅林「仮定を、n=kで成立じゃなくて、2からkまでのすべての自然数で成立にするんですね。k+1を考えるなら、kまでは全部成立していると考えていい」
真白「そのとおーりっ」
紅林「仮定をこう変えれば、a,bは仮定から素因数分解可能なので、積ab、つまりはk+1は素因数分解可能です」
真白「Q.E.D！」
『2以上のすべての自然数nに対して、
素因数分解が可能であることを証明せよ(一意性までは示さなくてよい)
proof)
数学的帰納法によって示す。
1) n=2の場合
2は素数なので明らか。
2) 2からkまでのすべての自然数で成立するとして、n=k+1の場合 (k≧2)
k+1が素数であるなら成立。
k+1が合成数の場合、
k+1=ab (a,bは2からkまでの自然数) と書ける。
帰納法の仮定から、a,bは素因数分解可能(有限個の素数の積で書ける)。よって、その積abも素因数分解可能。よって成立。
(1),(2)より、2以上のすべての自然数nに対して主張は成り立つ//』
蒼井「素因数分解については一意性の証明の方が厄介ですよね。同一法ですか」
真白「そうだけど、その話は今はいいよ。今の問題のまとめとして、帰納法には、1個前だけを仮定するんじゃなくて、1個前まで全部を仮定するパターンもあるよってこと」
蒼井「全部と言わないまでも、2個とか3個とかを仮定するパターンもありますね。フィボナッチ数列関係の問題なんか、そういうのが多い気がします」
真白「他に帰納法の話だと、無限降下法のことを、後ろ向き帰納法って言うこともあるらしいね」
蒼井「無限降下法ですか。次々に下がっていくのは帰納法っぽいですけど、調べたいものを全部網羅しようっていう導入から帰納法を見ていると、なんか違う感じがします」
真白「じゃあ、無限降下法はやめて。変数が2つのやつをやろっか。
n
ΣpCk・pC(n-k) = (p+q)Cn
k=1
を証明せよ」
蒼井「急に難しくないですか？ ヴァンデルモンドの畳み込みですよね、それ。なんとなく記憶にある証明が帰納法ではないのですが……」
山城「なんか、ついていけない感出てます」
真白「じゃあ、これは蒼くんに向けた課題ってことにして、別のをやろう。超限帰納法の話する？」
蒼井「高校課程で習わないのでパスでいいと思います」
真白「なんかお開き感が漂ってきたから、最後の問題！
すべての非負整数nに対して、
1+5+9+…+(4n+1)=n(2n+3)+1
を証明せよ」
蒼井「別に、普通に帰納法使うなり、等差数列の和の公式使うなりすればいいだけですよね」
山城「それならもう解けますよ。非負整数ってのは、0と自然数ですよね。なので、まずは0の場合ですね」
真白「そう、0からだよ！ 0から始める帰納法！」
蒼井「そのネタがやりたかっただけですか……」
山城「n=0の場合は、両方1なんでOK。次にn=kで成立するとして、n= k+1の場合。
(左辺)
=1+5+…+(4k+1)+(4k+5)
帰納法の仮定から、
=k(2k+3)+1+4k+5
あれ、これ、えっと」
蒼井「だから、目標を先に見ようね。右辺にk+1を代入すると？」
山城「(k+1)(2(k+1)+3)+1です」
蒼井「左辺も右辺も展開しようか」
山城「はい。
(左辺)
=k(2k+3)+1+4k+5
=2k^2+7k+6
(右辺)
=(k+1)(2(k+1)+3)+1
=2k^2+7k+6
あー、一致しました。はい」
真白「しゅーりょー」
『すべての非負整数nに対して、
1+5+9+…+(4n+1)=n(2n+3)+1
を証明せよ
proof)
数学的帰納法によって示す。
1) n=0の場合
(左辺)=1=(右辺)より成立。
2) n=kで成立するとして、n=k+1の場合 (k≧0)
(左辺)
=1+5+…+(4k+1)+(4k+5)
帰納法の仮定から、
=k(2k+3)+1+4k+5
=2k^2+7k+6
また、一方で、
(右辺)
=(k+1)(2(k+1)+3)+1
=2k^2+7k+6
よって、(左辺)=(右辺)
(1),(2)より、すべての非負整数nに対して主張は成り立つ//』
真白「よし、それじゃ、帰納法の会はこれにて終了ってことで」
蒼井「はい。お疲れ様です」
山城「ありがとうございました」
紅林「ありがとうございました」
蒼井「以上、『1から始める帰納法』でした」
