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

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

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

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) を導みちびく論理ろんりが必要ひつようである。

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が一歩先いっぽさきへ進すすめる規則きそくを与あたえる。有限回ゆうげんかいこの規則きそくを繰くり返かえすことで、任意にんいの自然数しぜんすうに到達とうたつする。

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 と一対一いちたいいちに対応たいおうする。したがって

である。

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

再帰的定義さいきてきていぎrecursive definitionは、基礎きそとなる対象たいしょうと、すでに定義ていぎした対象たいしょうから新あたらしい対象たいしょうを作つくる規則きそくによって全体ぜんたいを定さだめる方法ほうほうである。数列すうれつでは「次つぎの項こう」を作つくり、木きや論理式ろんりしきでは小ちいさい構造こうぞうを組くみ合あわせて大おおきい構造こうぞうを作つくる。

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

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

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

• 基礎きそとなる値あたいや対象たいしょうが指定していされている。
• すでに作つくった対象たいしょうから新あたらしい対象たいしょうを作つくる規則きそくが明確めいかくである。
• 数列すうれつなら $$n$$n の範囲はんい、構造こうぞうならどの構成こうせいを許ゆるすかが明確めいかくである。

再帰的定義さいきてきていぎrecursive definitionでは、基礎きそとなる対象たいしょうと構成規則こうせいきそくが不足ふそくしていないかを確認かくにんする。同おなじ基礎対象きそたいしょうと規則きそくから得えられる対象たいしょうが一意いちいであることは、数列すうれつなら数学的帰納法すうがくてききのうほうmathematical inductionで、木きや論理式ろんりしきならその構成こうせいに沿そう帰納法きのうほうで示しめられる。

5注意ちゅうい

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

6関連かんれんリンク

7演習えんしゅうリンク

8まとめ

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