I was reading through this paper and noticed a seemingly simple algebraic lemma (Lemma 2 on page 6) for which a proof is not given. I cannot seem to prove the fact myself, so I was hoping to turn to the math commmunity for help.
The lemma is as follows: Let $f(x)$ be a polynomial in $x$ of degree $p$ with non-negative coefficients. Then, for any $x,y \geq 0$, \begin{align*} y \cdot f(x+1) \leq \frac{C_0(p) \cdot y \cdot f(y)}{2} + \frac{x \cdot f(x)}{2} \end{align*} where $C_0(p) = p^{p(1 - o(1))}$.
I don't really understand what this $C_0(p)$ function represents and would appreciate any help in proving this lemma!
I think that the lemma is false.
For $f(x)=x^p,x=0$ and $y=C_0(p)^{-1/p}$, one has $$y \cdot f(x+1)=C_0(p)^{-1/p}\color{red}{\gt}\frac{C_0(p)^{-1/p}}{2}= \frac{C_0(p) \cdot y \cdot f(y)}{2} + \frac{x \cdot f(x)}{2}.$$
There are many counterexamples.
If $f(x)=Ax^p+B,x=0$ and $y\gt 0$ with $A\gt 0$ and $B\geqslant 0$, then $$y \cdot f(x+1) \color{red}{\gt} \frac{C_0(p) \cdot y \cdot f(y)}{2} + \frac{x \cdot f(x)}{2}$$ is equivalent to $$y\lt \bigg(\frac{2A+2B-BC_0(p)}{AC_0(p)}\bigg)^{1/p}.\tag1$$
Here, $2A+2B-BC_0(p)$ has to be positive, and then, every positive real number $y$ satisfying $(1)$ works as a counterexample.
So, one can say that the following is a counterexample :
Added : I'm going to add some observations.
$$y \cdot f(x+1) \le \frac{C_0(p) \cdot y \cdot f(y)}{2} + \frac{x \cdot f(x)}{2}\tag2$$
$f(x)=x+1,x=1,y=4$ is a counterexample. So, it is false that if $f(x)$ is a polynomial in $x$ of degree $p$ with non-negative coefficients, then for any pair of non-negative integers $(x,y)$, $(2)$ holds.
$(2)$ holds for $f(x)=x+1, x=3/2,y=11/2$ where $p=1$. So, it is false that if $f(x)$ is a polynomial in $x$ of degree $p$ with non-negative coefficients and $(2)$ holds, then $x,y$ are non-negative integers.
$(2)$ holds for $f(x)=x+1, x=1,y=5$ where $p=1$.