数学的帰納法すうがくてききのうほうと再帰的定義さいきてきていぎ

離散数学りさんすうがくdiscrete mathematicsでは、対象たいしょうを 1 つずつ増ふやす議論ぎろんがよく表あらわれる。数学的帰納法すうがくてききのうほうmathematical inductionは、そのような「最初さいしょに成なり立たち、次つぎへ進すすめるなら、すべてで成なり立たつ」という構造こうぞうを証明しょうめいにしたものである。

数学的帰納法すうがくてききのうほうmathematical inductionは、自然数しぜんすうに沿そって命題めいだいを全体ぜんたいへ広ひろげる証明法しょうめいほうである。再帰的定義さいきてきていぎrecursive definitionは、最初さいしょの値あたいと前まえの値あたいから次つぎを決きめる規則きそくで対象たいしょうを定義ていぎする。

Mathematical induction数学的帰納法すうがくてききのうほう and recursive definitions再帰的定義さいきてきていぎ

In discrete mathematics離散数学りさんすうがく, arguments often add objects one by one. Mathematical induction数学的帰納法すうがくてききのうほう turns the structure "it holds at the start, and if it can advance to the next case, then it holds everywhere" into a proof method.

Mathematical induction数学的帰納法すうがくてききのうほう is a proof method that extends a proposition along the natural numbers自然数しぜんすう. A recursive definition再帰的定義さいきてきていぎ defines objects by giving an initial value and a rule that determines the next value from earlier values.

1数学的帰納法すうがくてききのうほうの形かたち

自然数しぜんすう $$n$$n に関かんする命題めいだい $$P\left(n\right)$$P(n) をすべての $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}{n}_0$$n\ge n_0 で示しめしたいとする。このとき、次つぎの 2 つを示しめす。

最初さいしょの式しきを基底段階きていだんかいbase case、次つぎの式しきを帰納段階きのうだんかいinduction stepという。帰納段階きのうだんかいinduction stepで仮定かていする $$P\left(k\right)$$P(k) を帰納法きのうほうの仮定かていinduction hypothesisという。

基底きていbase caseと帰納法きのうほうのステップinduction stepの両方りょうほうが必要ひつようである。いくつかの例れいを確認かくにんするだけでは全すべての $$n$$n を示しめしたことにならず、仮定かてい $$P\left(n\right)$$P(n) から次つぎの $$P(n+1)$$P(n+1) を導みちびく論理ろんりが必要ひつようである。

1Induction form

Suppose we want to prove a proposition命題めいだい $$P\left(n\right)$$P(n) about a natural number自然数しぜんすう $$n$$n for all $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}{n}_0$$n\ge n_0. Then we prove the following two statements.

The first statement is the base case基底段階きていだんかい, and the second statement is the induction step帰納段階きのうだんかい. The temporary assumption $$P\left(k\right)$$P(k) used inside the induction step is the induction hypothesis帰納法の仮定.

Both the base case基底段階きていだんかい and the induction step帰納段階きのうだんかい are necessary. Checking several examples does not prove all $$n$$n; the proof needs a logical step that derives $$P(n+1)$$P(n+1) from the assumption $$P\left(n\right)$$P(n).

2なぜこれで十分じゅうぶんか

数学的帰納法すうがくてききのうほうmathematical inductionは、ドミノ倒たおしの比喩ひゆで理解りかいできる。最初さいしょのドミノが倒たおれることが基底段階きていだんかいbase caseであり、任意にんいのドミノが倒たおれたら次つぎも倒たおれることが帰納段階きのうだんかいinduction stepである。すると、すべてのドミノが倒たおれる。

厳密げんみつには、自然数しぜんすうの整列性せいれつせいwell-ordering propertyと同値どうちな原理げんりとして理解りかいできる。もし成なり立たたない $$n$$n があれば、その中なかで最小さいしょうのものが存在そんざいする。その最小値さいしょうちは基底段階きていだんかいではなく、直前ちょくぜんまでは成なり立たつはずなので、帰納段階きのうだんかいと矛盾むじゅんする。

