数学的帰納法

数学的帰納法の証明の仕組み 　 まず、奇数からなる次の数列について考えてみます。 　　ａ1＝１，ａ2＝１＋３，ａ3＝１＋３＋５，ａ4＝１＋３＋５＋７，ａ5＝１＋３＋５＋７＋９，・・・・　　これを計算すると 　　ａ1＝１，ａ2＝４，ａ3＝９，ａ4＝１６，ａ5＝２５，・・・・　　のようになります。この数字に規則性があり、 　　ａ1＝１ 2 ，ａ2＝２ 2 ，ａ3＝３ 2 ，ａ4＝４ 2 ，ａ5＝５ 2 ，・・・・　　のように表せることに気付きますか？ 　　さて、ここから数学的帰納法の仕組みです。（番号の小さいほうが案外解りにくいので、途中からの説明にしています。） 　　ａ4＝４ 2 　から始めます。 　　　　　　　　　　　　　　　　　　 次の項について　　ａ5＝（１＋３＋５＋７）＋９　　と考えると、 　　ａ5＝ａ4＋９＝１６＋９＝２５＝５ 2 　　となります。 　　　　　　　　　　　　　　　さらに、次の項について　ａ6＝（１＋３＋５＋７＋９）＋１１　　と考えると、 　　ａ6＝ａ5＋１１＝２５＋１１＝３６＝６ 2 　　となります。 　　　　　　　　　　　　　　　さらに、次の項について　ａ7＝（１＋３＋５＋７＋９＋１１）＋１３　　と考えると、 　　ａ7＝ａ6＋１３＝３６＋１３＝４９＝７ 2 　　となります。 　　　　　　　　　　　　　　　これを繰り返していけばいいのですが、数値（番号）を順に当てはめていたら、 　　　　　　　　　　　　　　　いつまでも終わりません。そこで、文字を利用します 　　ａk＝１＋３＋５＋７＋９＋１１＋・・・＋２ｋ−１＝ｋ 2 　と表せたとすると、 　　ａk+1＝（１＋３＋５＋７＋９＋１１＋・・・＋２ｋ−１）＋２ｋ＋１ 　　　　　＝ｋ 2 ＋２ｋ＋１＝（ｋ＋１） 2 　　　　となります。 　　この計算で、ｋ＝４ ならば、ａ4 を用いて ａ5 を示したことになります。この ａ5 を用いて ａ6 を示すには、 　　　　　　　　　　ｋ＝５ とすればいいのです。 　　ｋ は適当な自然数なので、一般的に証明できたことになります。また、証明の始まりが成り立つことが 　　いえてないと、この説明は意味を持ってきません。ですから、最初（普通ｎ＝１）の確認が要るのです。 Ｘ＋Ｙ＝ａ，ＸＹ＝ｂ　とするとき、次の問いに答えよ。 （１）Ｘ 2 ＋Ｙ 2 ，Ｘ 3 ＋Ｙ 3 を ａ，ｂを用いて表せ。 （２）Ｘ n ＋Ｙ n を ａ，ｂを用いて表したとき、ａ の ｎ 次式になることを証明せよ。

