# How to prove $[u^r](1+u+u^2)^r\leq [u^r](1+u)^k(1+u+u^2)^{r-\frac{k}{2}}$

I need to prove $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}\leq \sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r-\frac{k}{2}}{i}\binom{r+\frac{k}{2}-i}{r-2i}$ for all even k? I tried using the method by https://math.stackexchange.com/users/132007/markus-scheuer in Help me to simplify $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}$. Now What I want to prove is $[u^r](1+u+u^2)^r\leq [u^r](1+u)^k(1+u+u^2)^{r-\frac{k}{2}}$. Please help me to prove this. For k=2 this is simple but I don't know for general k.

• Let $k = 2m$ and write the right hand side as $$(1+u)^{2m}(1+u+u^2)^{r-m} = (1+2u+u^2)^m(1+u+u^2)^{r-m}.$$ – Daniel Fischer Aug 20 '17 at 11:19

Write $k = 2m$ to avoid fractions in exponents. Then
$$(1+u)^{2m}(1 + u + u^2)^{r-m} = (1 + u + u^2)^r + \sum_{j = 1}^m \binom{m}{j} u^j(1 + u + u^2)^{r-j}.$$
Since products of polynomials [or power series] with nonnegative coefficients again have nonnegative coefficients (this fact is so obvious that writing down a correct proof without omitting steps is hard), it follows that all coefficients of $(1+u)^{2m}(1 + u + u^2)^{r-m}$ are at least as large as the corresponding coefficient of $(1 + u + u^2)^r$.