Prove using mathematical induction that $n < 3 ^n$ for all positive integers n.

Question

As title says :

Prove using mathematical induction that $n < 3^n$ for all positive integers $n$.

I came till here

$(k+1)<3^k + 1$

From here I don't have any idea how to show $(k+1)<3^{(k+1)}$ . Please help.

Answer 1

Note that $3^{k+1}=3\cdot 3^k=3^k+3^k+3^k$. Then note that $3^k+3^k>1$ $\forall k$. Thus we conclude that

$$3^{k+1}=3^k+3^k+3^k>3^k+1$$

Answer 2

$3^k +1 < 3^k +3^k +3^k = 3*3^k = 3^{k+1}$

Answer 3

For $n=1$ we have $1\lt3$.

Assume $n\lt3^n$. We need to prove that $(n+1)\lt3^{n+1}$.

$3^{n+1}=3\cdot3^n\gt1+1+3^n\gt1+3^n\gt1+n$

Answer 4

We have for positive numbers that $k\ge 1$ which means that $k+1 \le k+k = 2k$. So your next step would be that given that $k < 3^k$ that $k+1 \le 2k < 2\cdot3^k < 3\cdot 3^k = 3^{k+1}$.

Answer 5

You're nearly there!

When you prove something by induction, after showing the base case ($1<3^1$), you want to assume the statement is true for some integer $k\in\mathbb{Z}^+$. Therefore, we want to start out by saying that for this integer $k$, we know that it is true that $k<3^k$.

We want to prove that $k+1<3^{k+1}$, and it is important in this case to use our assumption that $k<3^k$. You have the correct intuition to take this assumption, and modify it to get closer to what we want to prove. You correctly deduced that

$$k+1<3^k+1.$$

We want to prove that $3^k + 1<3^{k+1}$. It is important to remember that power of integers is just a fancy way of writing repeated multiplication. That is,

$$x^n = x\cdot x\cdot\ldots\cdot x~~\text{(n times)}$$ $$\text{or that }x^n = x^{n-1}\cdot x$$

This tells us that $3^{k+1}$ = $3\cdot3\cdot\ldots\cdot3$ a total of $k+1$ times, which is equal to saying $3^{k+1}=3^k \cdot 3$. Now, how can we represent $3^k\cdot 3$ in a form we can compare to $3^k + 1$? Well, just like exponents, multiplication of integers is just a fancy way of writing repeated addition:

$$n\cdot x = x + x + \ldots + x ~~\text{(n times).}$$

This tells us that $3^k\cdot3 = (3^k + 3^k + 3^k)$. Maybe this form will be easier to work with! Let's return to what we want to prove. Using our new form, we want to show that

$$3^k + 1 < 3^k + 3^k + 3^k.$$

Try and finish the proof yourself from here!