1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It suffices to show $3^k+1\le3^{k+1}$, possibly using the fact that $3^{k+1}=3\cdot3^k$. $\endgroup$ – Yves Daoust Mar 14 '17 at 11:32
  • $\begingroup$ @YvesDaoust can you please elaborate? It seems everyone is saying something but iam unable to understand. $\endgroup$ – Noddy Mar 14 '17 at 11:36
  • $\begingroup$ I won't do any better than others, I am afraid. $\endgroup$ – Yves Daoust Mar 14 '17 at 11:37
  • $\begingroup$ 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.... $\endgroup$ – Cato Mar 14 '17 at 11:53
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Noddy You're welcome! $\endgroup$ – Bram28 Mar 14 '17 at 13:41
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Noddy; fixed - where's Big Ears? $\endgroup$ – JMP Mar 14 '17 at 11:53
  • $\begingroup$ Thank you very much!, He is fine. $\endgroup$ – Noddy Mar 14 '17 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.