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

離散数学りさんすうがく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再帰的定義さいきてきていぎ gives base objects and rules for constructing new objects from ones already built.

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を使つかえる。整列性せいれつせいとは、自然数しぜんすうの空からでない部分集合ぶぶんしゅうごうには最小さいしょうの元げんがあるという性質せいしつである。$$P\left(n\right)$$P(n) が成立せいりつしない $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}{n}_0$$n\ge n_0 の集合しゅうごうが空からでないと仮定かていし、その最小元さいしょうげんを $$m$$m とする。$$P\left(n_0\right)$$P(n_0) は真しんなので $$m>n_0$$m>n_0 であり、$$m-1$$m-1 では $$P(m-1)$$P(m-1) が成立せいりつする。帰納段階きのうだんかいから $$P\left(m\right)$$P(m) も成立せいりつし、$$m$$m の選えらび方かたと矛盾むじゅんする。

基底きてい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.

For a rigorous view, use the well-ordering property整列性せいれつせい: every nonempty subset of the natural numbers has a least element. Suppose the set of $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}{n}_0$$n\ge n_0 for which $$P\left(n\right)$$P(n) fails were nonempty, and let $$m$$m be its least element. Since $$P\left(n_0\right)$$P(n_0) is true, $$m>n_0$$m>n_0. Minimality gives $$P(m-1)$$P(m-1), and the induction step then gives $$P\left(m\right)$$P(m), contradicting the choice of $$m$$m.

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を表あらわす。

$$P\left(n\right)$$P(n) を「任意にんいの $$n$$n 元げん集合しゅうごう $$A$$A について $$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2^n$$|\mathcal P(A)|=2^n」とし、すべての $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}0$$n\ge0 で $$P\left(n\right)$$P(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 の場合ばあいを明示めいじすることが重要じゅうようである。空集合くうしゅうごうは例外れいがいではなく、公式こうしきの出発点しゅっぱつてんである。

帰納段階きのうだんかいとして $$P\left(k\right)$$P(k) を仮定かていし、任意にんいの $$(k+1)$$(k+1) 元げん集合しゅうごう $$A^{\prime }$$A' をとる。$$a\in A^{\prime }$$a\in A' を 1 つ選えらび、$$A=A^{\prime }\setminus \left\{a\right\}$$A=A'\setminus\{a\} とおけば $$\left|A\right|=k$$|A|=k である。$$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

We now use the power sets[べき集合] and cardinality developed in the preceding lectures. Here, $$\left|A\right|$$|A| is the number of elements元げん of $$A$$A, and $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) is the set集合しゅうごう of all subsets部分集合ぶぶんしゅうごう of $$A$$A.

Let $$P\left(n\right)$$P(n) mean “for every set $$A$$A with $$n$$n elements, $$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2^n$$|\mathcal P(A)|=2^n.” We prove $$P\left(n\right)$$P(n) for every $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}0$$n\ge0.

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 $$P\left(k\right)$$P(k) and take an arbitrary set $$A^{\prime }$$A' with $$k+1$$k+1 elements. Choose $$a\in A^{\prime }$$a\in A' and put $$A=A^{\prime }\setminus \left\{a\right\}$$A=A'\setminus\{a\}, so $$\left|A\right|=k$$|A|=k. 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 base objects and rules for constructing new objects from ones already defined. For a sequence this produces a next term; for a tree or logical formula it combines smaller structures into a larger one. For example,

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.

• Base values or base objects are specified.
• Rules for constructing new objects from previously constructed ones are clear.
• For a sequence, the range of $$n$$n is clear; for a structure, the permitted constructors are clear.

For a recursive definition再帰的定義さいきてきていぎ, check that neither the base objects nor the construction rules are missing. Uniqueness from the same bases and rules can be proved by mathematical induction数学的帰納法すうがくてききのうほう for sequences, and by induction following the construction for trees or logical formulas.

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演習えんしゅうリンク

7Exercise links

8まとめ

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

8Summary

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