In proving $3^n > n2^n$ by induction for $n \geq 0$, I have so far got:
$3^{n+1} = 3 \times 3^n > 3 (n2^n)$
In order to complete the proof, I have to show that $3n2^n > (n + 1) 2^{n+1}$. But this last inequality is only valid for $n > 2$, even though it should be valid for $n \geq 0$.
Is there a mistake in my proof, or can this inequality not be proven by induction for $n \geq 0$?
On
Just for fun, here's a proof that shows "why" it's true. By dividing both sides through by $2^n$ and using exponentiation laws, the thing to prove is equivalent to showing that $(3/2)^n>n$ for all $n\geq 0$. The "why" is encapsulated in the following lemma (for a big enough number, multiplying by $3/2$ gives a larger result than adding $1$).
Lemma. If $x>2$, then $\frac{3}{2}x>x+1$.
Proof. This is a straightforward algebraic manipulation of the inequality.
Lemma. If $n\geq 2$ is a natural number, then $(3/2)^n>2$.
Proof. For $n=2$, we can check that $(3/2)^2=2+\frac{1}{4}>2$. For $n>2$, we proceed by induction: $(3/2)^n=\frac{3}{2}\cdot (3/2)^{n-1}>\frac{3}{2}\cdot 2>2$, which used the induction hypothesis $(3/2)^{n-1}>2$.
Corollary. If $n\geq 0$ is a natural number, then $(3/2)^n>n$.
Proof. For $n=0,1,2$, we can directly check the inequality is true. For $n>2$ we proceed by induction. Rewrite $(3/2)^n=\frac{3}{2}\cdot (3/2)^{n-1}$. Since $n-1\geq 2$, the second lemma gives $(3/2)^{n-1}>2$. So, with $x=(3/2)^{n-1}$ the first lemma gives $\frac{3}{2}\cdot (3/2)^{n-1} > (3/2)^{n-1}+1$. The induction hypothesis is $(3/2)^{n-1}>n-1$, so $(3/2)^{n-1}+1>(n-1)+1=n$.
Hypothesis: $3^n>n\cdot2^n$
With strong induction,
Base case ($n = 1$):
$3^1 > 1\cdot2^1$
Suppose hypothesis holds for all $n\leq k$ for some $k\in\mathbb{N}$. Then,
$3^{k+1} = 3\cdot3^{k} > 3\cdot k\cdot2^{k} = (1+2)\cdot k\cdot2^{k} = k\cdot2^{k} + k\cdot2^{k+1} = 2^{k+1}\cdot (\frac{k}{2} + k)$
Since we know the base case ($k=1$) is true, we only consider $k\geq2$ and so,
$2^{k+1}\cdot (\frac{k}{2} + k) \geq 2^{k+1}\cdot (\frac{2}{2}+k) = 2^{k+1}\cdot (1+k)$