mathbase
Learn/induction/Weak vs. Strong Induction

Lesson subsection

Weak vs. Strong Induction

Read the explanation, try the on-paper prompts, then explain the idea in your own words. Use AI feedback as a mentor, not a shortcut.

10–20 min focusProof-first mindset

Best flow: read → think on paper → write a short explanation → refine with feedback.

Reading

Core explanation

There are two common flavors of induction:

  1. Weak (ordinary) induction

    • Assume P(k) is true for some k.
    • Use this to prove P(k + 1) is true.

  2. Strong induction

    • Assume P(j) is true for all integers n₀ ≤ j ≤ k.
    • Use this to prove P(k + 1) is true.

Although strong induction looks stronger, the two forms are logically equivalent.

Strong induction is especially useful when P(k + 1) depends not just on P(k), but on earlier values like P(k - 1), P(k - 2), etc. (e.g., recurrence relations, factorizations, algorithm correctness).

Example (strong induction idea):

Every integer n ≥ 2 can be written as a product of primes.

To show this for n, you assume it holds for all smaller integers and break n into factors.

TL;DR — key idea

Weak induction assumes P(k) to prove P(k + 1); strong induction assumes all previous cases up to k. They are equivalent, but strong is often more convenient.

Try these in your notebook

Don’t skip this – writing proofs or explanations on paper is where most of the learning actually happens.

  • 1

    Explain the difference between the assumptions in weak and strong induction. Then give an example of a situation (even in words) where strong induction feels more natural than weak induction.

Once you’ve sketched some ideas, summarize the main insight in the reflection box on the right.

Check your understanding

In 3–6 sentences, explain the core idea of this subsection as if you were teaching a friend who hasn’t seen it. Focus on the logic, not just the final statements.

AI is optional. Use it to spot gaps and sharpen your wording, not to replace your own thinking.