§A3.10数学的帰納法の論理構造

最終更新

数学的帰納法では、基底段階と帰納段階の二つから、なぜすべての自然数についての主張が従うのでしょうか。本記事では、自然数nnについての述語P(n)P(n)を対象として二つの段階の役割を分け、帰納法の原理が自然数の性質に基づくことを最小数原理との関係から確かめ、強い帰納法との違いまで整理します。

1 帰納法の原理

この記事では、自然数は1,2,3,…1, 2, 3, \dotsを指すものとし、00を含めません。00を含める流儀もあり、その場合は以下の基底段階がP(0)P(0)になります。

定理 1.1 (数学的帰納法). 自然数nnについての述語PPが、次の二つを満たすとする。

  1. P(1)P(1)が真である（基底段階）。
  2. すべての自然数kkについてP(k)⇒P(k+1)P(k) \Rightarrow P(k+1)が真である（帰納段階）。

このとき、すべての自然数nnについてP(n)P(n)が真である。

基底段階はn=1n=1という一つの場合についてP(1)P(1)が真であることを示します。帰納段階は、個々のP(k)P(k)が真であることではなく、含意P(k)⇒P(k+1)P(k)\Rightarrow P(k+1)がすべての自然数kkについて真であることを示します。したがって、帰納段階だけでは、真であるP(k)P(k)は一つも保証されません。

二つの段階を合わせると、P(1)P(1)にP(1)⇒P(2)P(1)\Rightarrow P(2)を適用してP(2)P(2)を得ます。さらにP(2)⇒P(3)P(2)\Rightarrow P(3)を適用するとP(3)P(3)を得ます。帰納法の原理は、この出発点と全称的な引継ぎの性質から、すべての自然数nnに対するP(n)P(n)を結論します。

例 1.2 (基底段階を欠く場合).P(n)P(n)を「n=n+1n=n+1」とする。P(k)P(k)、すなわちk=k+1k=k+1を仮定すると、両辺に11を加えてk+1=k+2k+1=k+2を得る。したがって、すべての自然数kkについてP(k)⇒P(k+1)P(k)\Rightarrow P(k+1)は真である。一方、P(1)P(1)は1=21=2という偽の命題である。実際、どの自然数nnについてもP(n)P(n)は偽である。よって、帰納段階が真であっても、基底段階が無ければすべてのP(n)P(n)を結論することはできない。

2 帰納法が成り立つ根拠は、自然数の性質にある

帰納法が正しいことは、論理の規則だけからは出てきません。根拠は、自然数が「11から始まり、11ずつ増え、すべての自然数がこの積み上げによって得られる」という構造をもつことにあります。この構造を公理として書き下したものがペアノの公理であり、帰納法の原理はその一つとして置かれます。

同じ性質を別の形で述べたものが、次の最小数原理です。

定理 2.1 (最小数原理との同値). 自然数について、11が最小であること、11より大きい自然数nnがある自然数mmを用いてn=m+1n=m+1と表されること、および任意の自然数k,nk,nについてk≤n+1k\le n+1かつk≠n+1k\ne n+1ならばk≤nk\le nであることを認める。このとき、数学的帰納法の原理と「自然数からなる空でない集合には最小元がある」という最小数原理は同値である。

定理ブロックに書いた自然数の基本的な性質は、帰納法と最小数原理のどちらからも導かず、両方向の証明で共通に認めます。

証明 (最小数原理から帰納法を導く). 最小数原理を仮定する。自然数nnについての述語PPが定理 1.1 (1)と定理 1.1 (2)を満たすとし、

S={ n∈N≥1∣P(n) は偽 }S=\{\,n\in\NN\mid P(n)\text{ は偽}\,\}

と置く。S≠∅S\ne\varnothingと仮定すると、最小数原理によりSSは最小元n0n_0をもつ。

n0=1n_0=1ならば、n0∈Sn_0\in SによりP(1)P(1)は偽であるが、基底段階によりP(1)P(1)は真である。n0>1n_0>1ならば、n0=m+1n_0=m+1を満たす自然数mmがある。m<n0m<n_0とn0n_0の最小性からm∉Sm\notin S、すなわちP(m)P(m)は真である。帰納段階をk=mk=mに適用するとP(m+1)=P(n0)P(m+1)=P(n_0)は真となり、n0∈Sn_0\in SによってP(n0)P(n_0)が偽であることと両立しない。どちらの場合も仮定S≠∅S\ne\varnothingに反するので、S=∅S=\varnothingである。よって、すべての自然数nnについてP(n)P(n)は真である。▨

