Prove that $n(n-1)<3^n$ for all $n≥2$ By induction

Question

Prove that $n(n-1)<3^n$ for all $n≥2$. By induction. What I did:

Step 1- Base case: Keep n=2

$2(2-1)<3^2$

$2<9$ Thus it holds.

Step 2- Hypothesis:

Assume: $k(k-1)<3^k$

Step 3- Induction: We wish to prove that:

$(k+1)(k)$<$3^k.3^1$

We know that $k≥2$, so $k+1≥3$

Then $3k<3^k.3^1$

Therefore, $k<3^k$, which is true for all value of $n≥k≥2$

Is that right? Or the method is wrong? Is there any other methods?

Answer 1

We know that $k(k-1)<3^k$ (The induction assumption)

Multiply 3 both sides, and we get:

$3k(k-1)<3^{k + 1}$

Now we will be done if we prove that $k(k+1)\le3k(k - 1)$.

This can be rearranged as $2k - 4 \ge 0$, which is true since $k \ge 2$.

Hence proved.

Answer 2

I think that your solution is fine. However, I would phrase it slightly different.

Step-2. To be completely formal, I would say: Let $k>2$ and assume $k(k-1)<3^k$.

Step 3. We need to show $k(k+1)<3^{k+1}$. We have $$k(k+1)=k(k-1)+2k<3^k+2k<3^k+3^k+3^k=3^{k+1}$$ Where we have used the inductive hypothesis and the fact that $k<3^k$, which is true because $k>2$.

Notice that you can prove that the inequality is true for all $n\geq0$ (indeed the base case will become trivial!).

Answer 3

Other approach (not induction): by the binomial theorem, $$(1+2)^n=1+n.2+\frac12n(n-1).2^2+\frac1{3!}n(n-1)(n-2).2^3\cdots>n(n-1).$$