Prove inequality by induction

Question

Once again, I'm stuck in a demonstration by induction, this time, it's really proving that an inequality is valid. So, here is the inequality:

Prove that $\binom{2n}{n} \geq (n+5)^2 \ \forall n \geq 5, n \in \mathbb{N} $

Then, what I wanted to prove is that:

$\binom{2n+2}{n+1} \geq (n+6)^2$

For $n=5$:

$\binom{10}{5} = 252 \geq 100$

The inductive step would be:

$\binom{2n+2}{n+1} \geq (n+6)^2$

$\binom{2n+2}{n+1} = \frac{(2n + 2)(2n+1)(2n)!}{(n+1)(n+1)n!n!} = \frac{2(2n+1)}{n+1}\frac{(2n)!}{n!n!}$

By Inductive Hypothesis, I know that:

$\frac{2(2n+1)}{n+1}\frac{(2n)!}{n!n!} \geq \frac{2(2n+1)}{n+1} (n+5)^2 $

I want to prove, indeed, that:

$\frac{2(2n+1)}{n+1} (n+5)^2 \geq (n+6)^2$

And there I'm stuck. I've tried doing this:

$ 2(2n+1)(n+5)^2) \geq (n+6)^2(n+1) $

$\Rightarrow 4n^3 + 40 n^2 + 120 n + 50 \geq n^3 + 13n^2+38n+36$

$\Rightarrow n(4n^2 + 42n + 120) + 50 \geq n(n^2 + 13n + 38) + 36$

Because $50 \geq 36 \Rightarrow n(4n^2+42n+120) \geq n(n^2+13n+38) $

But they told me here that this inequality is not necessarily true. So.. any ideas how should I follow?

Thanks for your help!

Answer 1

What you have is right, you want to show that if $n \geq 5$, then

$$2(2n+1)(n+5)^2 \geq (n+6)^2(n+1) $$

This can be shown in various ways. For example, if you just expand everything, you get that

$$2(2n+1)(n+5)^2 \geq (n+6)^2(n+1) \Leftrightarrow 3n^3 + 29n^2 + 72n + 14 \geq 0 $$

which is obviously true for the region that we want.

---

Note, what they are telling you, is that just because $50 \geq 36$, does not necessary imply that $2(2n+1)(n+5)^2 \geq (n+6)^2(n+1) $.