第179回　数学的帰納法の第一歩（前編）

$ \newcommand{\LRARROW}{\Leftrightarrow} \newcommand{\SETL}{\bigl\{} \newcommand{\SETM}{\bigm|} \newcommand{\SETR}{\bigr\}} \newcommand{\LAND}{\mathrel{\land}} \newcommand{\LOR}{\mathrel{\lor}} \newcommand{\LNOT}{\lnot} \newcommand{\BITAND}{\mathrel{\&}} \newcommand{\BITOR}{\mathrel{|}} \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\RELATED}{\dashleftarrow\dashrightarrow} \newcommand{\REAL}{{\mathbb R}} \newcommand{\MINILOGL}{\bigl[\,} \newcommand{\MINILOGR}{\,\bigr]} \newcommand{\LOGL}{\Bigl[\,} \newcommand{\LOGR}{\,\Bigr]} \newcommand{\LOGDOTL}{\Bigl.} \newcommand{\LOGDOTR}{\Bigr.} \newcommand{\BIGLOGL}{\bigg[\,} \newcommand{\BIGLOGR}{\,\bigg]} \newcommand{\BIGBIGLOGL}{\Bigg[\,} \newcommand{\BIGBIGLOGR}{\,\Bigg]} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} \newcommand{\NEQ}{\neq} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\IMPLIES}{\Rightarrow} \newcommand{\NATURAL}{{\mathbb N}} \newcommand{\ABS}[1]{\bigl|#1\bigr|} $

僕の部屋

ユーリ「ねー、お兄ちゃん。ユーリ、たいくつだよ？」

僕「はい？」

ユーリ「聞こえなかった？　ユーリは、たいくつなの！」

僕「聞こえたよ」

ユーリ「……」

僕「……」

ユーリ「お兄ちゃん、いま何してるの？」

僕「本棚の整理」

ユーリ「それ、いましなきゃいけないこと？」

僕「そういうわけでもないけど」

ユーリ「あのね、ユーリ、たいくつなんだ」

僕「それ、さっき聞いたよ。……もしかして、ユーリのたいくつを解消することが求められているんだろうか」

ユーリ「気付くの遅いね」

僕「はあ……」

ユーリ「なんか、おもしろいクイズないの？」

僕「はいはい、それじゃね……」

ユーリ「『そのときは、あんな結末になるとは、二人とも想像すらできなかったのだ』」

僕「地の文をセリフで続けなくていいから」

ユーリ「そーゆーの、こないだ西尾維新に出てきたよ」

フィボナッチ数列

僕「おもしろい話といってもなあ……じゃあ、とりあえずフィボナッチ数列を書いてみようか」

ユーリ「ふぃぼなっちすうれつ」

僕「フィボナッチ数列は知ってるよね？」

ユーリ「知ってる。二つ足したのが次にくるの」

僕「すごい省略表現だな」

ユーリ「でも、あってるでしょ？」

僕「まあね。最初に$1,1$という二つの数があって、$$ 1, 1 $$ その二つを足した数が次に来る。つまり$1+1 = 2$だね。 $$ \underbrace{1, 1}_{1+1=2}, \underline{2} $$ そして、最後の二つを足した数がさらに次に来る。つまり$1+2 = 3$と。 $$ 1, \underbrace{1, 2}_{1+2=3}, \underline{3} $$ それを繰り返す。最後の二つを足した数が次に来る。$2 + 3 = 5$だね。 $$ 1, 1, \underbrace{2,3}_{2+3=5}, \underline{5}, \ldots $$ それをずっと繰り返してできる数列が、フィボナッチ数列」

ユーリ「フィボナッチ数列はユーリよく知ってるよ。お兄ちゃんよく話してくれるじゃん（『数学ガールの秘密ノート／数列の広場』、 『数学ガール』参照）」

僕「そうだね。フィボナッチ数列そのままじゃなくて、少しいじってみようか。 たとえば……こういうのはどう？　フィボナッチ数列をどんどん足していくんだ」

ユーリ「ほほー？　フィボナッチ数列を最初からずっと足していくってこと？$1+1+2+3+5+8+13+21+34+\cdots$みたいに」

僕「そういうことだね。そうやって足していったらどうなるか」

ユーリ「すごく大きくなる！　だってフィボナッチ数列は最後の二つを足して作ってる。それをさらに足したら、すっごく大きくなるよね！」

僕「ああ、そうだね。すごく大きくなるのは確かなんだけど、足し合わせて作ったものも、また数列になるよね？　その数列はどんな数列か、 というのが言いたかったこと」

ユーリ「どんな数列になるか……わかんない」

僕「いやいや、ちゃんと考えようよ」

ユーリ「$1,2,4,7$だけじゃ予想できないもん！」

僕「だったら、もっと計算してみないとね」

ユーリ「そっか」

僕「どう？ 今度は予想できそう？」

ユーリ「えーっと、結局、$$ 1, 2, 4, 7, 12, 20, 33, 54, \ldots $$ って数列を当てろって問題だね？　むずかしーなー」

僕「そうなんだ。お兄ちゃんはわかったよ、ユーリ」

ユーリ「うっそ、マジ？」

僕「見比べるとわかるよ」

ユーリ「見比べる……あっ！　わかった。これってフィボナッチ数列引く$1$じゃん！」

僕「おもしろいよね。足し合わせたらすごく大きくなるように思えるんだけど、 実はフィボナッチ数列でふたつ先の項から$1$引いたくらいの大きさにしかなってないんだね。 まあ、それだけフィボナッチ数列自体が急激に増えているってことだけど……どした？」

ユーリ「考えてるのにヒント出さないでよ！」

僕「ヒント？」

ユーリ「さっき、『見比べるとわかる』なんてヒント勝手に出したじゃん！　あのヒントで、フィボナッチ数列と比較しちゃったじゃん！　ユーリひとりで考えてたのに！」

僕「ごめんごめん。でも、まだ考えることはいっぱいあるから」

ユーリ「？」

僕「フィボナッチ数列の《最初の$n$項の和》は《第$n+2$項引く$1$》に等しい……って《答え》を出したけど、でも、 $1, 2, 4, 7, 12, 20, 33, 54$という、はじめの$8$個で具体的に確かめただけ。 まだ証明はしてないよね？」

ユーリ「しょーめー」

僕「もしかしたら、いまの解答1はまちがっているかもしれない。偶然そうなったのかもしれない」

ユーリ「いやー、それはナイよー。好きなだけ確かめられるし」

僕「フィボナッチ数列は無限に続くわけだから、好きなだけ確かめても、すべてを試し尽くすことはできないよね？」

ユーリ「そりゃそーだね……だから、証明？」

僕「だから、証明。僕たちは、フィボナッチ数列を眺めて、《どんな正の整数$n$に対しても、フィボナッチ数列の最初の$n$項の和は、第$n+2$項引く$1$に等しい》 という予想を立てた。そして、$n = 1,2,3,4,5,6,7,8$については具体的に確かめた。 でも、証明はしていない。証明しなければ、予想は予想にすぎない。証明されてはじめて、予想は定理になる」

ユーリ「《証明されてはじめて、予想は定理になる》。くうううっ、お兄ちゃん、これですよ、これ。かっこいー！　……でも、どーすれば証明になるの？」

僕「いっしょに考えていこうね」

ユーリ「うん！」

数式

僕「まず最初に、考えをきっちり進めるために数式で表すことにしよう」

ユーリ「でたな、数式マニア」

僕「フィボナッチ数列の第$n$項を$F_n$で表すことにすると、フィボナッチ数列はこんなふうに作るわけだよね？」

ユーリ「これって、$F_1,F_2,F_3,\ldots$がフィボナッチ数列ってことだよね？」

僕「そうだね。そして、この作り方をあらためて漸化式（ぜんかしき）で表すことがよくある」

ユーリ「ぜんかしき」

僕「どうして、こういう漸化式で表すか、わかる？」

ユーリ「わかんにゃい」

僕「無限を一気に扱えるからだよ」

ユーリ「なにいってるですか？」

僕「あのね、$F_{n+2} = F_{n} + F_{n+1}$という式に$n$という文字がでてきてるよね」

ユーリ「そだね」

僕「ここで、$n$という一文字は、$1,2,3,\ldots$という正の整数のどれでもいい。 どんな正の整数についても、 $F_{n+2} = F_{n} + F_{n+1}$ だよ、といってる。この一行で、$F_3,F_4,F_5,\ldots$という無数の項を定義していることになるんだね」

ユーリ「ま、そーだね。$n = 1,2,3,\ldots$だもん」

僕「そういうこと。だから、$F_{n+2} = F_{n} + F_{n+1}$ というこの式を使って何かを主張できたら、 いっぺんに無数の主張を行ったことになるんだよ。それが文字の力。それが数式の力。無限を一気に扱える」

ユーリ「ほほー……。思わず目がハートになっちゃうぜ」

僕「ちゃかすなよ。これで、フィボナッチ数列$F_n$は漸化式で書けた。こんどは《フィボナッチ数列の最初の$n$項の和》を表す数列を作ってみよう。 たとえば、その数列を$S_n$としてみる」

ユーリ「にゃるほど。$S_n$ってゆーのは、$F_1$から$F_n$までを足したものってこと」

僕「そうだね。いちおう表にしてみようか。正の整数$n$と、フィボナッチ数列$F_n$と、フィボナッチ数列の最初の$n$項の和$S_n$を並べてみよう」

ユーリ「ふんふん」

僕「ここまで準備してくると、問題1で考えていた僕たちの予想は、数式で正確に書くことができる」

ユーリ「おー、確かに！」

僕「$S_n$はフィボナッチ数列の最初の$n$項の和で、$2$個先の項引く$1$が$F_{n+2} - 1$ってことだね」

ユーリ「確かに、確かに！　……んでも、待ってよお兄ちゃん。でも、これはまだ証明じゃないじゃん。数式に置き換えただけだもん」

僕「ユーリの言う通りだよ。これはまた準備段階。証明はこれから」

ユーリ「だよね……で？」

僕「証明は、いまから考える」

ユーリ「え」