Thread: Strong Induction.

How do you know when you can apply the induction hypothesis in strong induction??

I understand how to get the base cases.
And then assume that P(n).
Then I understand that I need to prove P(n+1).

What I don't understand is why you are able to apply the induction hypothesis. I know the reason is so that you can augment is to see the truth of P(n+1) but I don't understand when you are able to do so. Thanks

*It would be helpful to show me via example of proving the existence of the "division algorithm," but anything is helpful. Thanks so much

Induction is a way of proving statements of the form "for all natural n, P(n)". To prove it, it is sufficient to prove P(0), called the base case, or basis, and the following statement: "for all natural n, P(n) implies P(n + 1)". The latter fact, called the induction step, is proved in a usual way, by fixing an arbitrary n and assuming P(n); from there one shows P(n + 1).

As I said, there is nothing special about the way one proves the step. In general, one has to know how to prove facts of the form "for all n, Q(n)", "exists n, Q(n)", "R implies S", "R and S", "R or S", etc. Once this is known, showing the induction step is routine. Contrast this with proving the original statement "for all n, P(n)". The usual way of proving it is to fix some n and to show P(n). However, this is often impossible. Here comes induction as a special way of proving this fact.

So the question boils down to, why the base case and the induction step guarantee that "for all n, P(n)" is true. Well, P(0) is shown in the base case. Further, one can instantiate universally quantified n in the induction step to any number. Thus, instantiating n to 0, we get "P(0) implies P(1)". Since P(0) is true, so is P(1). Next, instantiating n to 1 in the induction step, we get "P(1) implies P(2)". Since P(1) is true, so is P(2). Continuing in this way, one can show P(n) for each concrete number n.

The situation you described, when the induction step is "for all n, P(n) implies P(n + 1)" is regular induction. Strong induction has the following induction step: "for all n, P(0) and P(1) and ... and P(n) together imply P(n + 1)".