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