# Prove inequality $n<3^n$ using mathematical induction

Prove that $n<3^n$ where $n \in \mathbb N$,

when $n=1$, I have proved it's true.
And assumed when $n = p$ , $p<3^p$ is true.
Can any body help me in showing that it is true for $n =p+1$

-
–  lab bhattacharjee Dec 7 '13 at 14:27
Ya but the correct answer is not selected by the person who have asked the question and in my question it has no power in n. –  Marlon Abeykoon Dec 7 '13 at 14:33
no power? $n=n^1$ –  lab bhattacharjee Dec 7 '13 at 14:35
add comment

## 3 Answers

We have as our inductive hypothesis (IH) that $\,p \lt 3^p$.

So we need to show $$p+1 \lt 3^{p+1} = 3 \cdot 3^p.$$

Can you see that $$p + 1 \quad \overset{IH}{\lt}\quad 3^p + 1 \quad \lt \quad 3\cdot 3^p \;= \;3^{p+1}, \quad \forall p \in \mathbb N$$

-
Nicely done! +1 –  Sami Ben Romdhane Dec 7 '13 at 14:31
Thanks, @Sami! ;-) –  amWhy Dec 7 '13 at 14:31
yes i agree +1 also –  dato datuashvili Dec 7 '13 at 14:35
@dato $-1\notin \mathbb N$! –  amWhy Dec 7 '13 at 15:10
Not necessarily when we are working with inequalities: $3^p + \color{red}{1} \leq 3^p + \color{red}{3^p}$ because $1 \leq 3^p$, and for all $p > 0$, it happens to be true that $1 \lt 3^p$. This allows us then to say that $3^p + 1 \lt 3^p + 3^p \lt 3^p + 3^p + 3^p = 3\cdot 3^p = 3^{p+1}$. Note when $\lt$ is used, and note when $=$ is used. –  amWhy Dec 7 '13 at 15:25
show 8 more comments

If $n < 3^n$ then it follows that $$n+1 <3^n +1 < 3^n +(2\cdot 3^n)=3^{n+1}$$ here I used that $1<2\cdot 3^n$ for all $n\in \Bbb N$.

-
add comment

so we have proved that for $n=1$ ,$1<3$, what would be for $n+1$? we have $(n+1)<3^{n+1}$

which means that $(n+1)<3*3^n$ ,now clearly we have $3^p+1<3*3^p$, but also $3^p+1>p+1$ because we have used such thing that $p<3^p$, finally we conclude that $p+1<3*3^p$.

-
add comment