皆さんこんにちは。和からの数学・統計講師の川原です。 以前私は帰納法と演繹法についての記事を書きましたが、数学になじみのある方は帰納法と聞けば数学的帰納法を思い出すのではないでしょうか。本日は数学的帰納法についてお話してみます。 \(\ge 0\), ここはkに関する数学的帰納法で証明を記述するの正式でしょうが、ここでは割愛します。, (左辺) \(\ge \sqrt{\sqrt{a_1 a_2}\sqrt{a_3 a_4}}\) P(1) が成り立つ事を示す。; 任意の自然数 k に対して、「 P(k) ⇒ P(k + 1) 」が成り立つ事を示す。 以上のような論法の起源は、古代ギリシャの哲学者ミレトスのエウブリデス (en) が作ったとされるハゲ頭のパラドックス (Paradox of the Bald Man)[6]に帰せられる。これは砂山のパラドックスの起源としても知られる。, 前述のジョークにはさまざまなバリエーションがあるが、いずれも「少量の増加程度では大差ない。よって数学的帰納法より沢山の増加でも差はない」という誤謬を利用している。, 初期の例としては、プラトンによるパルメニデス(紀元前 370年)において暗黙に帰納法を使用した証明がみられる[7]。また数学的帰納法としての痕跡は、素数が無限個あることを示したユークリッドの証明や、バースカラ2世による "cyclic method(英語版)"[8] に見ることができる。通常とは逆に、パラメータとなる自然数が減少していく逐次的な論法は、砂山のパラドックスにみられる。つまり、10,000粒の砂粒が砂山を形成し、そこから一粒の砂を取り除いても砂山が残るならば、一粒だけ残った砂(或いは全ての粒を取り去った後)でもなお砂山を形成するといえる。, 等差数列について暗黙に数学的帰納法を用いた証明は、紀元 1000年ごろにal-Karaji(英語版)による "al-Fakhri" に扱われている。al-Karaji は二項定理やパスカルの三角形を示すのに数学的帰納法を用いた。, しかし、これらの古代の数学者たちは帰納法の仮定を明示することはしていない。別の似た例としては(Freudenthal が注意深く示したように、Vacca が著したものとは対立するが)、Francesco Maurolico(英語版)が 1575年の著作 "Arithmeticorum libri duo" にて最初の n 個の奇数の和が n2 に等しいことを示す際にこの技術を用いている。明示された形での数学的帰納法の原理はパスカルがその著作 "Traité du triangle arithmétique" (1655)にて与えた。フランス人フェルマーは、帰納法と関連する、無限降下法による間接的な証明をうまく使っている。帰納法の仮定はヤコブ・ベルヌーイによっても使われ、以後多少よく知られるようになった。現代的な厳密さをもち体系的な数学的帰納法の原理の扱いは 19世紀に入ってジョージ・ブール、オーガスタス・ド・モルガン、チャールズ・サンダース・パース、ジュゼッペ・ペアノ、 リヒャルト・デーデキントによって為された。, ここでは「髪の毛が少ない人」の意味で「ハゲ」という言葉を用いている。髪の毛の本数が0本である必要は無い。, 松村英之、『集合論入門』、朝倉書店〈基礎数学シリーズ 5〉、1966年、p. [数学的帰納法]は高校数学で[背理法]に並んで重要な証明法です.初めて[数学的帰納法]を学んだとき不思議な考え方に戸惑う人は多いですが,一度分かってしまえば難しいものではありません.この記事では,具体例から[数学的帰納法]を解説します. 数学的帰納法の簡単な変化形 数学的機能法の変化形(1) まず、簡単にわかるのは、最初のn=1の場合をn=0にしたり、n=2にすることです。 (1) n=2の場合に成立。 (2) n=kの場合が成立するならn=k+1の時 … 数学的帰納法(すうがくてききのうほう、英: mathematical induction)は自然数に関する命題 P(n) が全ての自然数 n に対して成り立っている事を証明するための、次のような証明手法である[注 1]。, 上で1と2から3を結論づける所が数学的帰納法に当たる。自然数に関するペアノの公理の中に、ほぼ等価なものが含まれている。, なお、数学的「帰納」法という名前がつけられているが、数学的帰納法を用いた証明は帰納ではなく、純粋に自然数の構造に依存した演繹論理の一種である。2 により次々と命題の正しさが"伝播"されていき、任意の自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられた[要出典]。ジョン・ウォリスによって、彼の著作Arithmetica Infinitorumの中で、この方法にinductionという名前が与えられたとされる[1] [2]。, 高校の教科書等の初等的な解説書ではドミノ倒しに例えて数学的帰納法を説明しているものも多い。P(n) を「n 枚目のドミノが倒れる」の意味だとすれば、上の論法は以下のようになる:, が正しい事が分かる。次に k = 1, 2, ... に対して 2 を適用する事で、, が分かる。(a), (b) より、P(2) が成り立ち、この事実と (c) を組み合わせる事により P(3) が従う。以下同様に P(4), P(5), …も従い、結局 3 の, ただし、以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であって、1, 2 と 3 の間にはギャップがある。詳しくは後述の「数学的帰納法の形式的な取り扱い」の項目を参照されたい。, 数学的帰納法が成り立つことを数学的帰納法の原理といい、ペアノの公理Ⅴが数学的帰納法の原理そのものを表しているが、数学的帰納法の原理をあえて証明するならば、次のように証明される。, 自然数rがMの要素であるとすると、Mの定義によってPrが正しい。また、数学的帰納法の手順より、, 従ってペアノの公理Vによって、MはNに一致し、よって命題Pnがすべての自然数において成り立つ。, 数学的帰納法には次のようなバリエーションもあり、場合によってはこれらを用いる必要がある。これらのバリエーションの正しさは、上で述べた標準的な形の数学的帰納法を用いて示すことができる。, 変数変換によって明らかなように、変数 n が表す範囲は n → n + 1 という操作で閉じていれば {1, 2, ...} である必要はなく、0 を自然数に含めることにしたり、あるいは任意の整数 m に関する {m, m + 1, ...} という範囲でもよいことになる。, 例えば n → n + 1 ではなく、n → n + 2 で証明し、開始点が P(2) であれば、全ての正の偶数で証明できる。バリエーションとしては、P(2) から n → n + 2 で正の偶数を証明し、P(1) から n → n + 2 で正の奇数を証明し、よって全ての自然数で成立するという証明方法もある。他にも、P(0) から n → n + 1 と n → n − 1 を両方証明し、全ての整数で成立することを証明するというのもある。, 仮定として P(k) だけでなく P(1) から P(k − 1) までのすべて(もしくは一部)を用いる。これを完全帰納法(英: complete induction、これは同じく完全帰納法と訳される perfect induction とは別物)もしくは累積帰納法(英: course of values induction)という。, この議論と次に述べる「先立つすべての結果を用いる」形の数学的帰納法の正しさは自然数全体の集合 N が通常の大小関係 < によって整列されていることによる。< が N 上の整列順序であることは、最初に述べた標準的な形の数学的帰納法を用いることで証明される。, 数学的帰納法は自然数に関する論法だが、自然数以外の集合に対しても、集合の元を適切に順序づける事で数学的帰納法を適用できる事がある。例えば直積集合 N × N 上に辞書式順序, 次の等式が成り立つという命題を P(n) とし、この命題が任意の自然数 n について成立することを数学的帰納法を用いて証明する。, 次に、任意の自然数 k をとる。P(k) は下記の通りであり、これが成立すると仮定する。, これが成立することを使いて P(k + 1) の左辺を計算すると、P(k + 1) も成立することが分かる。, 以上から、数学的帰納法により、任意の自然数 n について命題 P(n) が成立する。, 数学的帰納法の原理を説明する前に、まず前述した直観的説明のどこにギャップがあったのかを説明する。前述の説明では、まず我々は P(1) を結論づけ、次に (a), (b) から P(2) を結論づけ、さらにそれと (c) を組み合わせる事で P(3) を結論づけ、さらにそれと(d)を組み合わせる事で P(4) を結論づけた。以上の議論から分かるように、P(2) を結論づける為には2ステップの推論、P(3) を結論づけるには3ステップの推論、…、P(100) を結論づけるには100ステップの推論が必要となる。, 従って有限回のステップでは有限個の n に対してしか P(n) を結論づける事ができず、「無限個ある自然数全てに対して P(n) が成り立つ」という数学的帰納法の結論について有限の長さの証明が与えられたとはいえない。これが前述した直観的説明におけるギャップである。, そこで、ペアノ算術などの形式的な体系では、数学的帰納法を証明に用いてよいことが公理として仮定されるのが普通である。つまり、形式的には、自然数の性質から数学的帰納法の正しさが証明できるのではなく、逆に自然数の本質的な性質を与える推論規則として数学的帰納法が仮定される、ということになる。, この原理からもともとの形の数学的帰納法が導かれることは,次のようにして示せる。帰納法の仮定 1., 2.