証明 (帰納法から最小数原理を導く). 帰納法の原理を仮定する。SSを自然数からなる集合とし、SSは最小元をもたないと仮定する。P(n)P(n)を「11からnnまでのどの自然数もSSに属さない」と定める。

1∈S1\in Sならば、11が最小の自然数であることから11はSSの最小元となる。これはSSが最小元をもたないという仮定に反するので、1∉S1\notin SでありP(1)P(1)は真である。

自然数kkを任意にとり、P(k)P(k)を仮定する。k+1∈Sk+1\in Sと仮定する。k+1k+1より小さい元s∈Ss\in Sがあるならば、s≤k+1s\le k+1かつs≠k+1s\ne k+1であるからs≤ks\le kとなり、P(k)P(k)に反する。したがってSSにk+1k+1より小さい元は存在せず、k+1k+1はSSの最小元となる。これはSSが最小元をもたないという仮定に反するので、k+1∉Sk+1\notin SでありP(k+1)P(k+1)は真である。

定理 1.1により、すべての自然数nnについてP(n)P(n)は真である。したがってS=∅S=\varnothingである。「SSが最小元をもたないならばSSは空集合である」という含意の対偶は、「SSが空でないならばSSは最小元をもつ」である。§A3.6 定理 1.1により、空でない自然数の集合は最小元をもつ。▨

この同値関係から、帰納法と、最小の反例を取る背理法とが同じ内容であることが分かります。「すべてのnnでP(n)P(n)」を示すために、PPが偽になる最小の自然数を取って矛盾を導く議論は、帰納法の別の書き方です。

3 強い帰納法

帰納段階でP(k)P(k)だけを仮定するのではなく、P(1)P(1)からP(k)P(k)までのすべてを仮定してよい形があります。

定理 3.1 (強い帰納法). 自然数nnについての述語PPが、P(1)P(1)が真であり、かつすべての自然数kkについて、P(1),P(2),…,P(k)P(1),P(2),\ldots,P(k)がすべて真であることからP(k+1)P(k+1)が従うとする。このとき、すべての自然数nnについてP(n)P(n)が真である。

証明.Q(k)Q(k)を「1≤j≤k1\le j\le kを満たすすべての自然数jjについてP(j)P(j)が真である」と定める。Q(1)Q(1)はP(1)P(1)と同値であり、仮定により真である。自然数kkを任意にとり、Q(k)Q(k)を仮定する。Q(k)Q(k)からP(1),P(2),…,P(k)P(1),P(2),\ldots,P(k)はすべて真であるので、強い帰納法の帰納段階からP(k+1)P(k+1)が従う。よって、1≤j≤k+11\le j\le k+1を満たすすべての自然数jjについてP(j)P(j)が真であり、Q(k+1)Q(k+1)が成り立つ。定理 1.1をQQに適用すると、すべての自然数kkについてQ(k)Q(k)が真である。したがって、すべての自然数nnについてP(n)P(n)が真である。▨

この証明が示しているとおり、強い帰納法は通常の帰納法から導かれるので、証明することができる主張の範囲は両者で変わりません。強い帰納法では、帰納段階でP(k)P(k)だけでなく、P(1)P(1)からP(k)P(k)までのすべてを使うことができます。

例 3.2 (単純帰納法と強い帰納法の使い分け). 和の公式

1+2+⋯+n=n(n+1)21+2+\cdots+n=\frac{n(n+1)}2

は通常の帰納法で示される。n=1n=1のときは両辺が11である。n=kn=kで公式が成り立つと仮定すると、

1+2+⋯+k+(k+1)=k(k+1)2+(k+1)=(k+1)(k+2)21+2+\cdots+k+(k+1) =\frac{k(k+1)}2+(k+1) =\frac{(k+1)(k+2)}2

