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?

Answer 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.

Answer 2

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

1. Assume that the inequality holds for some $n\in\Bbb N$. i.e. $n<3^n$.
2. 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:

1. Assume that the inequality holds for some $n\in\Bbb N$. i.e. $n<3^n$.
2. $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.)
3. You just derived that the inequality also holds for $n+1$. i.e. $(n+1)<3^{n+1}$.
4. Done!

Answer 3

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

Answer 4

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