数学B数学的帰納法 問題「nを自然数とする時、次の等式が成り立つことを、数学的帰納法を用いて証明しろ」1+2+2²+・・・+2ⁿ⁻¹=2ⁿ-1オレンジのライン部分がなぜこうなるのか分かりません。教えて欲しいです。 ②の式を代入しただけでは? 【背理法2|背理法が有効な証明の2つのタイプと例】, 「任意の自然数$n$に対して,〜が成り立つことを示せ.」という問題に[数学的帰納法]が有効であることは冒頭に述べた通りです., もし1が欠けていると「最初のピースが倒せない」し,2が欠けていると「$k$個目が倒れても,$k+1$個目が倒れてくれないかもしれない」ので,1,2のどちらが欠けても[数学的帰納法]は成り立ちませんね., と続いていくので,任意の自然数$n$に対して成り立つことが証明できたことになるわけです., 注意ですが,問題によっては「3以上の任意の自然数$n$に対して,〜を示せ.」などとなっている場合がありますが,このときは, 数学的帰納法は「最初の場合に成り立つこと」を示し,「$n=k$で成り立つとき,$n=k+1$でも成り立つこと」を示すのが基本的な数学的帰納法の王道パターンである., 任意の自然数$n$に対して,等式$(*):1+3+5+\dots+(2n-1)=n^2$が成り立つことを数学的帰納法により示しましょう., $((*)の左辺)=1=1^2=((*)の右辺)$となって,等式$(*)$が成り立つことが分かります., [2] 「$n=k$のとき$(*)$が成り立つ」とし,$n=k+1$のとき$(*)$が成り立つことを示します.すなわち,「$1+3+5+\dots+(2k-1)=k^2$が成り立つ」とし,$1+3+5+\dots+\{2(k+1)-1\}=(k+1)^2$が成り立つことを示します., 2以上の任意の自然数$n$に対して,不等式$(*):3^n>4n$が成り立つことを数学的帰納法により示します., $((*)の左辺)=3^2=9>8=4\times2=((*)の右辺)$となって,不等式$(*)$が成り立つことが分かります., [2] 「$n=k$ $(k\ge2)$のとき$(*)$が成り立つ」とし,$n=k+1$のとき不等式$(*)$が成り立つことを示します.すなわち,「$3^k>4k$が成り立つ」とし,$3^{k+1}>4(k+1)$が成り立つことを示します., $a_1=1$, $a_{n+1}=\dfrac{a_n}{1+a_n}$だから,数列$\{a_n\}$を初項から順に求めると,, となります.よって,数列$\{a_n\}$の一般項は$a_n=\dfrac{1}{n}$と予想できるので,これを数学的帰納法により示します., [2] 「$n=k$のとき予想が正しい」とし,$n=k+1$のとき予想が正しいことが成り立つことを示します.すなわち,「$a_n=\dfrac{1}{n}$が成り立つ」とし,$a_{n+1}=\dfrac{1}{n+1}$が成り立つことを示します., [1], [2]より,題意の一般項は$a_n=\dfrac{1}{n}$となります., 数学的帰納法は「任意の自然数$n$に対して,〜を示せ」型の証明で用いることが多い.また,例3のように「〜を求めよ.」といった場合にも「予想を立てて,数学的帰納法により証明する」という手法を用いることもある., このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。, 「任意の自然数$n$に対して,〜が成り立つことを示せ.」という問題に[数学的帰納法]が有効である, 「$n=k$のときに成り立つ」とし,それを利用して$n=k+1$のときに成り立つことを示す., 「$1+3+5+\dots+(2k-1)=k^2$が成り立つ」とし,$1+3+5+\dots+\{2(k+1)-1\}=(k+1)^2$が成り立つことを示します., 「$3^k>4k$が成り立つ」とし,$3^{k+1}>4(k+1)$が成り立つことを示します., 「$a_n=\dfrac{1}{n}$が成り立つ」とし,$a_{n+1}=\dfrac{1}{n+1}$が成り立つことを示します., 任意の自然数$n$に対して,等式$(*):1+3+5+\dots+(2n-1)=n^2$が成り立つことを示せ., 2以上の任意の自然数$n$に対して,不等式$(*):3^n>4n$が成り立つことを示せ., 漸化式$a_1=1,a_{n+1}=\dfrac{a_n}{1+a_n}$を満たす数列$\{a_n\}$の一般項を求めよ.. まず、簡単にわかるのは、最初のn=1の場合をn=0にしたり、n=2にすることです。, (3) 上記の(1)(2)が成立することから、n≧2のすべての自然数に対して成立することが示せた。, (3) 上記の(1)(2)が成立することから、n≧1のすべての自然数に対して成立することが示せた。, \(n\)個の正の実数a_1,a_2,a_nに対して