解答例 （１）　Ｘ 2 ＋Ｙ 2 ＝（Ｘ＋Ｙ） 2 −２ＸＹ＝ａ 2 −２ｂ， 　　　 Ｘ 3 ＋Ｙ 3 ＝（Ｘ＋Ｙ） 3 −３ＸＹ（Ｘ＋Ｙ）＝ａ 3 −３ａｂ （２）　［�T］ｎ＝１のとき　　Ｘ＋Ｙ＝ａ　であるから ａ の １次式になる。 　　　 　　　ｎ＝２のとき　　Ｘ 2 ＋Ｙ 2 ＝ａ 2 −２ｂ　　であるから ａ の ２次式になる。 　　　 ［�U］ｎ＝ｋ−１，ｋ で、Ｘ k-1 ＋Ｙ k-1 が ａ の ｋ−１次式，Ｘ k ＋Ｙ k が ａ のｋ次式であると仮定する。 　　　　　　 ｎ＝ｋ＋１　において、 　　　　　　　　　　　　　 Ｘ k+1 ＋Ｙ k+1 ＝（Ｘ＋Ｙ）（Ｘ k ＋Ｙ k ）−ＸＹ k −ＸＹ k 　　　　　　　　　　　　　　　　　　　　＝（Ｘ＋Ｙ）（Ｘ k ＋Ｙ k ）−ＸＹ（Ｘ k-1 ＋Ｙ k-1 ） 　　　　　　　　　　　　　　　　　　　　＝ａ（Ｘ k ＋Ｙ k ）−ｂ（Ｘ k-1 ＋Ｙ k-1 ） 　　　　　　　　　　　　　ここで仮定を用いると、ａ（Ｘ k ＋Ｙ k ）はａ の ｋ＋１次式，ｂ（Ｘ k-1 ＋Ｙ k-1 ）はａ の ｋ−１次式 　　　　　　　　　　　　　であるので、Ｘ k+1 ＋Ｙ k+1 は ａ のｋ＋１次式となり、ｎ＝ｋ＋１でも成立す る。 　　　　［�T］，［�U］より　　Ｘ n ＋Ｙ n はａ の ｎ 次式になる。 　　　ここでは、ｎ＝ｋ＋１の証明に、ｎ＝ｋ−１，ｋを用いるので、第一段階でｎ＝１，２を示す必要があります。 １，２，４，・・・，２ n-1 のｎ個の整数を適当に選んでそれらを加えると、１から２ n −１までの整数が すべてつくれることを、数学的帰納法を用いて証明せよ。 　（ここでは、証明 すべきことに注意してしださい。） 　一番重要なことが証明されてない例。 　　　　［�T］ｎ＝１のとき 　　　　　　　このとき、２ n-1 ＝１　なので、使う整数は１ だけであるから、つくれる整数は、１ だけである。 　　　　　　　また、２ n −１＝１　であるから、１から２ n −１まで、つまり１ だけになる。 　　　　［�U］ｎ＝ｋのとき、　１，２，４，・・・，２ k-1 の ｋ個の整数で、１から２ k −１までの整数がすべて つくれると仮定する。 　　　　　　　ｎ＝ｋ＋１のとき、１，２，４，・・・，２ k-1 の ｋ個の整数に ２ k が加わるので、 　　　　　　　　　　　　　　　ｎ＝ｋのときは、１から２ k −１までの整数がつくれたので、この最大値に、 　　　　　　　　　　　　　　　２ k を加えた　２ k ＋２ k −１＝２ k+1 −１までの整数がつくれる。 　　　　［�T］，［�U］より証明された。 　これと同様で、　　１＋２＋４＋・・・＋２ n-1 ＝２ n −１　　を証明しても同じです。 　=========================================================================================== 　ここで証明すべきことは、全ての整数つくれることです。上記の解答では最大値にしかなりません。 　　　　　　　　　　　ｎ＝ｋのときの証明まではそのまま使えます。これ以降の証明を示します。 　　　　　　　ｎ＝ｋ＋１のとき、１，２，４，・・・，２ k-1 ，２ k の ｋ＋１個の整数のなかで、２ k を用いないとｎ＝ｋの 　　　　　　　　　仮定で２ k −１までの整数がすべてつくれたから、２ k −１より大きい整数について考える。 　　　　　　　　　この、２ k −１より大きい整数を、２ k ＋ｒ とすると、ｒ は１，２，４，・・・，２ k-1 の ｋ個の整数で 　　　　　　　　　つくれる整数になる。つまり、ｒ は１から２ k −１までの整数がすべて含まれる。 　　　　　　　　　また、１，２，４，・・・，２ k-1 を用いないと、 ｒ ＝０ となるので、ｒ の可能な値は、 　　　　　　　　　ｒ ＝０，１，２，・・・・，２ k −１　である。よって、２ k ＋２ k −１＝２ k+1 −１までの整数が全てつくれる。 　 　　 　　 　　 　　 漸化式