第180回 数学的帰納法の第一歩(後編)

「じゃ、最初に発見しなくちゃダメじゃん!」とユーリは叫ぶ。 「論理と証明」第5章前編。
【お休みの予告】
結城浩です。いつもご愛読ありがとうございます。 おかげさまでこのWeb連載も今回で第180回を迎えることになりました! みなさまの応援に感謝します。

さて、たいへん恐れ入りますが、さらなるパワーアップをはかるため、 このWeb連載の更新を2017年1月13日までお休みさせてください。

日程は以下の通りです。ご迷惑をおかけしますが、よろしくお願いいたします。

Web連載「数学ガールの秘密ノート」予定

・2016年12月 9日(金)第180回更新
・2016年12月16日(金)お休み
・2016年12月23日(金)お休み
・2016年12月30日(金)お休み
・2017年 1月 6日(金)お休み
・2017年 1月13日(金)第181回更新
・(以後、毎週金曜日更新)
登場人物紹介
:数学が好きな高校生。
ユーリのいとこの中学生。 のことを《お兄ちゃん》と呼ぶ。 論理的な話は好きだが飽きっぽい。
$ \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|} $

僕の部屋

ユーリは数学的帰納法についておしゃべりをしている。(第179回の続き)

ユーリ「あのね。無数のドミノは倒せない、って思ったの。だって、一個ずつしか倒せないもん。 数学的帰納法の話って、お兄ちゃんの《テンテンテン》でごまかされた感じがする。それが、すんごくイヤ」

「なるほど、なるほど」

ユーリ「ドミノは無数にあるから、倒し尽くすことはないでしょ? だったら、証明したいことも無数にあるんだから、証明し尽くすことはないってことにならない?」

「ユーリ! ユーリは、ほんとに賢いなあ! まったく同じこと、考えたよ」

ユーリ「え? お兄ちゃんが?」

「うん。そして、自分なりに納得したポイントがあるんだ」

ユーリ「そーなんだ」

「まず、数学的帰納法はこういう2ステップの証明方法だったよね?」

数学的帰納法
すべての正の整数$n$に関して《$n$についての主張》が成り立つことを証明する手順は次の通り。

(ステップA)
  《$1$についての主張》が成り立つことを証明する。

(ステップB)
  《$k$についての主張》が成り立つならば《$k+1$についての主張》も成り立つことを証明する。

ユーリ「前回読んでないヒト向けの配慮はいーから、先に進んでよ」

「メタ発言自重。それで、ユーリがいう《テンテンテン》はこれのことだろ? 説明するときに書いた、これ」

(ステップA)で証明される主張
 《$1$についての主張》は成り立つ。


(ステップB)で証明される無数の主張
 《$1$についての主張》が成り立つならば《$2$についての主張》も成り立つ。
 《$2$についての主張》が成り立つならば《$3$についての主張》も成り立つ。
 《$3$についての主張》が成り立つならば《$4$についての主張》も成り立つ。
  ・
  ・
  ・
 《$9999999$についての主張》が成り立つならば《$10000000$についての主張》も成り立つ。
  ・
  ・
  ・

ユーリ「これこれ! 最後の『・・・』があやしいの。どこまでいっても終わらないじゃん? これで、証明したことになるの?」

「自分が納得したときにはこんなふうに考えたんだよ。『このまま、$1$個ずつ追いかけていったら、いつまで経っても終わらないな』って。 そこで、考え方を変えてみた。『《$n$についての主張》が証明されないような、そんな正の整数$n$ってあるのかな?』ってね」

ユーリ「証明されないもの……」

「どこまでいっても証明が終わらない。いつまで経っても証明が終わらない。そんな感覚に襲われてしまう。だったら、《$n$についての主張》で証明されないものはあるだろうかと考えてみたんだ」

ユーリ「たとえば《$123$についての主張》とか、そゆこと?」

「そういうこと。たとえば、ね。いまユーリが言ったのは$n$が$123$の場合を考えたわけだ」

ユーリ「そんでそんで?」

「具体的に$n = 123$と与えられたら、それは確実に証明できることがわかるよね。

 《$1$についての主張》は成り立つ。
 《$1$についての主張》が成り立つならば《$2$についての主張》も成り立つ。
 《$2$についての主張》が成り立つならば《$3$についての主張》も成り立つ。
 《$3$についての主張》が成り立つならば《$4$についての主張》も成り立つ。
  ・
  ・
  ・
 《$120$についての主張》が成り立つならば《$121$についての主張》も成り立つ。
 《$121$についての主張》が成り立つならば《$122$についての主張》も成り立つ。
 《$122$についての主張》が成り立つならば《$123$についての主張》も成り立つ。

ユーリ「にゃるほど……これは証明できてる」

「いまは$123$で考えたけれど、$1234$でも、$100000$でも何でも同じだよね。だから、自分はこんなふうに納得したんだ。 『数学的帰納法を使って《$n$についての主張》を証明したならば、 どんな正の整数$n$を持ってきても、確かにそれは証明されている』ってね」

ユーリ「うう……確かに証明できない$n$は持ってこれない……くぅ、くやしいが納得じゃ」

「ところで、ユーリは途中に出てきた《テンテンテン》は気にならないの?」

ユーリ「だって、それは無限じゃないもん。ユーリが気にしてたのは、最後についてる《テンテンテン》だけ。無限に続くやつ」

「その違いがわかるんだ。すごいな。その違いはとっても大事なんだよ。数式でもよく出てくるよ。こんなの」

$$ \begin{align*} & F_1 + F_2 + \cdots + F_n && \text{有限個の項を表している} \\ & F_1 + F_2 + \cdots && \text{無数の項を表している} \\ \end{align*} $$

