数学的帰納法

ドミノ倒しの仕組み

同様に等比数列の和 $1+r+\cdots+r^n=\frac{r^{n+1}-1}{r-1}\quad(r\ne1)$ も $n=0$ から帰納法で示せます。

最小反例法は、反例のうち最小のものを仮定し、それより小さい場合から矛盾を導く方法で、帰納法と密接に関係します。

Q奇数の和★☆☆

$1+3+\cdots+(2n-1)=n^2$ を $n\ge1$ で証明してください。

HINTヒントを見る

$k$ の式に次の奇数 $2k+1$ を加えます。

ANS解答を見る

$n=1$ で成立します。 $k$ で和が $k^2$ と仮定すると、次の和は $k^2+(2k+1)=(k+1)^2$ です。よって帰納法で成立します。

Q不等式★★☆

$n\ge0$ で $2^n\ge n+1$ を証明してください。

HINTヒントを見る

$2^{k+1}=2\cdot2^k$ と仮定を使います。

ANS解答を見る

$n=0$ では $1\ge1$ 。 $2^k\ge k+1$ と仮定すると $2^{k+1}\ge2(k+1)\ge k+2$ です。最後は $k\ge0$ を使いました。

Q誤った帰納法を見抜く★★★

初期段階を確認せず、 $P(k)\Rightarrow P(k+1)$ だけを示せば十分でしょうか。

HINTヒントを見る

常に偽である命題を考えます。

ANS解答を見る

不十分です。たとえば $P(n):n<0$ を $n\ge0$ で考えると、 $P(k)$ が偽なので含意 $P(k)\Rightarrow P(k+1)$ は空虚に真でも、どの $P(n)$ も真になりません。開始点が必要です。