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

答 誤り:$k = 1$のとき（$1$頭から$2$頭へのステップ）、最初の$1$頭と最後の$1$頭は重ならず、色を橋渡しできない。

注意 有名な偽証明。帰納ステップの議論は「最初の k 頭」と「最後の k 頭」に共通の馬がいることを暗に使っているが、それが成り立つのは k$\ge$2 のときだけ。k$=$1 のとき 2 頭は互いに素な2つの1頭集合になり、色が結び付かない。基底 n$=$1 は正しく、ステップも k$\ge$2 では正しいのに、ちょうど 1$\to$2 の一箇所だけ切れているため連鎖が始まらない。帰納ステップは「すべての k」で成り立つことを確認しなければならない。▨

答

注意 帰納法は P(1) と$\forall k$(P(k)$\Rightarrow$P(k+1)) の両輪で成り立つ。片方だけでは何も言えない。ドミノの比喩でいえば、基底は「最初の1枚を倒すこと」、ステップは「隣へ倒れる仕組み」。どちらが欠けても全部は倒れない。▨

答 誤り: 仮定しているのは$P(k)$だけなのに、$k$とは限らない$a, b \ (a, b < k+1)$について$P(a), P(b)$を使っている。強い帰納法が必要。

注意 通常の帰納法の仮定は「直前の P(k)」しか与えない。しかし k+1$=$ab の a, b は k より小さい任意の数であって、k とは限らない。正しくは強い帰納法（P(2)$\land$…$\land$P(k) をすべて仮定して P(k+1) を示す）を使う。「直前だけでは足りず、それまで全部を使いたい」場面が強い帰納法の出番。なお強い帰納法は通常の帰納法と論理的な強さは同じ（Q(k)$=$P(2)$\land$…$\land$P(k) に通常の帰納法を適用すればよい）。▨

答 誤り:$a_{k-1} < 2^{k-1}$を使いたいのに、仮定は$P(k)$だけで$P(k-1)$を与えない。強い帰納法（または$P(k) \land P(k+1)$を命題に取る）が必要。

注意 漸化式が2つ前まで遡るとき、通常の帰納法の仮定（直前の1つだけ）では足りない。強い帰納法を使うか、示す命題を Q(n)$=$「P(n) かつ P(n+1)」と組にして通常の帰納法を回す。どちらも同じことで、要は「ステップで実際に使う仮定を、仮定として宣言しておく」ことが大切。▨

答$P(1) \ \land \ \forall k \ \bigl(P(k) \Rightarrow P(k+1)\bigr)$

注意 基底 P(1) と、帰納ステップ$\forall k$(P(k)$\Rightarrow$P(k+1))。この2つから$\forall n$P(n) が従う、というのが帰納法の原理。無限個の主張$\forall n$P(n) が、2つの有限な確認に還元されるのが要点。どちらか一方だけでは何も従わない。▨

答$S = \{ n \mid P(n)$が偽$\}$（反例の集合）の最小元$n_0$を取る。

注意 基底 P(1) と帰納ステップを仮定して S$\ne$∅ とすると、最小数原理より S に最小元$n_{0}$がある。$n_{0} =$1 なら基底に矛盾。$n_{0}$> 1 なら最小性から$P(n_{0}$− 1) は真、帰納ステップより$P(n_{0})$も真となり$n_{0} \in$S に矛盾。よって S$=$∅、すなわち$\forall n$P(n)。帰納法と「最小の反例を取る背理法」が地続きであることが見える。▨

答 誤り: 基底が偽。$n = 1$で左辺は$1$、右辺は$\dfrac{1 + 1 + 2}{2} = 2$で一致しない。

注意 帰納ステップの計算は完全に正しい（実際 (k²+3k+4)/2$=$((k+1)²+(k+1)+2)/2）。それでも主張は偽である。正しい公式は n(n+1)/2 で、この式は常に 1 だけ大きい。「ステップが通る」ことと「主張が真」は別物で、基底が偽なら連鎖は始まらない。ステップだけ検算して安心するのは危険。▨

答$\forall k \ \Bigl( \bigl(P(1) \land P(2) \land \cdots \land P(k)\bigr) \Rightarrow P(k+1) \Bigr)$

注意 通常の帰納法が仮定するのは直前の P(k) だけだが、強い帰納法は P(1) から P(k) までを全部仮定してよい。仮定が強いぶん使いやすく、素因数分解の存在や2つ前まで遡る漸化式で必要になる。論理的な強さは通常の帰納法と同じで、Q(k)$=$P(1)$\land$…$\land$P(k) に通常の帰納法を適用すれば導ける。▨

答 誤り: 帰納ステップで示すのは含意$P(k) \Rightarrow P(k+1)$であって、$P(k)$そのものではない。

注意 帰納ステップは「もし P(k) が真なら P(k+1) も真」という含意を示す作業であり、P(k) が実際に真だと主張しているのではない。P(k) が真であることは、基底 P(1) から含意を k−1 回たどってはじめて言える。含意を示す、という構造を取り違えると「示すべきことを仮定している（論点先取）」という誤解に陥る。▨

答 誤り: 基底ケース$P(1) \ (1 = 2)$を確認していない（実際に偽）。帰納ステップだけでは何も従わない。

注意 帰納ステップ「P(k)$\Rightarrow$P(k+1)」自体はこの偽証明でも正しく示されている。しかし帰納法が要求するのは P(1)$\land \forall k$(P(k)$\Rightarrow$P(k+1)) の両方。最初の1枚が倒れていなければ、ドミノがどれだけ連鎖する仕組みでも1枚も倒れない。基底の確認は飾りではない。▨

答 誤り: 最後の不等式$2k^2 \ge (k+1)^2$は$k \ge 3$でしか成り立たない（$k = 1, 2$で破れる）。実際$n = 2, 3, 4$で主張は偽。

注意 基底 n$=$1 は正しく、ステップの式変形も k$\ge$3 では正しい。しかし k$=$1, 2 でステップが破れるので、n$=$1 からの連鎖がそこで切れる。実際 2²$=$4 > 4 は偽、2³$=$8 > 9 は偽、$2^{4} =$16 > 16 も偽。正しい主張は「n$\ge$5 で 2ⁿ > n²」で、基底を n$=$5（32 > 25）に置けばステップ（k$\ge$5$\ge$3）が常に通り、証明が完成する。ステップが成り立つ範囲と基底の位置を合わせること。▨

答$\lnot \forall n \ P(n) \ \equiv \ \exists n \ \lnot P(n)$。この$n$たちの中から最小の$n_0$を取る。

注意 全称の否定は存在。反例が存在するなら、最小数原理により最小の反例$n_{0}$が取れる。この$n_{0}$について「$n_{0}$より小さいところでは P が成り立つ」という強い情報が無料で手に入るのが最小反例法の旨み。これは強い帰納法の言い換えでもある。▨