となる。P(k+1)P(k+1)を示すためにP(k)P(k)だけを用いるので、通常の帰納法で足りる。

R(j)R(j)を「自然数j+1j+1は素数の積として表される」とする。R(1)R(1)は22が素数であることから真である。R(1),R(2),…,R(k)R(1),R(2),\ldots,R(k)がすべて真であると仮定する。k+2k+2が素数ならばR(k+1)R(k+1)は真である。k+2k+2が合成数ならばk+2=abk+2=ab、2≤a,b≤k+12\le a,b\le k+1を満たす自然数a,ba,bがある。1≤a−1,b−1≤k1\le a-1,b-1\le kであるから、帰納法の仮定によりaaとbbはそれぞれ素数の積として表され、k+2k+2も素数の積として表される。よってR(k+1)R(k+1)は真であり、強い帰納法によりすべての自然数jjについてR(j)R(j)が真である。したがって、22以上のすべての自然数は素数の積として表される。因数a,ba,bは事前に決まらないため、R(k)R(k)だけでなくすべての既知の場合を用いる。

ak+1a_{k+1}がaka_kとak−1a_{k-1}の両方から定まる漸化式について、ak+1a_{k+1}の性質を示すときにaka_kとak−1a_{k-1}の性質をともに用いる場合がある。この場合にはP(k)P(k)とP(k−1)P(k-1)が必要なので、それまでのすべての場合を仮定する強い帰納法を用いることができる。

例題

条件と何を求めるかを確認してから、式と答えの対応を見比べてください。

数学的帰納法の論理構造についての問題である。偽証明にはどこに誤りがあるかを指摘し、構造を問うものにはその論理式や手順を答えよ。