基底きていbase caseが最初さいしょの到達点とうたつてんを与あたえ、帰納法きのうほうのステップinduction stepが一歩先いっぽさきへ進すすめる規則きそくを与あたえる。有限回ゆうげんかいこの規則きそくを繰くり返かえすことで、任意にんいの自然数しぜんすうに到達とうたつする。

2Why it works

Mathematical induction数学的帰納法すうがくてききのうほう can be understood through the domino metaphor. The base case基底段階きていだんかい says that the first domino falls. The induction step帰納段階きのうだんかい says that whenever an arbitrary domino falls, the next one also falls. Therefore every domino falls.

More rigorously, induction can be understood as a principle equivalent to the well-ordering property整列性せいれつせい of the natural numbers. If some $$n$$n failed to satisfy $$P\left(n\right)$$P(n), there would be a smallest failing $$n$$n. That smallest value cannot be the base case, and the previous case should already hold, so the induction step gives a contradiction.

The base case基底段階きていだんかい gives the first reachable point, and the induction step帰納段階きのうだんかい gives the rule for moving one step forward. Repeating this rule finitely many times reaches any chosen natural number自然数しぜんすう.

3具体例ぐたいれい：有限集合ゆうげんしゅうごうの冪集合べきしゅうごうの大おおきさ

この例れいは、べき集合しゅうごうpower setの正式せいしきな講義こうぎより前まえに置おく帰納法きのうほうの例れいである。ここでは最小限さいしょうげんとして、$$\left|A\right|$$|A| は $$A$$A の元げんelementの個数こすう、$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) は $$A$$A の部分集合ぶぶんしゅうごうsubset全体ぜんたいの集合しゅうごうset、有限集合ゆうげんしゅうごうfinite setは元げんを $$n$$n 個こもつ集合しゅうごうとして扱あつかう。

$$\left|A\right|=n$$|A|=n のとき、$$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2^n$$|\mathcal P(A)|=2^n を示しめす。

基底段階きていだんかいとして、$$n=0$$n=0 のとき $$A=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$A=\varnothing であり、

なので $$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=1=2^0$$|\mathcal P(A)|=1=2^0 である。ここで $$n=0$$n=0 の場合ばあいを明示めいじすることが重要じゅうようである。空集合くうしゅうごうは例外れいがいではなく、公式こうしきの出発点しゅっぱつてんである。

帰納段階きのうだんかいとして、$$\left|A\right|=k$$|A|=k のとき $$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2^k$$|\mathcal P(A)|=2^k と仮定かていする。新あたらしい元げん $$a\notin A$$a\notin A を加くわえた集合しゅうごう $$A^{\prime }=A\cup \left\{a\right\}$$A'=A\cup\{a\} を考かんがえる。$$A^{\prime }$$A' の部分集合ぶぶんしゅうごうは、$$a$$a を含ふくまないものと含ふくむものに分わかれる。含ふくまないものは $$A$$A の部分集合ぶぶんしゅうごうであり、含ふくむものは $$B\cup \left\{a\right\}$$B\cup\{a\} の形かたちで $$B\subseteq A$$B\subseteq A と一対一いちたいいちに対応たいおうする。したがって

である。

3Worked theorem: size of a power set

This example appears before the formal lecture on power sets[べき集合]. Here, $$\left|A\right|$$|A| means the number of elements元げん of $$A$$A, $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) means the set集合しゅうごう of all subsets部分集合ぶぶんしゅうごう of $$A$$A, and a finite set有限集合ゆうげんしゅうごう is treated as a set with $$n$$n elements.

We prove that if $$\left|A\right|=n$$|A|=n, then $$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2^n$$|\mathcal P(A)|=2^n.

As the base case基底段階きていだんかい, when $$n=0$$n=0 we have $$A=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$A=\varnothing and

