数学的帰納法を使って

算数・数学教室のブログで、ガチガチの数学の記事を書くことにはためらいもありましたが、たまには書いてもよいでしょう。以下の記事は、高校までの数学をご存じのかたむけの記事になります。とても読む気になれないというかたは、どうぞほかの記事をお読みくださればと思います（当教室のブログで、こういう記事のほうがずっと稀です）。また、文系のかたでも習ったことのおありになる内容だと思います。数学的帰納法を使って、二項定理の証明と、フィボナッチ数列の一般項がどうしてそうなるのかの証明をしたいと思います。

数学的帰納法は、大学院の専門の数学でもひんぱんに使いました。背理法と帰納法は極めてひんぱんに用いる証明の方法でした。ここで、読者の皆様は、帰納法をご存じであると仮定しまして、それを用いて、まず、二項定理の証明をしたいと思います。

私には中高の数学の教員の経験がございます。二項定理も数学的帰納法も何度も授業でお教えしました。しかし、二項定理を帰納法で証明したことはございません。それはなぜかと考えますと、おそらく理由は単純で、二項定理のほうを先に習うため、二項定理を帰納法で証明することがないのだろうと思います。しかし、おそらく二項定理を帰納法で証明するのは自然だと思います。中高の教師であったころ、なぜ私は「二項定理を数学的帰納法で証明せよ」というテスト問題を出さなかったのか、不思議なほど、自然な発想です。ありきたりなのかもしれませんし、あるいは私が知らないうちに、どこかの大学入試で出ていそうな気もするのですが、以下に、二項定理を数学的帰納法で証明いたしますね。

二項定理も、ご存じであることを前提とさせていただきます。と申しますか、これから証明するのですから、ご存じなくてもいい、というのが正確なところでしょう。${n}$個のものから${k}$個とってくる場合の数を、${­_n C_k}$と書くことにいたしますと、${(a+b)^n=_nC_0 a^n+_nC_1 a^{n-1}b+_nC_2 a^{n-2}b^2+\cdot\cdot\cdot+_nC_n b^n}$と展開できることです。有名な例として、${(a+b)^2=a^2+2ab+b^2}$などがあります。${x^2}$を微分すると${2x}$になることも、ここから来ています。それでは証明いたしますね。

${n=1}$のときに成り立つのは明らかです。${n=k}$のときに成り立つと仮定して、${n=k+1}$のときに成り立つことを示しましょう。

仮定から、${(a+b)^k=_kC_0 a^k+_kC_1 a^{k-1}b+_kC_2 a^{k-2}b^2+\cdot\cdot\cdot+_kC_k b^k}$ですが、この両辺に、${(a+b)}$をかけてみましょう。${(a+b)^k(a+b)=(_kC_0 a^k+_kC_1 a^{k-1}b+\cdot\cdot\cdot+_kC_k b^k)(a+b)}$となり、右辺に分配法則を使いますと、${(a+b)^{k+1}}$ ${=a^{k+1}+_kC_1a^kb+_kC_2a^{k-1}b^2+\cdot\cdot\cdot+_kC_{k-1}a^2b^{k-1}+_kC_kab^k+_kC_0a^kb+_kC_1a^{k-1}b^2+\cdot\cdot\cdot+_kC_{k-1}ab^k+b^{k+1}}$となりまして、右辺をまとめますと、次のようになります。すなわち、${a^{k+1}+(_kC_0+_kC_1)a^kb+(_kC_1+_kC_2)a^{k-1}b^2+\cdot\cdot\cdot+(_kC_{k-1}+_kC_k)ab^k+b^{k+1}}$となります。ここで、${_kC_i+_kC_{i+1}=_{k+1}C_{i+1}}$であることを使いますと（※これはあとでご説明いたします。ここはこの証明のキモですので）、右辺は${a^{k+1}+_{k+1}C_1a^kb+_{k+1}C_2a^{k-1}b^2+\cdot\cdot\cdot+_{k+1}C_kab^k+b^{k+1}}$ ${=_{k+1}C_0a^{k+1}+_{k+1}C_1a^kb+_{k+1}C_2a^{k-1}b^2+\cdot\cdot\cdot+_{k+1}C_kab^k+_{k+1}C_{k+1}b^{k+1}}$となりまして、確かに${n=k+1}$のときも成り立ちました。証明終わりです。

さきほど後回しにしたところをご説明いたしますね。

${_kC_i+_kC_{i+1}=_{k+1}C_{i+1}}$が成り立つことですが、これは二項係数の基本的な性質です。組み合わせ的なご説明をいたしますね。${k+1}$個のものから、${i+1}$個のものを取り出す場合の数を考えます。ある具体的な品物Aを取り出すか、取り出さないかで場合に分けます。Aを取り出すならば、その場合は、残り${k}$個から${i}$個を取り出す場合の数となり、${_kC_i}$通りとなります。Aを取り出さないならば、その場合は、残り${k}$個から${i+1}$個を取り出す場合の数となり、${_kC_{i+1}}$通りとなります。これらの足し算なので、${_kC_i+_kC_{i+1}=_{k+1}C_{i+1}}$が成り立つわけです。パスカルの三角形を成立させているものは、これです。