【漸化式の基本3|数学的帰納法はイメージは「ドミノ倒し」!】←今の記事, 【背理法1|背理法はこう考える!仕組みを具体例から理解する】 \(=\frac{a_1+a_2}{2}-\sqrt{a_1a_2}\) を満たす論理式 P(n) が与えられたとする。自然数の部分集合 A を A = { n ∈ N : ¬ P(n) } によって定める。この A が空集合であるということを示したい。そうでないと仮定すると、Aに属する最小の自然数 a を取ることができるが、P(0)は成り立っていることから a は0でない。従って、ある自然数 b について a = b + 1となっているが、a は A に属する最小の自然数であったということから、b ∉ A であり、P(b) は成り立つことになる。帰納法の仮定から P(a) も成り立つことになり、これは矛盾である。, 逆に、「n 以下の任意の自然数 k について k ∉ A」という形の命題 P(n) を考えることで、数学的帰納法から上の原理を導くことができる。A を自然数のある集合とし、A に属する最小の自然数が存在しないと仮定する。もし P(0) が成り立たないと、0 が A に属する最小の自然数となって仮定に反するから、P(0) は成り立つ。P(n) が成り立つとし、もし P(n + 1) が成り立たないとすると、n + 1 が A の最小の自然数となって仮定に反するから、P(n + 1) も成り立つ。よって数学的帰納法により A は空となる。, 上記の形で自然数について定式化された数学的帰納法は、任意の整列集合に対して次のように一般化することができる。この一般化を超限帰納法 (ちょうげんきのうほう、英: transfinite induction)という。任意濃度の集合は選択公理と同値な整列可能定理により整列順序を持つとすることができるので、選択公理を含む公理系であれば超限帰納法は任意濃度の集合に対して成立すると主張できる。, ただし、"<" は a < b ⇔ ( a ≤ b ∧ a ≠ b) で定義される二項関係とする。, (1) A は整列集合であるから順序 "≤" について最小元を持つ。これを、a0 とする。定理の条件において a = a0 と置けば、x < a を満たす A の元は存在しないので、「x < a を満たす A の全ての元 x について P(x) が真」という命題は無条件に真であり、従って、定理の条件を満たすためにはP(a0) は真でなければならない[4]。, (2) つぎに超限帰納法の言明が偽と仮定する。これはある整列集合Aおよび、その上で定義された命題関数 P の組が存在して、定理の条件を満たしても P(x) が偽となる A の元 x が存在することを意味する。Pが偽となる A の元全ての集合を Af とする。A は整列集合であるからその部分集合である Af も最小元を持つ。これを a とする。当然 P(a) は偽である。, (3) (1)で証明したように、定理の条件を満たしている限り A の最小元a0 についてP(a0) は真であるから a はa0 ではあり得ない。従って、Aa = {x | x ∈ A ∧ x < a} と置けば、Aa は空ではない (少なくとも a0 を含む)。, (4) a は P が偽となる A の最小元であるから、x ∈ Aa であれば、P(x) は真である。従って、定理の条件により P(a) は真とならねばならないが、これは前言と矛盾する。, (5) 以上から、定理の条件を満たしても P(x) が偽となる x ∈ A が存在するような整列集合 A と、その上で定義される命題関数 P の組は存在し得ないことになる。従って超限帰納法の言明は真である。, 無限下降列が存在しない二項関係を整礎関係という。整礎関係が定義された集合に対して次が成り立つ。これを整礎帰納法(英: well-founded induction)という。, 超限帰納法は整礎帰納法の特殊な場合である。特に、超限帰納法においては、任意の空でない部分集合に最小元が存在する、という性質が、整礎帰納法においては、任意の空でない部分集合に極小元が存在する、という性質に対応している。, もちろんこの「証明」には理論上の根本的な問題点がある。この「証明」の問題点は、「ハゲ」の定義を厳密に毛が何本以下であるかで与えることができない点、もしくは「ハゲ」を定義できたとして、任意の「ハゲ」に髪の毛を一本足したときに、必ず「ハゲ」になる訳ではない点にある。

