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.
Asked
Active
Viewed 47 times
1
-
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
1 Answers
2
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$.
Daniel Fischer
- 206,697