これで、二項定理を数学的帰納法で証明することが終わりました。いかがでしょうか。なかなか気持ちがいいです。ご不明だったかたには申し訳ございません。当教室は個人指導でありまして、おひとりおひとりに合わせた授業をしております。不特定多数を相手にしたこのようなブログでは、どうしても説明不足になると思います。とくに、TeXを打つのが大変で…。ごめんなさいね。ご不明な点はきちんとご納得いただけるまでご説明いたしております。

これで、このブログ記事は終わりではありません。フィボナッチ数列の一般項のお話になります。フィボナッチ数列とは、以下のような漸化式で定義される数列です。

${a_1=1,a_2=1,a_{n+2}=a_n+a_{n+1}}$

具体的に数列を書き並べますと、${1,1,2,3,5,8,13,\cdot\cdot\cdot}$となります。前の２つの数を足したものが、つぎの数になるわけです。これの意味するところは割愛します。今回は、これの一般項について書きます。結論から書きますと、一般項は次のようになります。

${a_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)}$

なぜ急にこんな形をしているのか、これをどう導いたのかなぞですが、私もこれは単にGoogle検索して出しただけに過ぎません。しかし、数学的帰納法がいかに強力であるかを示すために、これを証明することによって文句なしにしてしまうということをします。

これは、${n=1,n=2}$のときに成り立つことを示したのち、${n=k,n=k+1}$のときに成り立つことを仮定して、${n=k+2}$のときに成り立つことを示しましょう。隣接３項間の漸化式ですからね。

まず、${n=1}$のときですが、右辺は、${\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})-(\frac{1-\sqrt{5}}{2}))=\frac{1}{\sqrt{5}}\cdot\sqrt{5}=1}$となって、成り立ちます。

つぎに、${n=2}$のときですが、右辺は、${\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^2-(\frac{1-\sqrt{5}}{2})^2=\frac{1}{\sqrt{5}}(\frac{6+2\sqrt{5}}{4}-\frac{6-2\sqrt{5}}{4})=\frac{1}{\sqrt{5}}\cdot\frac{4\sqrt{5}}{4}=1}$となりまして、やはり成り立ちます。

さて、${n=k,n=k+1}$のときに成り立つと仮定しまして、${n=k+2}$に成り立つことを示しましょう。漸化式から以下のことが言えます。

${a_{k+2}=a_k+a_{k+1}}$ ${=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^k-\frac{1-\sqrt{5}}{2})^k)+\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^{k+1}-\frac{1-\sqrt{5}}{2})^{k+1})}$ ${=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^k(1+\frac{1+\sqrt{5}}{2})-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^k(1+\frac{1-\sqrt{5}}{2})}$ ${=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^k(\frac{3+\sqrt{5}}{2})-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^k(\frac{3-\sqrt{5}}{2})}$ ${=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^k(\frac{6+2\sqrt{5}}{4})-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^k(\frac{6-2\sqrt{5}}{4})}$ ${=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^k(\frac{1+\sqrt{5}}{2})^2-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^k(\frac{1-\sqrt{5}}{2})^2}$ ${=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{k+2}-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^{k+2}}$

ほら、${n=k+2}$のときも言えましたでしょ。これで証明終わりです。これは、ゴールが見えているので、二重根号外しみたいなものも逆算でできますし、ほんとうに機械的な手順で証明できてしまいます。

最初に、どうやって一般項の式を思いついたのかは知りませんが、とにかく思いついちゃったらこのように証明してしまって、論理的に文句なしにすることができます。数学的帰納法の強力さを示したつもりです。いかがでしたでしょうか。

私は大学院で数学（位相幾何学）を専門としていましたが、ほんとうに背理法と帰納法はひんぱんに使ったものです。使われている論文もたくさん読みました。本日は、いかに数学的帰納法が強力か、というのを、二項定理の証明と、フィボナッチ数列の一般項がどうしてこうなるのかの証明で、お示しいたしました。ごめんなさいね、ついてこられなかったというかたには申し訳なかったです。繰り返しになりますが、当教室では、おひとりおひとりに合わせたご指導をしておりますので、これは難しすぎる(あるいは幼稚すぎる？)と思われたかたにもきちんと対応しておりますので、どうぞご安心くださいませ。珍しく、ガチガチの数学のブログ記事でした。二項定理の証明のやりかたは、２つの関数の積の微分（ライプニッツルール）の${n}$階導関数を導くときもまったく同じようにやれますので、興味のあるかたは、演習問題といたしますね。それではまた来週！