128。, Mathematical Induction Provides A Tool For Proving Large Problems By Proceeding Through The Solution Of Smaller Increments, Origin of the Name "Mathematical Induction" Florian Cajori, https://ja.wikipedia.org/w/index.php?title=数学的帰納法&oldid=79417844. \(= \sqrt[4]{a_1 a_2a_3 a_4}\), これで任意の自然数kに対して\(n=2,2^2,\cdots,2^k\)に対して証明できました。, たくさんのnに対して証明ができていますが、これは飛び飛びのnに対して証明されただけにすぎません。, (3) \(n=2^k\)の場合を利用して\(n le 2^k\)の場合を証明する, ここは、式をだらだら書くより、例で示したほうがわかりやすいのでn=5の場合を示します。, \(5 \le 2^{k+1}\)となる自然数kが存在します。この場合、k=2です(もちろん2以上ならなんでもよい)。, ここで、\(A=\frac{a_1 + a_2+  a_3 +  a_4 + a_5}{5}\)とおき、 \(\ge \frac{\sqrt{a_1 a_2}+\sqrt{a_3 a_4}}{2}\) \[\frac{a_1+a_2+\cdots+a_n}{n}  \ge  \sqrt[n]{a_1 a_2 \cdots a_n}\], が成立することです。山のように証明方法があるそうですが、数学的帰納法で証明します。, \(n=2\)の場合は、簡単な式の変形で証明することができますが、\(n\)個になると、式の変形で証明するのはかなり困難です。, (左辺)-(右辺) さらに、\(a_6=a_7=a_8=A\)とおくと、(2)で示した結果から、, \( A=\frac{a_1 + a_2+  a_3 + \cdots + a_8}{8} \ge \sqrt[8]{a_1 a_2 a_3 a_4 a_5 A^3}\), \( A \ge \sqrt[8]{a_1 a_2 a_3 a_4 a_5 } A^{3/8}\)

