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.
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.
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$$
$3^k +1 < 3^k +3^k +3^k = 3*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!
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$