Proof by induction that $2^n+1 \leq 3^n$ for all positive integers $n$

Question

I am having trouble proving the following inequality:

For all positive integers $n$, $2^n+1 \leq 3^n$

The examples we have worked with in class so far have all involved the same integer on both sides of the equation, such as:

For all positive integers $n$, $2^n \leq 2^{n+1}-2^{n-1}-1$

The $3$ in the equation I am trying to prove is throwing me off. Also, I am not sure how to deal with the $+1$ on the left hand side of the inequality.

Answer 1

You assume that $2^k+1\le 3^k$. Then you want to prove that under this assumption, we will have that $2^{k+1}+1\le3^{k+1}$.

$$\begin{align}2^{k+1}+1&=(2\times2^k)+1\\ &=2(2^k+1)-1\\ &=(2^k+1)+(2^k+1)-1\\ &\le 3^k+3^k-1\\ &=3^{k+1}-1-3^k\\ &\le 3^{k+1}\end{align}$$

Answer 2

When $n=1$ it is obviously true.

Suppose $2^k + 1 \le 3^k$ for $n=k$

You want to show that $2^{k+1} + 1 \le 3^{k+1}$

And to see this: $$2^{k+1} + 1 = (2^k+ 1) + (2^k + 1) - 1$$ $$\le (3^k) + (3^k) -1$$ $$\le (3^k) + (3^k) + (3^k)=3^{k+1}$$

Answer 3

You have the following problem : To prove that for all $n \geq 1$ we have $2^n + 1 \leq 3^n$. (Note that the statement is not true for $n=0$).

This is equivalent to the statement that $2^n < 3^n$ for all $n \geq 1$. The rewrite is key, since it resolves the question of what to do with the $1$ that is sticking out. Upon request (although I request you to have a go first) I can provide a reason why the two statements are equivalent.

But from here we can proceed as usual. The base case is $n = 1$, which gives $2 < 3$ which is true.

For the induction case, we know that $2^k < 3^k$, and we want to prove that $2^{k+1} < 3^{k+1}$.

When you have an inequality, then multiplying both sides by a positive number retains inequality.

So, if you know that $2^k < 3^k$, then multiplying both sides by $2$ gives you $2 \times 2^k < 2 \times 3^{k}$, or $2^{k+1} < 2 \times 3^k$.

Next, since $2 < 3$, multiply both sides by $3^k$, to get $2 \times 3^k < 3 \times 3^k$, or $2 \times 3^k < 3^{k+1}$.

Combine the statements above : $2^{k+1} < 2 \times 3^{k} < 3^{k+1}$. Hence, the statement is true for $k+1$, and hence in general.

What you need to take away from this proof is that equivalent rewriting can often simplify statements. If anything, all the others are fairly standard manipulations.