1

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

1123581321
  • 954
  • 3
    Are you allowed to prove the inequality for $n = 0, 1, 2$ separately, and then start the induction with a base case of $n = 3$? This is a mathematically valid way to prove the statement "$3^n > n \cdot 2^n$ for all non-negative integers $n$". – JimmyK4542 Apr 23 '19 at 04:23
  • I could do that, I'm just wondering why induction doesn't work for $n \geq 0$ in this case, even though the given inequality is true for $n \geq 0$. – 1123581321 Apr 23 '19 at 04:24
  • 3
    @1123581321 Induction often doesn't work with just the base case. A lot of times in order to find which terms of the inductive step to prove manually, you have to actually work with the problem first. In this case you can see your argument requires you to manually compete some more steps. – Melody Apr 23 '19 at 04:26

2 Answers2

3

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

Darius
  • 1,111
2

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

Kyle Miller
  • 19,353