解法の型帰納法が要求するのは P(1) ∧\land∀k\forall k (P(k) ⇒\Rightarrow P(k+1)) の両方。基底が偽ならステップが正しくても何も従わず、ステップがある k で破れれば連鎖はそこで切れる

  1. 次は数学的帰納法による「証明」だが、誤りがある。どこが誤りかを指摘せよ。

    主張: すべての自然数 n について n=n+1 。「証明」: P(k) すなわち k=k+1 を仮定する。両辺に 1 を足すとk+1=k+2 、これは P(k+1) である。よって帰納法よりすべての n で成立。\begin{array}{l} \text{主張: すべての自然数 } n \ \text{について } n = n + 1 \ \text{。} \\ \text{「証明」: } P(k) \ \text{すなわち } k = k + 1 \ \text{を仮定する。両辺に } 1 \ \text{を足すと} \\ \quad k + 1 = k + 2 \ \text{、これは } P(k+1) \ \text{である。よって帰納法よりすべての } n \ \text{で成立。} \end{array}

  2. 次は数学的帰納法による「証明」だが、誤りがある。どこが誤りかを指摘せよ。

    数列 a1=1, a2=3, an+2=an+1+an について an<2n を示したい。「証明」: P(k) すなわち ak<2k を仮定すると ak+1=ak+ak−1<2k+ak−1 。\begin{array}{l} \text{数列 } a_1 = 1, \ a_2 = 3, \ a_{n+2} = a_{n+1} + a_n \ \text{について } a_n < 2^n \ \text{を示したい。} \\ \text{「証明」: } P(k) \ \text{すなわち } a_k < 2^k \ \text{を仮定すると } a_{k+1} = a_k + a_{k-1} < 2^k + a_{k-1} \ \text{。} \end{array}

  3. 数学的帰納法の論理構造について、次の問いに答えよ。

    「すべての自然数 n について P(n)」の否定を書き、最小反例法の第一歩を述べよ。\text{「すべての自然数 } n \ \text{について } P(n) \text{」の否定を書き、最小反例法の第一歩を述べよ。}

  4. 数学的帰納法の論理構造について、次の問いに答えよ。

    強い帰納法の帰納ステップを論理式で書き、通常の帰納法との違いを述べよ。\text{強い帰納法の帰納ステップを論理式で書き、通常の帰納法との違いを述べよ。}

  5. 次は数学的帰納法による「証明」だが、誤りがある。どこが誤りかを指摘せよ。

    主張: すべての自然数 n について 1+2+⋯+n=n2+n+22 。「証明」: n=k で成立を仮定すると1+⋯+k+(k+1)=k2+k+22+(k+1)=k2+3k+42=(k+1)2+(k+1)+22となり P(k+1) が従う。\begin{array}{l} \text{主張: すべての自然数 } n \ \text{について } 1 + 2 + \cdots + n = \dfrac{n^2 + n + 2}{2} \ \text{。} \\ \text{「証明」: } n = k \ \text{で成立を仮定すると} \\ \quad 1 + \cdots + k + (k+1) = \dfrac{k^2 + k + 2}{2} + (k+1) = \dfrac{k^2 + 3k + 4}{2} = \dfrac{(k+1)^2 + (k+1) + 2}{2} \\ \quad \text{となり } P(k+1) \ \text{が従う。} \end{array}

  6. 次は数学的帰納法による「証明」だが、誤りがある。どこが誤りかを指摘せよ。

    ある学生の主張: 「帰納法の仮定で P(k) を仮定してよいのだから、P(k) はすでに真だと分かっている。よって帰納ステップでは P(k) を証明したことになる。」\begin{array}{l} \text{ある学生の主張: 「帰納法の仮定で } P(k) \ \text{を仮定してよいのだから、} \\ \quad P(k) \ \text{はすでに真だと分かっている。よって帰納ステップでは } P(k) \ \text{を証明したことになる。」} \end{array}

  7. 数学的帰納法の論理構造について、次の問いに答えよ。

    「すべての自然数 n について P(n)」を数学的帰納法で示すとき、示すべき2つの命題を論理式で書け。\text{「すべての自然数 } n \ \text{について } P(n) \text{」を数学的帰納法で示すとき、示すべき2つの命題を論理式で書け。}

  8. 次は数学的帰納法による「証明」だが、誤りがある。どこが誤りかを指摘せよ。

    主張: 2 以上のすべての整数は素因数分解をもつ。「証明」: P(k) （k が素因数分解をもつ）を仮定して P(k+1) を示す。k+1 が素数なら明らか。合成数なら k+1=ab (1<a≤b<k+1) と書けるので、仮定より a,b の分解を掛ければよい。\begin{array}{l} \text{主張: } 2 \ \text{以上のすべての整数は素因数分解をもつ。} \\ \text{「証明」: } P(k) \ \text{（} k \ \text{が素因数分解をもつ）を仮定して } P(k+1) \ \text{を示す。} \\ \quad k+1 \ \text{が素数なら明らか。合成数なら } k+1 = ab \ (1 < a \le b < k+1) \ \text{と書けるので、} \\ \quad \text{仮定より } a, b \ \text{の分解を掛ければよい。} \end{array}

  9. 数学的帰納法の論理構造について、次の問いに答えよ。

    最小数原理（自然数の空でない部分集合には最小元がある）から数学的帰納法を導くとき、どんな集合の最小元を取るか。\text{最小数原理（自然数の空でない部分集合には最小元がある）から数学的帰納法を導くとき、どんな集合の最小元を取るか。}

  10. 次は数学的帰納法による「証明」だが、誤りがある。どこが誤りかを指摘せよ。

    主張: どんな n 頭の馬の集まりも、すべて同じ色である。「証明」: n=1 では明らか。n=k で成立を仮定し、k+1 頭を考える。最初の k 頭は同じ色、最後の k 頭も同じ色。重なりの馬を通じてすべて同じ色。よって k+1 頭も同じ色。\begin{array}{l} \text{主張: どんな } n \ \text{頭の馬の集まりも、すべて同じ色である。} \\ \text{「証明」: } n = 1 \ \text{では明らか。} n = k \ \text{で成立を仮定し、} k+1 \ \text{頭を考える。} \\ \quad \text{最初の } k \ \text{頭は同じ色、最後の } k \ \text{頭も同じ色。重なりの馬を通じて} \\ \quad \text{すべて同じ色。よって } k+1 \ \text{頭も同じ色。} \end{array}

演習

問題を解いてから「解答・解説」を開けます。

数学的帰納法の論理構造についての問題である。偽証明にはどこに誤りがあるかを指摘し、構造を問うものにはその論理式や手順を答えよ。

演習を読み込み中…

前提記事