ユーリ「この違いはわかるよん。$F_1 + F_2 + \cdots + F_n$は$n$個足してるから有限個でしょ。$F_1 + F_2 + \cdots$は無限個足してる」

「そうだね。『無限個の項』という言い方をすることはあまりなくて、たいていは『無数の項』というかな」

ユーリ「へー」

「数学的帰納法の《説明》をするときには《テンテンテン》を使うけど、数学的帰納法そのものには《テンテンテン》は出てこないよ」

ユーリ「えっ、そーだっけ?」

「よく読んでなかったユーリに配慮して、もう一度書いてみようか」

数学的帰納法
すべての正の整数$n$に関して《$n$についての主張》が成り立つことを証明する手順は次の通り。

(ステップA)
  《$1$についての主張》が成り立つことを証明する。

(ステップB)
  《$k$についての主張》が成り立つならば《$k+1$についての主張》も成り立つことを証明する。

ユーリ「ほんとだ! 《テンテンテン》は出てきてない!」

数学的帰納法を使う

「数学的帰納法のいいところは、考えを進めるパターンがあるところ。《$n$についての主張》を証明したかったら、2ステップに当てはめて考えていけばいいからね。 そのときにはドミノのことを思い出すのも悪くない。最初のドミノを倒す(ステップA)と、 途中の$k$番目が倒れたならば、$k+1$番目が倒れることを示す(ステップB)と」

ユーリ「ちょっと待ってお兄ちゃん。それってすごくない? だって《$n$についての主張》の形だったら、何でもサクサク証明できるってことでしょ? パターンに当てはめて」

「いや……残念ながら、そううまくは行かないんだ。何でもサクサクとはいかない」

ユーリ「なんで? いま、当てはめればいーって言ったじゃん」

「たいていは(ステップA)はすぐにできる。具体的だから、まあ機械的にできる。でも、(ステップB)を証明するのは機械的にはいかない。簡単な問題は簡単にいくけど、難しい問題は難しい」

ユーリ「なーんだ」

「それでも、さっき言ったように、考えを進める道筋があるのは助かるんだよ」

ユーリ「たとえば?」

「え?」

ユーリ「たとえば、どんなふうに? 『ほらユーリ、数学的帰納法を使えばこんなふうに問題が解けるんだよ』……って例がないとわかんないよ。《例示は理解の試金石》だもん」

「はいはい……何か問題を考えろってことだね。たとえば、フィボナッチ数列の第$n$項までの和$F_1 + F_2 + \cdots + F_n$は……」

ユーリ「それ、さっきやったばっかり(第179回参照)」

フィボナッチ数列$F_n$と、その第$n$項までの和$S_n = F_1 + F_2 + \cdots + F_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} $$ ここで、 $$ S_n = F_{n+2} - 1 \qquad (n = 1,2,3,\ldots) $$ が成り立つ。

「それじゃ、たとえば平方和を考えてみようか。つまり$F_1^2 + F_2^2 + \cdots + F_n^2$ということ」

ユーリ「ほほー?」

問題4(フィボナッチ数列の平方和)
フィボナッチ数列の一般項を$F_n$で表す。 また、 $$ T_n = F_1^2 + F_2^2 + \cdots + F_n^2 $$ とする。$T_n$は、どんな数列になるか。

ユーリ「……」

「さて」

ユーリ「これ、どーやって数学的帰納法使うの?」

「いやいや。数学的帰納法は《$n$についての主張》を証明する方法なんだから、まず何を証明すべきかを見つけなくちゃいけない」

ユーリ「だって、$T_n$について証明すんでしょ?」

「そうなんだけど《$T_n$とはこういう数列である》という形の主張にしなければ、証明できないよ。何を証明するか決まらないのに、証明はできないよね」

ユーリ「んー、そりゃそーか……ちょっと待って。だったら、$T_n$がどんな数列か、予想しなきゃダメってこと?」

「そういうことになるね」

ユーリ「なんか話、ちがーう! 数学的帰納法だとすべてオーケー、じゃないの?」

「そんなこと言ってないよ。$T_n$という数列について予想を立てたら、それを数学的帰納法で証明できるかも、ということ」

ユーリ「そんなにうまいこと予想なんて、できないよー」

「だから、予想を立てる前に必ずやるべきことがある」

ユーリ「なになに?」

「小さい$n$について、具体的に$T_n$の値を求めること。具体的に計算できるんだから。具体的に値を求めると、予想しやすくなるんだ」

ユーリ「うわめんどい」

「いっしょに計算していこう」

ユーリ「へーい」

「まずは、$F_n^2$の表を作ろうか」

$F_n^2$を求めて表に書く
$$ \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 F_n^2 & 1 & 1 & 4 & 9 & 25 & 64 & 169 & \cdots \\ \hline \end{array} $$
この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

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

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

人気の連載

おすすめ記事

ケイクス

この連載について

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

結城浩

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

この連載の人気記事

関連記事

関連キーワード

コメント

enfcuvwi 論理と命題、証明は数学の根幹をなす重要分野なのに、中高では軽く触れる程度しか学ばない この分野を学べば数学的思考が苦手な人は減ると思うけどね 約3年前 replyretweetfavorite

chibio6 フィボナッチ数列からは数学的帰納法の問題がたくさん作れそう。 約3年前 replyretweetfavorite

brv00 メタ発言のとこリサが終始無言で、いないんじゃないかって錯覚させる演出がおもしろかったです(ぇ 約3年前 replyretweetfavorite

aramisakihime 《kについての主張》だけでなく《k+1についての主張》も書いてあると、証明がわかりやすくなりますね。 約3年前 replyretweetfavorite