数学的帰納法（通常・強化・二段仮定）
アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）
要点
帰納法が有効なのは、自然数が1から出発して1ずつ増やすことで全部に到達できる構造を持つから。n=1での成立（出発点）とn=kからn=k+1への伝播、この両方が揃って初めて全ての自然数への一般化が正当化される。示したい命題が弱くて帰納が回らないときは、より強い命題を立てるという逆説的な発想が有効になることがある。
こんなときに使う
- 『すべての自然数nについて』という主張の証明は帰納法を第一候補にする
- 帰納法の仮定だけでは次のステップが示せないときは、命題を強めることを検討する
手順
- 1. n=1（または最小のn）で成立を示す
- 2. n=kで成立すると仮定し、n=k+1でも成立することを示す
- 3. 以上より、すべての自然数nで成立すると結論する
例題
1+2+…+n=n(n+1)/2を帰納法で示せ。
解答
- n=1：左辺1、右辺1で成立。
- n=kで成立と仮定：1+…+k=k(k+1)/2
- 両辺にk+1を加える：1+…+k+(k+1)=k(k+1)/2+(k+1)=(k+1)(k+2)/2
- これはn=k+1のときの右辺と一致。∴ すべてのnで成立
別解・ほかの見方
- 2段仮定（n=k,k+1の両方を仮定してn=k+2を示す）、強化帰納法など
落とし穴
- 出発点（n=1）の確認を省略する
- 仮定を正しく使わずにn=k+1を示そうとする
- 示したい命題が弱すぎて帰納が回らない（強い命題を立てる）
なぜ大事か
整数・不等式・確率すべての論証の締め。仮定を強める発想が差になる
東大での出方
整数・不等式・確率すべての論証の締め。仮定を強める発想が差になる。
確認問題
- すべての自然数nについて3ⁿ≧2ⁿ+1を帰納法で示せ
前提になるノード
このノードを前提にするノード
「数列」のノード
- ①② 等差数列・等比数列
- ③ 階差数列 a(n+1)−a(n)=f(n)
- ④ 和S(n)から一般項を逆算
- ⑤ Σの基本公式（k, k², k³, 等比）
- ⑥ (等差)×(等比)の和：S−rS
- ⑦ 部分分数分解で隣同士を消す
- ⑧ ルートの和は有理化して差の形
- ⑨ 対数の和は log の差に分解して消す
- ㉓ 群数列（項数と末項の通算番号）
- Σ計算・部分分数分解による差の形（望遠鏡和）
- 階差数列・Sとaの関係
- 数学的帰納法（通常・強化・二段仮定）
- 格子点の数え上げ
解説は自作です。誤りに気づいたら お問い合わせ（/contact/）から教えてください。