How to complete a proof by induction 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?
 A: 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.
A: 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!
A: 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.$$
A: 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$$
