How to complete a proof by induction

Question

I was trying my hand at proof by induction and got this exercise from the first chapter of Wissam Raji's "An introduction in elementary number theory".

I have to prove by induction that $n< 3^n \forall n \in N$

The basis was trivial, but I don't know if the inductive step is complete. Here is my reasoning

$(n+1) < 3^{(n+1)} \Rightarrow n+1 < 3*3^n \Rightarrow n < 3 * 3^n + 1$

From here I deduce that

$3^n \le 3* 3^n - 1 \Rightarrow 3^n + 1 \le 3*3^n \forall n \in N$

$\Box$

Can this be considered finished? Am I even on the right track?

mathlove · Accepted Answer · 2014-08-05T11:21:27.387

1

Unfortunately, no.

For the $n+1$ step, since you suppose $3^n\gt n$, you'll have $$\begin{align}3^{n+1}-(n+1)&=3\cdot \color{red}{3^n}-(n+1)\\&\gt 3\cdot \color{red}{n}-(n+1)\\&=2n-1\\&\ge 2\cdot 1-1\\&\gt 0.\end{align}$$ I hope this helps.

edited Aug 05 '14 at 11:21

answered Aug 05 '14 at 10:45

mathlove

139,939

I don't understand why $33^n - (n+1) > 3n - (n+1)$ – Federico klez Culloca Aug 05 '14 at 12:16
@FedericoCulloca: We have $3^n\gt n$, right? Then multiplying both sides by $3$ gives you $3\cdot 3^n\gt 3n$. Then substracting $n+1$ from both sides gives you $3\cdot 3^n-(n+1)\gt 3n-(n+1)$. – mathlove Aug 05 '14 at 12:19
@FedericoCulloca: Isn't my comment helpful? – mathlove Aug 05 '14 at 15:07
Yes, but I'm still pondering how we can use an hypotesis to prove the rule. – Federico klez Culloca Aug 05 '14 at 15:40
@FedericoCulloca: The hypothesis is $3^n\gt n$. See the parts colored in red in my answer. I used the hypothesis to prove $3^{n+1}\gt n+1$. So, it means that we can prove that if $3^n\gt n$, then $3^{n+1}\gt n+1$. – mathlove Aug 05 '14 at 15:46
Ok, it seems I have to go back to square one to understand induction better. Thanks for your answer. – Federico klez Culloca Aug 05 '14 at 16:12
@FedericoCulloca: You are welcome! – mathlove Aug 05 '14 at 16:16

score 1 · Answer 2 · answered Aug 05 '14 at 10:46

1

To do the inductive step, what you have to do is

Assume that the inequality holds for some $n\in\Bbb N$. i.e. $n<3^n$.
From this, derive that the inequality also holds for $n+1$. i.e. $(n+1)<3^{n+1}$.

If $n<3^n$, $3^{n+1}=3\cdot3^n>3n=n+2n>n+1$, thus we are done.

In your reasoning, it is not enough to become a 'proof', but it can be a 'preparing before writing down the proof'. To use your reasoning, you can write the proof like this:

Assume that the inequality holds for some $n\in\Bbb N$. i.e. $n<3^n$.
$3^n+1\leq3\cdot3^n \Rightarrow 3^n\leq3\cdot3^n-1 \Rightarrow n<3\cdot3^n-1 \Rightarrow n+1<3\cdot3^n \Rightarrow (n+1)<3^{n+1}$ (This is a reversing of what you did.)
You just derived that the inequality also holds for $n+1$. i.e. $(n+1)<3^{n+1}$.
Done!

answered Aug 05 '14 at 10:46

Jaehyeon Seo

1,873

Where does $3n = n+2n$ come from? – Federico klez Culloca Aug 05 '14 at 12:18
That is obvious. Do you want something like $3n=(2+1)n=2n+n$? – Jaehyeon Seo Aug 05 '14 at 12:34
I wasn't asking about the equivalence per-se, more about where those terms come from. – Federico klez Culloca Aug 05 '14 at 12:37
Sorry, I might misunderstand your comment. But still, I don't know what you want to know(sorry for bad english...). Are you asking about $3\cdot3^n>3n$? – Jaehyeon Seo Aug 05 '14 at 12:42
1

mathlove's comment clarified what I wanted to know, thanks – Federico klez Culloca Aug 05 '14 at 16:13

score 1 · Answer 3 · answered Aug 05 '14 at 10:47

1

IMO you are argumenting backwards and in circles: Your logic flow is $3^{n+1} > n+1 \Longrightarrow\dots$ You should assume $3^n>n$ and get $$3^{n+1}=3\times3^n > 3n= n+ 2n > n+1.$$

answered Aug 05 '14 at 10:47

gammatester

18,827

score 0 · Answer 4 · answered Jun 01 '16 at 01:51

0

You have to prove that : $$3^n+1<3^{n+1}$$ $$3^n<3^{n+1}-1$$ $$3^n<(3-1)\sum_{k=0}^{n}3^{n-k}$$ $$3^n<2\sum_{k=0}^{n}3^{n-k}$$ $$=2\cdot(3^n+3^{n-1}+\cdots+1).\ \ \ \ \Box$$

answered Jun 01 '16 at 01:51

user180321

123

How to complete a proof by induction

4 Answers4