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
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.
Write the hypothesis before using it. For the sum proof it says the sum up to k equals k times k plus 1 over 2. Keep that line ready: the next algebra spends it to reach k plus 1.
Test strong induction at n equal to 12. Split 12 as 3 times 4, both strictly between 1 and 12. The hypothesis range 2 to 11 covers both, so each brings its own prime factor.
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.
The rewritten readings were written for this dataset.
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.
14 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.