Proof by induction that $2^n+1 \leq 3^n$ for all positive integers $n$ 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.
 A: 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}$$
A: 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}$$
A: 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.