so $$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=1=2^0$$|\mathcal P(A)|=1=2^0. It is important to state the case $$n=0$$n=0 explicitly. The empty set is not an exception; it is the starting point of the formula.

For the induction step帰納段階きのうだんかい, assume that $$\left|A\right|=k$$|A|=k implies $$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2^k$$|\mathcal P(A)|=2^k. Add a new element元げん $$a\notin A$$a\notin A and consider $$A^{\prime }=A\cup \left\{a\right\}$$A'=A\cup\{a\}. Each subset部分集合ぶぶんしゅうごう of $$A^{\prime }$$A' either does not contain $$a$$a or does contain $$a$$a. The subsets not containing $$a$$a are exactly the subsets of $$A$$A, and the subsets containing $$a$$a correspond one-to-one to sets of the form $$B\cup \left\{a\right\}$$B\cup\{a\} with $$B\subseteq A$$B\subseteq A. Therefore

4再帰的定義さいきてきていぎ

再帰的定義さいきてきていぎrecursive definitionは、最初さいしょの対象たいしょうと、次つぎの対象たいしょうを作つくる規則きそくによって全体ぜんたいを定さだめる方法ほうほうである。

たとえば数列すうれつ $$a_n$$a_n を

で定さだめることは再帰的定義さいきてきていぎrecursive definitionである。ここで $$a_0$$a_0 を指定していしないと、次つぎを作つくる規則きそくだけでは値あたいが定さだまらない。

再帰的定義さいきてきていぎrecursive definitionでは、次つぎを必かならず確認かくにんする。

• 初期値しょきちが指定していされている。
• 次つぎを作つくる規則きそくが明確めいかくである。
• どの範囲はんいの $$n$$n に対たいして規則きそくを使つかうかが明確めいかくである。

再帰的定義さいきてきていぎrecursive definitionでは、初期値しょきちと再帰規則さいききそくが不足ふそくしていないかを確認かくにんする。同おなじ初期値しょきちと規則きそくから得えられる対象たいしょうが一意いちいであることは、しばしば数学的帰納法すうがくてききのうほうmathematical inductionで示しめせる。

4Recursive definitions

A recursive definition gives initial data and a rule for producing the next object, such as

Specifying $$a_0$$a_0 is necessary; the rule for producing the next term alone does not determine the values.

For a recursive definition再帰的定義さいきてきていぎ, always check the following points.

• Initial values are specified.
• The rule for producing the next object is clear.
• The range of $$n$$n for which the rule is used is clear.

For a recursive definition再帰的定義さいきてきていぎ, check that neither the initial value nor the recursion rule is missing. The fact that the same initial value and rule determine a unique object can often be proved by mathematical induction数学的帰納法すうがくてききのうほう.

5注意ちゅうい

帰納法きのうほうの仮定かていは、すべての $$n$$n について証明しょうめいしたい命題めいだいそのものを一度いちどに仮定かていすることではない。任意にんいの 1 つの $$k$$k について一時的いちじてきに仮定かていし、次つぎの場合ばあいを示しめすためだけに使つかう。

5Warning

The induction hypothesis is not the statement to be proved for all $$n$$n at once. It is a temporary assumption for one arbitrary $$k$$k, used only to prove the next case.

6関連かんれんリンク

6Related links

7まとめ

数学的帰納法すうがくてききのうほうmathematical inductionは、自然数しぜんすう上うえの命題めいだいを扱あつかう基本きほん的てきな証明しょうめい法ほうである。再帰的定義さいきてきていぎrecursive definitionは、有限ゆうげん列れつ、木き、グラフ、計算けいさん手て順じゅんの定義ていぎで頻繁ひんぱんに使つかわれる。

7Summary

Mathematical induction数学的帰納法すうがくてききのうほう is a basic proof method for statements over the natural numbers自然数しぜんすう. Recursive definitions再帰的定義さいきてきていぎ are used frequently when defining finite sequences, trees, graphs, and computational procedures.