Proof by Induction and Strong Induction

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.