0
$\begingroup$

In Rosen's book Discrete Mathematics and Its Applications, 8th Edition it is mentioned that:

You may be surprised that mathematical induction and strong induction are equivalent. That is, each can be shown to be a valid proof technique assuming that the other is valid.

One of the examples given for strong induction in the book is the following:

Suppose we can reach the first and second rungs of an infinite ladder, and we know that if we can reach a rung, then we can reach two rungs higher … prove that we can reach every rung using strong induction

If the two proof techniques are "equivalent", how can I prove the above example using mathematical induction (as opposed to strong induction)?

$\endgroup$
1
  • 2
    $\begingroup$ I’m voting to close this question because it is more appropriate for Mathematics. $\endgroup$ Apr 14, 2022 at 9:02

1 Answer 1

1
$\begingroup$

In this case it is simple: Instead of proving "For every n ≥ 0, I can reach rung n on the ladder", you prove "For every n ≥ 0, I can reach rung n on the ladder, plus I can reach rung n-1 if n ≥ 1".

The statement is true for n = 0. The induction step n->n+1 works for n = 0 (because I can reach rungs 0 and 1); for n ≥ 1 I could reach rung n and n-1. Since I can reach rung n-1, I can also reach rung (n-1) + 2 = n+1, therefore I can reach rung n and n+1, so the statement is true for n+1.

$\endgroup$
1
  • 1
    $\begingroup$ There is a general reduction from complete induction to standard induction, which is how you show that the two are equivalent. $\endgroup$ Apr 14, 2022 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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