Mathematical Induction

Mathematical induction topples infinitely many statements in one row, like a line of dominoes. First you show that the first domino falls (the claim holds at n = 1), then that if any domino falls the next one falls too (if it holds at n = k, it holds at n = k + 1). Once you confirm just these two things, the claim is guaranteed true for every natural number at once. Here you follow the dominoes toppling in turn to see the two steps of induction for yourself.

Domino Effect — Induction Intuition

Fallen dominoes3

💡 Domino Analogy

①Topple the first domino (n=1 verified)

②If one falls, the next does too (k → k+1)

③These two conditions topple every domino

④This is the heart of mathematical induction!

Structure — 3 Steps

📐 Role of Each Step

①Base: directly verify P(1)

②Hypothesis: assume P(k) holds

③Inductive: use the hypothesis to show P(k+1)

④All three completed ⇒ proof for every natural number

Example: Prove 1+2+...+n = n(n+1)/2

Step 1: n=1

LHS = 1, RHS = 1×22 = 1 ✓

Directly check both sides at n=1

Step 2: assume P(k)

1+2+...+k = k(k+1)2 (hypothesis)

Assume the formula holds at n = k

Step 3: show P(k+1)

1+2+...+k+(k+1) = k(k+1)2 + (k+1) = (k+1)(k+2)2

Use the hypothesis to derive the (k+1) case

✅ Proof complete!

①P(1) verified ✓

②P(k) ⇒ P(k+1) ✓

③Therefore the formula holds for every natural number

Tips for Induction

⚠️ Common Mistakes

①Skipping the base case (n=1) breaks the proof

②Use the precise statement as the hypothesis

③Always invoke the hypothesis when proving P(k+1)

④If you don't use the hypothesis, it's not induction

📐 When to Use Induction

①Identities/inequalities involving n

②Sum formulas

③Divisibility (e.g., 3^n − 1 is even)

④Geometry (sum of angles of n-gon)

Wrap-up

Mathematical Induction

P(1) ∧ [P(k) → P(k+1)] ⟹ ∀n∈ℕ, P(n)

Base + induction step ⇒ holds for all naturals

🎯 Exam Points

①Three-step structure: Base (n=1) → Hypothesis (n=k) → Step (n=k+1)

②Never skip the base

③Always use the hypothesis

④For inequality induction, manipulate LHS at k+1

⑤Sometimes the base is n=2 or higher

Worked Examples & Past Exam

Example 1

When proving 1 + 2 + ... + n = n(n+1)/2 for all natural numbers n by mathematical induction, which step must be checked first?

Induction has two steps: (i) it holds at n=1, and (ii) assuming it holds at n=k, it holds at n=k+1.

(i) check n = 1, (ii) P(k) ⟹ P(k+1)

First, in the base step n=1, check that the left and right sides are equal.

n=1: left = 1, right = 1×22 = 1

▸ Base step: first verify it holds at n = 1.

Without the starting point (n=1), the whole induction collapses.

Example 2

In induction, after assuming the statement holds at n=k, what must you show using that assumption?

Assume the statement holds at n=k (inductive hypothesis).

assume: P(k) holds

Using this as a stepping stone, show it also holds at n=k+1.

to show: P(k+1) holds

▸ Show that it also holds at n = k+1.

You must actually use the hypothesis P(k) to derive P(k+1).

2023 CSAT Math type, adapted

Which two steps of mathematical induction correspond to all the dominoes falling?

①n=1 holds, and P(k) ⟹ P(k+1)

②only n=1 holds

③only P(k) ⟹ P(k+1)

④substitute every n directly

⑤n=2 holds, and P(k) ⟹ P(k−1)

▸ ① n=1 holds, and P(k) ⟹ P(k+1)

The first domino falls = the base step holds at n=1.

(i) holds at n = 1

If the k-th falls then the (k+1)-th falls = the inductive step P(k) ⟹ P(k+1).

(ii) P(k) ⟹ P(k+1)

← Previous

Sum of Series

Recurrence Relations

Was this helpful? Support seegongsik