-1
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – arif Jul 13 '15 at 17:19
  • $\begingroup$ 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. $\endgroup$ – marty cohen Jul 13 '15 at 20:26

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.