I have a general question about strong induction:

Assuming that the base case is 0, if I let my inductive hypothesis be that for all 0 <= k < n some statement is true, and if I prove that that statement is true for n, does this mean that I've proved it for all natural numbers?

Some examples do something a little differently: Assuming that for all 0 <= k <= n is true which includes n, they prove it's true for n + 1..are these two equivalent? Or is only the second method valid? Thanks.


They are equivalent. Note that both methods show that assuming the statement is true for $0\le k\le 16$, it is also true for $17$. The first method does this when $n=17$, the other when $n=16$. Since with both methods one shows the induction step for all $n$, the difeerence in notation does not matter.

Note however that the first variant (correctly) allows one to drop the base case: The induction step for $n=0$ shows that, assuming the statement is true for all $k$ with $0\le k<0$ it also holds for $0$; but as $0\le k<0$ is impossible, the assumption is vacuously true, hence the case $n=0$ follows without special considereation. This does not work with the second formulation because to do the same trick, we'd have to use $n=-1$, which we don't want to.

  • $\begingroup$ Thanks for the great explanation! $\endgroup$ – Daniel Cook Oct 25 '13 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.