2020/2/18 \( A \ge (a_1 a_2 a_3 a_4 a_5 )^{1/5}\), 上の相加平均、相乗平均の証明では、n=2を繰り返してn=4の証明を行い、n=4の証明をつかってn=3の証明をしています。同様に、n=4の証明からn=8の証明を行い、n=8の証明をつかって、n=5,6,7の証明をしています。, このような手順で、n=2,4,3,8,5,6,7,16,9,10,11,12,13,14,15,32,17…の順序で相加平均と相乗平均の関係式を証明することができました。\(2^k\)の場合を先に証明して、\(2^k\)より小さい自然数の証明をしています。, 上記まとめでは、「n=2,4,3,8,5,6,7,16,9,10,11,12,13,14,15,32,17…の順序で相加平均と相乗平均の関係式を証明した」と書きました。もちろん、これはこれでいいのですが、必ずしもこの順序でなくてもよいことがわかります。例えば、n=2,4,8,16,32,3,5,6,7,9,10,11,12,13,14,15,17,…の順序でも証明ていることがわかります。先に、n=32の場合を証明すると、32より小さい自然数nに対しては証明できるからです。, 任意の自然数kに対して、\(n=2^k\)とおくと、「\(\frac{\sum_{j=1}^{n}a_j}{n} \ge \sqrt[n]{\prod_{j=1}^n a_j} \)が成立」を証明することになっています。こちらは、kに注目してみると小さいほうから順序よく証明していることになります。.