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.

  • $\begingroup$ 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}.$$ $\endgroup$ – Daniel Fischer Aug 20 '17 at 11:19

Write $k = 2m$ to avoid fractions in exponents. Then

\begin{align} (1 + u)^{2m} &= \bigl((1+u)^2\bigr)^m \\ &= (1+2u + u^2)^m \\ &= \bigl((1+u+u^2) + u\bigr)^m \\ &= (1 + u + u^2)^m + \sum_{j = 1}^m \binom{m}{j} u^j(1 + u + u^2)^{m-j}, \end{align}

and therefore

$$(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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.