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

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.

• It suffices to show $3^k+1\le3^{k+1}$, possibly using the fact that $3^{k+1}=3\cdot3^k$. – Yves Daoust Mar 14 '17 at 11:32
• @YvesDaoust can you please elaborate? It seems everyone is saying something but iam unable to understand. – Noddy Mar 14 '17 at 11:36
• I won't do any better than others, I am afraid. – Yves Daoust Mar 14 '17 at 11:37
• start at n=1 (the lowest positive integer) then $1 < 3^1$ then consider any case where $n < 3^n$ will $n + 1 < 3^{n+1}$ be true? $3^{n+1} - 3^n = 3^n(3 - 1}$ so the RHS has to increase by more than the increase of 1 on the LHS - so it will be true, if it is true for 1, it will be true for 2,3,4,5.... – Cato Mar 14 '17 at 11:53

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$$

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!

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

• @Noddy You're welcome! – Bram28 Mar 14 '17 at 13:41

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}$.

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$

• @Noddy; fixed - where's Big Ears? – JMP Mar 14 '17 at 11:53
• Thank you very much!, He is fine. – Noddy Mar 14 '17 at 12:07