僕：数学が好きな高校生。
テトラちゃん：僕の後輩。好奇心旺盛で根気強い《元気少女》。
マイナスワン
僕は後輩のテトラちゃんとおしゃべりをしている。
僕「……という話をユーリとしていたんだよ」
テトラ「なるほどです。小数が無限に続くかどうかは《何進法で表しているか》という《数の表記法》の問題なんですね。 そんなふうに考えたことはありませんでした（第214回参照）」
僕「うん。《数字が無限に続くからキリが悪い》という感覚は、 《数の値》の問題じゃなく《数の表記法》の問題といえるんだね……あ、そうだ。 表記法といえば最近おもしろい本が出版されたよね。 素数を印刷した本」
テトラ「素数を印刷した本……ああ、$2,3,5,7,\ldots$のような素数表でしょうか」
僕「いや、そうじゃなくて、本一冊が《たった一つの素数》を書き表している本という意味」
テトラ「すみません。意味がわからないんですが」
僕「『2017年最大の素数』という本。2017年の時点で人類が知っている最大の素数ひとつを、まるごと紙の本に印刷してしまったんだ。 50番目のメルセンヌ素数で、二千三百二十四万九千四百二十五桁あるそうだよ」
テトラ「え？ $23,249,425$けた？！」
僕「そうそう。すごいよね。数百ページの本だって」
テトラ「数字がびっしり書かれている本ということですね」
僕「そうなるね……うん、それで、これはメルセンヌ素数だから、$$ 2^{N} - 1 $$ という形になっているんだ。ここで$N = 77232917$という数」
テトラ「メルセンヌ素数というのは$2^{N} - 1$の形をした素数ということですね」
僕「そうだね。だから、十進法の位取り記数法で表記すると数百ページの本を埋め尽くす数字列が、とても短く、$$ 2^{77232917} - 1 $$ と表記できるともいえる」
テトラ「なるほど！ それは、おもしろいといいますか、不思議といいますか……最後にマイナス$1$が付くのもアクセントっぽいですね」
僕「アクセントというか、もしも$2^{77232917}$だったら、偶数だから素数にはならないよ」
テトラ「あちゃっ！ それはそうですね……」
僕「$2^{77232917} - 1$は二進法で表すと楽しいよ。だって、すべての桁が$1$になるから」
テトラ「ええと……そうなりますかね」
僕「あれ？ そうだよ。$N$が正の整数なら、$2^N - 1$の形をした数は何でも、二進法で表したらすべての桁が$1$になる。 メルセンヌ素数に限らずね。 小さい数で確かめてみようか？」
$$ \begin{align*} 2^1 - 1 &= 1 &&= \BINREP{1} \\ 2^2 - 1 &= 3 &&= \BINREP{11} \\ 2^3 - 1 &= 7 &&= \BINREP{111} \\ 2^4 - 1 &= 15 &&= \BINREP{1111} \\ 2^5 - 1 &= 31 &&= \BINREP{11111} \\ &\vdots && \vdots \\ \end{align*} $$
テトラ「ははあ……確かにそうですね。あれれ、もしかして、これって当たり前ですか？ だって、二進法の各桁は$2^N$ですから……」
僕「まあ、当たり前といえばそうだね。二進法の各桁は$2$の冪乗になる。下の位から、$2^0$の位、$2^1$の位、$2^2$の位……とね。 だから、$2^N$という数を二進法で表記すると、 $2^N$の位が$1$になって、そこから下はぜんぶ$0$になる。 何個の$0$が並ぶと思う？」
テトラ「$0$が、ええと……はい、$N$個ならぶと思います」
僕「どうして、そう思ったの？」
テトラ「小さな数で試してみました。たとえば、$2^3 = 8$という数だと、二進法で$\BINREP{1000}$で、$0$が$3$個になりますから……」
僕「そうだね」
$$ 2^N = \BINREP{1000\cdots0} \qquad \text{$1$ $\HIRANO$ あとに$N$個$\HIRANO$ $0$} $$テトラ「ははあ、ということは、確かに$2^N - 1$は二進法で表記すると$1$が$N$個ならびますね。 だって、そこに$1$を足したら、どどどどっと繰り上がりしなくちゃいけませんから」
僕「そうだね。だから、$2^N - 1$は二進法で表記すると$1$が$N$個並ぶことになる」
$$ 2^N - 1 = \BINREP{111\cdots1} \qquad \text{$N$個$\HIRANO$ $1$} $$テトラ「はいはい、わかります」
僕「$N = 4$で確認してみると、$$ 2^4 - 1 = \BINREP{1111} \qquad \text{$4$個$\HIRANO$ $1$} $$ うん、確かにあってる。 ということは、2017年最大の素数というのは……」
テトラ「こうですねっ！」
$$ 2^{77232917} - 1 = \BINREP{111\cdots1} \qquad \text{$77232917$個$\HIRANO$ $1$} $$僕「だから、もしも『2017年最大の素数』を二進数で表したものを本にしたいなら、七千七百二十三万二千九百十七個の$1$を並べればいいということになるね」
テトラ「……くっ、くくっ……」
僕「どうしたの！ お腹いたいの？」
テトラ「い、いえ……ちょっと笑いのツボに入ってしまいました……そんなに、たくさんの$1$が並んだ本……」
プラスワン
テトラ「し、失礼しました。それにしても、ちょっと意外でした」
僕「二進法で$1$が並ぶのがそんなに意外かなあ」
テトラ「いえいえ、そうではなくてですね。ユーリちゃんとのお話で出てきた《大きい数の勝負》のことです（第211回参照）」
僕「ああ……」
テトラ「先輩が『どちらの方が大きい数をいえるか競争』なんて子供っぽいことやってたなんて」
僕「まあ、小学生のころの話だし。テトラちゃんはそういうのはなかったの？」
テトラ「え？ あたしですか？ なかったです……なかったと思います。そういう、なんていいますか、 ストレートな言い争いはなかったです」
僕「そうなんだ」
テトラ「あ、でも、先輩がおっしゃっていた《足す$1$》で《無限》 を感じるというのはわかるような気がします。 以前、ペアノの公理のときもその話題が出てきました （『数学ガール／ゲーデルの不完全性定理』参照）」
僕「うんうん、そうだね。僕もそのことを考えていたよ。数学的帰納法の話にもつながっていく」
テトラ「数学的帰納法！ それはドミノ倒しですね」
僕「そうだね。二つのステップで……」
テトラ「お待ちください、先輩。テトラにいわせてください。以前、先輩からきちんと数学的帰納法は教わりました（『数学ガールの秘密ノート／整数で遊ぼう』参照）。 ですから、あたしはそれを説明できるはずですっ！」
僕「おお！ テトラちゃんが覚醒モードに！」
僕は茶化し気味に煽ったことをやや反省しつつ、 彼女が数学的帰納法について書くのを待つ。
テトラ「……ここまで、思い出せましたけど」
《ステップA》
「$n = 1$のときに成り立つ」ことを証明する。
《ステップB》
どんな正の整数$k$についても、
「$n = k$のときに成り立つ」と仮定すると、
「$n = k+1$のときも成り立つ」
ことを証明する。
僕「うん。これはこれで正しいけど？」
テトラ「ええと、いくつか引っかかっていることがあります。順番にお話ししますね。 あたしは、数学的帰納法が二つのステップでできているというのを覚えていました。 たとえばその二つに《ステップA》と《ステップB》のように名前を付けます」
僕「うんうん」
テトラ「《ステップA》は、何というか当たり前の話で、$n = 1$のときに成り立つことを証明するというステップです……でも、 あの、これは《何が成り立つことを証明する》と表現すればいいんでしょうか」
僕「ああ、なるほど。いまテトラちゃんは《ステップA》の話を始めたけど、ちょっとそこでストップしよう。そもそも数学的帰納法って、何？」
テトラ「数学的帰納法というのは……数学で、$1,2,3,\ldots$について何かを証明するときの……方法？」
僕「そうだね。もう少しきちんというと、いま、正の整数$n$についての数学的な主張があるとする。 主張といっても、命題といっても、条件といっても、述語といってもいいんだけど、 とにかく$n$が与えられると真か偽か定まるような主張があるとする」
テトラ「はい。わかります」
僕「たとえばその主張を$P(n)$と書くことにする。たとえば、だよ。そうすると、$P(123)$は真だとか、$P(7)$は偽だとか決まる」
テトラ「はいはい」
僕「$P(1)$が真で、$P(2)$も真で、$P(3)$も真で……と調べていったとしても、すべての正の整数$n$について$P(n)$が真であることは調べられない」
テトラ「正の整数は無限にあるから、ですね」
僕「そういうこと。もちろん、何か一つでも$P(n)$が偽になるような$n$が見つかれば、すべての正の整数$n$について$P(n)$が真であるとはいえないよ。そのような$n$が反例になるから」
テトラ「はい、わかります」
僕「でも、もしも、すべての正の整数について$P(n)$が真になるということを言いたかったら、ひとつひとつ具体的に確かめるんじゃなくて、証明しなくちゃならない。正の整数は無限にあるから」
テトラ「なるほど。そこで使うのが数学的帰納法！」
僕「だね。だから、数学的帰納法は何かといわれたら、すべての正の整数$n$に対して、 数学的主張$P(n)$が成り立つことを証明するための証明法である……となる」
テトラ「理解しました。あたしは先走りしてしまいましたね。二つのステップがあって……という前に、 数学的帰納法とは何かを言うべきでした」
僕「さて、それで……」
テトラ「はい。では再スタートします。数学的帰納法というのは、すべての正の整数$n$に対して、 数学的主張$P(n)$が成り立つことを証明するための証明法です。 証明するためには、二つのステップが必要です」
僕「うん」
テトラ「《ステップA》は、$P(1)$が成り立つことを証明するステップです。当たり前ですけれど、大事です。 これは、ドミノ倒しで《$1$番目のドミノを倒す》ようにするものです」
僕「……」
テトラ「《ステップB》は、急激にややこしくなるんですが……」
僕「そうだね」
テトラ「《ステップB》は、どんな正の整数$k$に対しても、
$P(k)$が成り立てば、$P(k+1)$も成り立つ
ことを証明するステップです。 これは、ドミノ倒しで《$k$番目のドミノが倒れたら、$k+1$番目のドミノも倒れる》ようなものです」
僕「その通り、その通り。《どんな正の整数$k$に対しても》というところがとても大事だね。ずらっと並んだドミノのどこを見ても、ひとつ倒れたら次が倒れるという保証が大事」
テトラ「はい。これが数学的帰納法です」
僕「え？」
テトラ「え？」
僕「いやいや、最後にもう一度まとめてほしいなあ、テトラちゃん。その《ステップA》と《ステップB》が証明されたら、何が証明されることになるの？」
テトラ「あっ、そういうことですか。はい。《ステップA》と《ステップB》の二つを証明したら、 どんな正の整数$n$に対しても、$P(n)$が成り立つことが証明できたことになります。 ……これが、数学的帰納法です」
僕「そうそう。そこまで言い切ると、とても気持ちがいいね。《すべての正の整数について何かを証明せよ》という問題が出たら、数学的帰納法を使うというのはよくあること。 そのときには、テトラちゃんがいう二つのステップに分けて答えることになる。 つまりそれは、証明の方針が明確になるということだね。 くだけた言い方をすれば《何を書けば証明したことになるか》がはっきりしたともいえる」
テトラ「何を書けば証明したことになるか……なるほど」
僕「そうだね。証明問題が苦手な人の中には《何を書けば証明したことになるか》がピンと来ない人がいる。目の前にはいかにも成り立ちそうな正の整数に関する数学的主張がある。 適当な正の整数を代入しても確かに成り立ちそうだ。 でも、何を書けば証明したことになるんだろう？……と途方にくれちゃうんだね」
テトラ「あたし……そういう悩み方、しょっちゅうするかもです」
僕「数学的帰納法は証明法の一つだから、証明の方針をしっかり教えてくれる。テトラちゃんが言ったように、ドミノ倒しみたいだね。 でも全部のドミノを具体的に倒すんじゃなくて、二つのステップを使って倒しちゃうわけなんだ」
$P(n)$は、正の整数$n$についての数学的主張とする。
すべての正の整数$n$について$P(n)$が成り立つことを証明するには、 以下の《ステップA》と《ステップB》を証明すればよい。
《ステップA》 $P(1)$が成り立つ。
《ステップB》 どんな正の整数$k$についても、$P(k)$が成り立つならば$P(k+1)$が成り立つ。
「《ステップA》と《ステップB》を証明することで、 すべての正の整数$n$について$P(n)$が成り立つことが証明できる」 というこの証明法を、数学的帰納法という。
数学的帰納法を使う
テトラ「先輩！ 何か問題出していただけませんか？」
僕「えっ？」
テトラ「あたし、数学的帰納法という武器を使ってみたいです！ テトラはいま、《すべての正の整数$n$についての数学的主張》を切望してます！」
僕「すごいなあ……じゃあね、たとえばこういうのは？」
この連載について
数学ガールの秘密ノート
数学青春物語「数学ガール」の女子高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わってください。本シリーズはすでに何冊も書籍化されている人気連載です。 （毎週金曜日更新）
