Proof by Induction and Strong Induction
Prove a statement for every natural number by settling a base case and showing each case forces the next. Strong induction assumes all earlier cases when one predecessor is not enough.
What a learner can do afterwards
- Prove a summation formula by induction with the inductive step written out
- Use strong induction where the previous case alone is insufficient
- Diagnose a flawed induction that skips the base case
1 · Read
An induction proof settles a claim for every whole number from some starting point. It has three parts: a base case, an inductive hypothesis, and an inductive step. The hypothesis assumes the claim for some case k so the step can climb to k plus 1. A classic target is the sum 1 plus 2 up to n equals n times n plus 1 over 2. The base case checks n equal to 1, where both sides equal 1.
Assume 1 plus 2 up to k equals k times k plus 1 over 2. Add k plus 1 to both sides. The left side becomes the sum up to k plus 1. The right side becomes k times k plus 1 over 2 plus k plus 1, which simplifies to k plus 1 times k plus 2 over 2. That is exactly the formula with k plus 1 in place of k.
Strong induction assumes every case from the start up to k, not only case k. It is needed when the next case depends on much earlier cases. Every integer above 1 has a prime factor: a composite n splits into factors strictly between 1 and n, far below n minus 1. Mei assumes every integer from 2 up to k has a prime factor, then proves it for k plus 1, which is strong induction.
A proof with a correct step but no checked starting value proves nothing. The step only says the claim passes from k to k plus 1, assuming it holds at k. With no anchor the chain of links hangs on nothing. Dan is wrong to say the step alone is enough: always check the base case first, then write the step so the hypothesis is visibly used.
Anchor the chain with a base case, climb one link with the inductive step, and assume the whole range when one predecessor is not enough.
2 · Watch
Take it off screen
Where it sits
Where this leads
Jobs that lean on this skill. Follow one to see everything it is built on.
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.