# Strong induction different assumptions

I have a question regarding strong induction. I've seen examples on proofs that assume that P(n) is true for all n that is smaller or equal than k and thereby dealing with k+1 in the inductive step followed. In some other other case i have seen examples where it is assumed that P(n) is true for all n < k followed by induction proof on the k.

Can someone tell me why this is different and which one is correct approach?

• What's the difference between the two methods you have stated? – shardulc Jul 8 '15 at 11:12
• sorry, ive edited my question, re-read the last part. – arif Jul 8 '15 at 11:23

It varies depending on the problem.

Ordinary induction proves n assuming the truth for n-1.

Mildly strong induction, to prove truth for n, might have to assume the truth for n-1 and n-2.

Somewhat strong induction, to prove truth for n, might have to assume the truth for a fixed number of predecessors n-1, n-2, ..., n-k.

Really strong induction, to prove truth for n, might have to assume the truth for a number of predecessors that depends on n: n-1, n-2, ..., n-k(n).

And finally, for the traditionally strong induction, to prove truth for n, might have to assume the truth for all of its predecessors: n-1, n-2, ..., 2, 1.

It all depends on what you are trying to prove.

• I understand the 4 first versions of induction, but could you write a sentence or two about the last one. I mean, isnt it the same version 3? – arif Jul 13 '15 at 17:19
• For the third one, an example might be using the first $\lceil \sqrt{n} \rceil$ predecessors. I agree that my phrasing is not as precise as it might be. – marty cohen Jul 13 '15 at 20:26