第179回 数学的帰納法の第一歩(前編)

「だから、この式を使って何かが主張できたら、無数の主張を行ったことになるんだよ」と「僕」はいう。 「論理と証明」第5章前編。
登場人物紹介
:数学が好きな高校生。
ユーリのいとこの中学生。 のことを《お兄ちゃん》と呼ぶ。 論理的な話は好きだが飽きっぽい。
$ \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, \ldots $$

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

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

フィボナッチ数列を足していく
$$ 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots $$
$$ \begin{array}{rcl} 1 &=& 1 \\ 1 + 1 &=& 2 \\ 1 + 1 + 2 &=& 4 \\ 1 + 1 + 2 + 3 &=& 7 \\ &\vdots& \\ \end{array} $$

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

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

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

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

問題1(フィボナッチ数列の和)
フィボナッチ数列の最初の$n$項を加えて得られる数列は、どんな数列になるか。
$$ \begin{array}{rcl} 1 &=& 1 \\ 1 + 1 &=& 2 \\ 1 + 1 + 2 &=& 4 \\ 1 + 1 + 2 + 3 &=& 7 \\ & \vdots & \\ \end{array} $$
$$ 1, 2, 4, 7, \ldots $$

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

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

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

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

ユーリ「そっか」

どんな数列が出てくるか、計算を続けてみよう
$$ \begin{array}{rcl} 1 &=& 1 \\ 1 + 1 &=& 2 \\ 1 + 1 + 2 &=& 4 \\ 1 + 1 + 2 + 3 &=& 7 \\ 1 + 1 + 2 + 3 + 5 &=& 12 \\ 1 + 1 + 2 + 3 + 5 + 8 &=& 20 \\ 1 + 1 + 2 + 3 + 5 + 8 + 13 &=& 33 \\ 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 &=& 54 \\ & \vdots & \\ \end{array} $$

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

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

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

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

「見比べるとわかるよ」

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

解答1(フィボナッチ数列の和)
フィボナッチ数列の最初の$n$項を加えて得られる数列は、
フィボナッチ数列の第$n+2$項から$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$で表すことにすると、フィボナッチ数列はこんなふうに作るわけだよね?」

フィボナッチ数列の作り方
$$ \begin{array}{rcl} F_1 &=& 1 \qquad \text{(第$1$項は$1$)}\\ F_2 &=& 1 \qquad \text{(第$2$項も$1$)}\\ F_3 &=& F_1 + F_2 = 1 + 1 = 2 \qquad \text{(第$3$項は第$1$項と第$2$項を足して$2$)}\\ F_4 &=& F_2 + F_3 = 1 + 2 = 3 \qquad \text{(第$4$項は第$2$項と第$3$項を足して$3$)}\\ F_5 &=& F_3 + F_4 = 2 + 3 = 5 \qquad \text{(第$5$項は第$3$項と第$4$項を足して$5$)}\\ &\vdots& \\ \end{array} $$

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

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

フィボナッチ数列$F_n$を漸化式で定義する
$$ \left\{\begin{array}{llll} F_1 &= 1 \qquad \text{(第$1$項は$1$)}\\ F_2 &= 1 \qquad \text{(第$2$項も$1$)}\\ F_{n+2} & = F_{n} + F_{n+1} \qquad \text{第$n+2$項は、第$n$項と第$n+1$項$\HIRANO$和} \\ \end{array}\right. $$ ただし、$n=1,2,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$としてみる」

フィボナッチ数列の最初の$n$項の和を表す数列$S_n$を定義する
$$ S_n = F_1 + F_2 + \cdots + F_n \qquad (n = 1,2,3,\ldots) $$

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

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

数列を具体的に書いてみる
$$ \begin{array}{|c|cccccccc|} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \cdots \\ \hline F_n & 1 & 1 & 2 & 3 & 5 & 8 & 13 & \cdots \\ \hline S_n & 1 & 2 & 4 & 7 & 12 & 20 & 33 & \cdots \\ \hline \end{array} $$

ユーリ「ふんふん」

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

僕たちの予想
$$ S_n = F_{n+2} - 1 \qquad (n = 1,2,3,\ldots) $$

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

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

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

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

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

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

ユーリ「え」

問題2
フィボナッチ数列の第$n$項を$F_n$とし、 $F_1$から$F_n$までの和を$S_n$とするとき、 $$ S_n = F_{n+2} - 1 \qquad (n = 1,2,3,\ldots) $$ を証明せよ。

この続きは有料会員登録をすると
読むことができます。
cakes・note会員の方はここからログイン

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

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

人気の連載

おすすめ記事

ケイクス

この連載について

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

結城浩

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

この連載の人気記事

関連記事

関連キーワード

コメント

urush1hara https://t.co/ATzr1fjOzb 帰納法使わないで母関数いじくり回して解けた、、、、お休み( ̄q ̄)zzz 1年以上前 replyretweetfavorite

chojo40 帰納法に対する納得感が得られないという気持ちもわかる気がします。次回にどうユーリは納得するのか楽しみです。 2年弱前 replyretweetfavorite

aramisakihime 数学的帰納法の表し方が、ユーリ向けにやさしくなってますね。(手元にゲーデル巻も『整数で遊ぼう』もなくて確かめてませんが) 2年弱前 replyretweetfavorite

chibio6 ユーリが数学的帰納法で一般項を示しただけでは満足せず、無限に足すとどうなるのかを気にしだした。どうなるのだろうか。 2年弱前 replyretweetfavorite