An Intro to Reverse Induction
Hello world. Welcome to my first blog post.
We have all seen 'vanilla' induction (assuming you studied CS/maths) in undergrad. Provide base case, assume true for all k up to n, then prove for k+1, blah blah.
A while ago, I came across a neat variation on the idea in the book Concrete Mathematics, where you assume true for n, then prove for n-1 (hence 'reverse'). It is best illustrated with an example. The exercise in the book asks us to prove the statement
This of course is the famous AM-GM inequality (which, if you recognised it as such, probably means you are wasting your time reading this :).
In any case, let's (gently) go on with the proof, the mechanics of which are an exercise in algebraic manipulation (although the overall idea is nifty). The inequality is obviously true for n=1. It is also true for n=2, since after some basic manipulation we end up with
We will prove P(n) in two steps, by proving the following two statements:
- P(n) implies P(n-1).
- P(n) and P(2) imply P(2n).
We begin with step 1, by first setting
We want to show that: if P(n) is true, then
is also true. Ok, so assume that P(n) is true. Now, substituting for x_n on the right-hand side of P(n), and multiplying the remaining terms in the sum by (n-1)/(n-1) followed by some simplifying, we get
But remember what our substitution for x_n looks like; we can thus just divide both sides by x_n and we get
which concludes part 1 of the proof!
For the second and final part, we will show that P(n) and P(2) imply P(2n). Well, assume both P(n) and P(2) are true. We want to show that
Now since P(n) holds by assumption, we have
We don't like dealing with roots, so take the nth root of both sides in both these inequalities, multiply them with one another, and we get
What can we do with the right hand side? Well, since P(2) is true, we have
Now, taking our nth-root left-hand side from above, and taking this right hand side, and raising both to the n, we now have
Boom. We have proven the second and final step, which means we have shown P(n), what we originally set out to prove, to be true. QED.
(For those unsure about why this works, think about the two steps of our proof, and what we proved in each step. Now consider our base case of P(2). Since this is true, P(4) is true. But P(n) implies P(n-1), which means that P(3) is also true! Continuing in this manner, we thus cover all integers greater than 0 (i.e. the natural numbers), and our induction is done).
Does anyone have any other examples of reverse induction in action? Do share.