第２問（１）超解説その３（数学的帰納法の説明）

第２問 2008年度東大数学理系第５問
自然数ｎに対して、をで表す。たとえば，
，である。
（１）ｍを0以上の整数とする。はで割り切れるが、
　　　では割り切れないことを示せ。
（２）ｎが２７で割り切れることが、
　　　が２７で割り切れるための必要十分条件であることを示せ。

（１）の超解説その３（数学的帰納法の説明）

（１）の命題を（＊）とし、（＊）が成り立つことを数学的帰納法で示す。
ⅰ　ｍ＝０のとき、
　　　＝＝＝１
　　　＝＝１
　　　＝＝３
　　したがって、はで割り切れが、では割り切れないから
　　(＊)は成り立つ。
ⅱ　ｍ＝ｋ(≧０)とき(＊)が成り立つと仮定すると、
　　はで割り切れるが、では割り切れないから、
　　３で割り切れない適当な整数ｐが存在して、
　　＝ｐ
　　ｍ＝ｋ＋１の場合を考える。
　　＝
　　　　　　　　＝
　　　　　　　　＝
　　　　　　　　＝
　　ここで、の各位の数字の和は３なので、
　　は３の倍数であるが、９の倍数ではない。
　　よって、３で割り切れない整数ｑによって
　　＝３ｑ
　　とおける。このとき
　　＝３ｑ・ｐ＝ｐｑ
　　ｐ，ｑは３の倍数でないので、適当な整数ａ，ｂによって、
　　ｐ＝３ａ±１，ｑ＝３ｂ±１
　　と表せる。４つの組み合わせ
　　ｐｑ＝３（３ａｂ＋ａ＋ｂ）＋１，３（３ａｂ－ａ＋ｂ）－１，３（３ａｂ＋ａ－ｂ）－１，３（３ａｂ－ａ－ｂ）＋１
　　はいずれも３の倍数ではない。
　　したがって、はで割り切れるが、では割り切れないから、
　　(＊)はｍ＝ｋ＋１の場合も成り立つ。

　以上ⅰⅱより、０以上のすべての整数について(＊)が成り立つことが証明された。

を超解説する！
細部の説明に入る前に数学的帰納法の枠組みを確認しておきましょう。
数学的帰納法とは、次の３段手続きによって証明する方法です。

ⅰ ｎ＝１のとき命題が成り立つことを示す。
ⅱ ｎ＝ｋのとき命題が成り立つと仮定すると、ｎ＝ｋ＋１でも成り立つことを示す。
以上ⅰⅱから、すべての自然数について命題が成り立つと宣言する。

なぜ、これで命題がすべての自然数ついて成り立つといえるでしょうか。

これは将棋倒し（ドミノ倒し）であると思えば良いのです。
ⅰでは、将棋の１枚目の駒（ドミノの１枚目）が倒れることを証明します。
ⅱでは、ｎ枚目の駒が倒れると仮定すると、ｎ＋１枚目が倒れることを証明します。
この２つによって、すべての駒が倒れることが証明されます。

？？？どうして？
ポイントは、
ⅱでは、『ｎ枚目の駒が倒れると仮定すると、ｎ＋１枚目が倒れることを証明します。』
の赤のところが抽象的なｎとなっているところです。
このｎは自然数であれば何でも変身します。
場合によってはｎは１になりますし、２にも３にも４にも・・・１万にもなります。
例えば、ｎが１に変身するとき、
１枚目の駒が倒れると仮定すると、１＋１枚目が倒れる
＝１枚目の駒が倒れると仮定すると、２枚目が倒れる
ｎが２に変身するとき、
２枚目の駒が倒れると仮定すると、２＋１枚目が倒れる
＝２枚目の駒が倒れると仮定すると、３枚目が倒れる
ｎが３に変身するとき、
３枚目の駒が倒れると仮定すると、３＋１枚目が倒れる
＝３枚目の駒が倒れると仮定すると、４枚目が倒れる
ｎが４に変身するとき、
４枚目の駒が倒れると仮定すると、４＋１枚目が倒れる
＝４枚目の駒が倒れると仮定すると、５枚目が倒れる
　　　　　　・
　　　　　　・
　　　　　　・
と無限に続いていきます。
つまり、ⅱが言っていることは、
１枚目が倒れれば、２枚目が倒れる
２枚目が倒れれば、３枚目が倒れる
３枚目が倒れれば、４枚目が倒れる
４枚目が倒れれば、５枚目が倒れる
　　　　　　・
　　　　　　・
　　　　　　・
ということです。
そして、ⅰによって１枚目が倒れることが保証されているのです。
ⅰとⅱを合わせれば、すべての駒が倒れることが証明されます。

ⅰでは、将棋の１枚目の駒（ドミノの１枚目）が倒れることを証明します。
ⅱでは、ｎ枚目の駒が倒れると仮定すると、ｎ＋１枚目が倒れることを証明します。
を
ⅰ ｎ＝１のとき命題が成り立つことを証明する。
ⅱ ｎ＝ｋのとき命題が成り立つと仮定すると、ｎ＝ｋ＋１でも成り立つことを証明する。
と書き換えれば、ⅱでは、
ｎ＝１のとき成り立てば、ｎ＝２でも成り立つ。
ｎ＝２のとき成り立てば、ｎ＝３でも成り立つ。
ｎ＝３のとき成り立てば、ｎ＝４でも成り立つ。
ｎ＝４のとき成り立てば、ｎ＝５でも成り立つ。
　　　　　　・
　　　　　　・
　　　　　　・
と無限に続きます。
そして、ⅰではｎ＝１のとき、成り立つことが保証されています。
ⅰとⅱを合わせれば、命題はすべての自然数について成り立つことがいえるわけです。

によって確かにすべての自然数について成り立つことが分かると思います。
尚、命題の始まりは１でなくてもよくて、ｎ＝１をｎ＝０とすれば

ⅰ ｎ＝０のとき命題が成り立つことを示す。
ⅱ ｎ＝ｋのとき命題が成り立つと仮定すると、ｎ＝ｋ＋１でも成り立つことを示す。
以上ⅰⅱから、０以上のすべての整数について命題が成り立つと宣言する。

０以上のすべての整数について成り立つことになります。
また、

ⅰ ｎ＝６のとき命題が成り立つことを示す。
ⅱ ｎ＝ｋのとき命題が成り立つと仮定すると、ｎ＝ｋ＋２でも成り立つことを示す。

のようなバリエーションもあります。
このときの結論は何ですか。

（１）の解答その１超解説その２へ　（１）の解答その１超解説その４へ

　

数独ナンプレ解き方コツ解法難問テクニック研究

数独フリーソフト数独自動生成無料アプリ難問作成プログラム

魔方陣数独で学ぶ初心者のための VBA 入門基礎から応用まで
 数独ナンプレ難問シンプルな解き方・簡単な解法・わかりやすい攻略法の研究

VB講義へ
ＶＢ講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための VC++による C言語入門 C++ 入門基礎から応用まで第１部
 初心者のための VC++による C言語入門 C++ 入門基礎から応用まで第２部
初心者のための VC++による C言語入門 C++ 入門基礎から応用まで第３部
初心者のためのEclipseによるJava入門基礎から応用まで
 初心者のためのJava入門サイト基礎から応用まで

本サイトトップへ