<s>[INST] How to prove this sequence of inequalities The number $c_{g}(n)$ is defined by the recurrence
\begin{equation}
c_{g}(n) = c_{g}(n-1)+ (n-1)(n-2)c_{g-1}(n-2) ,
\end{equation}
with $c_{0}(n)=1$ for any $n\geq 1$ and $c_{g}(n)=0$ if $n \leq 2g$.
My question is how to prove the following inequality
\begin{equation}
\frac{c_{g}(n+1)^2}{c_{g}(n) c_{g}(n+2)} \geq \frac{(n+1)(2n+1)}{(n+2)(2n-1)}.
\end{equation}
for any $g\geq 1$.
I have tried to prove it by induction, but failed. 
 [/INST] It is straighforward to prove that:
$$ c_1(n) = 2 \binom{n}{3}. \tag{1}$$
By induction, it follows that $c_g(n)$ is a $3g$-degree polynomial in the variable $n$. In particular:
$$\begin{eqnarray*} c_2(n)-c_2(n-1)&=&2(n-1)(n-2)\binom{n-2}{3}\\&=&8(n-2)\binom{n-1}{4}=40\binom{n}{5}-16\binom{n-1}{4},\end{eqnarray*}$$
$$ c_2(n) = 40\binom{n+1}{6}-16\binom{n}{5} = 40\binom{n}{6}+24\binom{n}{5}. $$
By replacing $(n-1)(n-2)$ with $n(n-1)$ in the functional equation we get that the "main term" in $c_g(n)$ is just 
$$ c_g(n) \sim \frac{(3g)!}{3^g\cdot g!}\binom{n}{3g},\tag{2} $$
and by assuming $c_g(n)=K_g\cdot n^{3g}$ we have:
$$ \frac{c_g(n+1)^2}{c_g(n)c_g(n+2)} = \left(\frac{(n+1)^2}{(n+1)^2-1}\right)^{3g}\geq\left(1+\frac{1}{(n+1)^2}\right)^{3g}\geq 1+\frac{3g}{(n+1)^2}.$$
We have to estimate something that is related with $\frac{d^2}{dx^2}\log c_g(x)$, hence it would be useful to prove that $c_g(n)$ has $3g$ real roots in the interval $[0,2g]$. This may be achieved in the following way:


*

*Prove, by induction, that $c_g(n) = \sum_{h=2g+1}^{3g} K_h \binom{n}{h}$ with $K_h\geq 0$;

*Prove that $c_g(n)$ is strictly increasing when $n\geq 2g$;

*Use Descartes sign rule.


After that, $c_g(n)=K_g \prod_{\rho}(n-\rho)$ and the convexity of $\frac{1}{x^2}$ give:
$$\frac{c_g(n+1)^2}{c_g(n)c_g(n+2)}=\prod_{\rho}\frac{(n+1-\rho)^2}{(n+1-\rho)^2-1}\geq 1+\frac{3g}{(n+1-\frac{1}{3g}\sum_{\rho}\rho)^2}\geq 1+\frac{3g}{(n+1)^2},\tag{3}$$
since $\frac{1}{3g}\sum_{\rho}\rho$ obviously belong to $[0,2g]$ - and may be explicitely computed with a little effort, since it depends only on the coefficients of $n^{3g}$ and $n^{3g-1}$ in $c_g(n)$.
Now we prove $(1.)$ It holds for $g=1$ and $g=2$. Assume that a $K_h\binom{n}{h}$ contributes to $c_{g-1}(n)$. Then:
$$ K_h\left((h+1)(h+2)\binom{n+1}{h+3}-2(h+1)\binom{n}{h+2}\right)$$
contributes to $c_g(n)$, by the same techinique used to find a closed expression for $c_2(n)$. However, 
$$\binom{n+1}{h+3}=\binom{n}{h+3}+\binom{n}{h+2},$$
hence the contribute given to $c_g(n)$ can be written as:
$$ K_h\left((h+1)(h+2)\binom{n}{h+3}+h(h+1)\binom{n}{h+2}\right)\tag{4}$$
and $(1.)$ is proved. By the Descartes' sign rule, now we know that $c_g(n)$ has $3g$ real roots, all positive except one root in zero. The inequality:
$$\frac{c_g(n+1)^2}{c_g(n)c_g(n+2)}\geq 1+\frac{3g}{(n+1)^2}$$
yet follows. Now we notice that $(1.)$ implies $(2.)$, since:
$$ c_g(n) = \sum_{h=2g+1}^{3g}K_h\binom{n}{h} $$
with $K_h>0$, gives that $c_g(n)$ is an increasing function over $n\geq 2g$. Since $K_{3g}=\frac{(3g)!}{3^g\cdot g!}$, we just need to find a closed expression for $K_{3g-1}$ to refine our inequality. By $(4)$, given that:
$$ c_{g-1}(n) = A\binom{n}{3g-3}+B\binom{n}{3g-4}+\ldots, $$
$$ c_g(n) = C\binom{n}{3g}+D\binom{n}{3g-1}+\ldots,$$
we have:
$$ C = (3g-1)(3g-2)A,\qquad D=(3g-3)(3g-2)(A+B), $$
and:
$$ \sum_{\rho}\rho = 3g\left(\frac{3g-1}{2}-\frac{D}{C}\right),\qquad \frac{D}{C}=\frac{3g-3}{3g-1}\left(1+\frac{B}{A}\right),$$
hence we have
$$\frac{1}{3g}\sum_{\rho}\rho > \frac{g}{2}$$
and the final refined inequality:

$$\frac{c_g(n+1)^2}{c_g(n)c_g(n+2)}\geq 1+\frac{3g}{\left(n+1-\frac{1}{2}g\right)^2}.$$

</s>