Tips on constructing a proof by induction.

Question

So right now I'm working on a discrete mathematics course and I've been having a bit of trouble figuring out how to prove certain equations using mathematical induction. I have very little trouble understanding how to use mathematical induction to prove equations such as this: $1 + 2 ... + n = \dfrac{n(n+1)}2$ for all integers $n \ge 1$. But when it comes to less straightforward proofs such as the one I am currently working on: "Prove that $2n + 1 \le 2^n$ for $n \ge 3$" give me real trouble. Are there any tips for proofs like this any could share? Any help is greatly appreciated.

Answer 1

When proving inequalities by induction it’s often very helpful simply to ask yourself what happens to each side of the proposed inequality when $n$ is increased by $1$.

In this case the expression $2n+1$ on the left increases by $2$ when you replace $n$ by $n+1$, while the expression $2^n$ on the right is multiplied by $2$ when you replace $n$ by $n+1$: instead of adding $2$, you’re adding $2^n$. If $n\ge 1$, then $2^n\ge 2$, and replacing $n$ by $n+1$ adds at least as much to the righthand side as it does to the lefthand side: it adds $2^n$ to the righthand side and $2$ to the lefthand side, and $2^n\ge 2$.

At this point you’ve already essentially done the induction step: you’ve shown that if $2n+1\le 2^n$ and $n\ge 1$, then $2(n+1)+1\le 2^{n+1}$. All that remains is to find the smallest $n\ge 1$ for which $2n+1\le 2^n$, and by actual experiment that turns out to be $n=3$.

Answer 2

For a proof by induction, you need two things. The first is a base case, which is generally the smallest value for which you expect your proposition to hold. Since you are instructed to show that the inequality holds for $n\ge3$, your base case would be $n=3$. This is usually the easy part.

The second part is your inductive step, where you assume that your proposition is true for some $n$ (and you showed in part $1$ that there is such a value) and show that it is also true for $n+1$. So here, if you know that $2n+1\le2^n$, can you show that $2(n+1)+1\le2^{n+1}$? Here, I notice that $2^{n+1}=2\cdot2^n$, so let's start by doubling the original inequality: $2(2n+1)=4n+2\le2\cdot2^n$. Also, since we know (by part of our assumption) that $n\ge3$, we know that $2n+8\le4n+2$, and $2(n+1)+1=2n+3\le2n+8$, so by transitivity we can say that $2(n+1)+1\le2^{n+1}$.

Often, figuring out how to show the $n+1$ case involves a bit of trial and error, as you try to figure out how to simplify or manipulate the equations or inequalities to get what you want. Keep in mind any restrictions on the value of $n$ that are assumed, as these may allow you to take steps that you couldn't in a more general case, as I did with $2n+8\le4n+2$, above.

Answer 3

The inductive hypothesis $2n+1\le2^n$ lets us begin the examination of the next case:

$$2(n+1)+1 = 2n+3=(2n+1)+2\le2^n+2$$

To continue, we note that $2\le2^n$ if $n\ge1$, so we have

$$2^n+2\le2^n+2^n=2^{n+1}$$

and we're done, except for checking for a base case. This is where the $n\ge3$ comes in: $2\cdot3+1=7\le8=2^3$ is true, whereas $2\cdot1+1=3\le2=2^1$ and $2\cdot2+1=5\le4=2^2$ are not.

Note, it might seem that $2\cdot0+1=1\le1=2^0$ means that $n=0$ would work as a base case for the induction. Indeed it would, except for the fact that $2\le2^n$ only holds for $n\ge1$.