I found the interesting inequality when I study hypergraph 2-coloring $$\sum_{i+j=k} \binom{r-1}{i}\binom{r-1}{j}(1-p)^i(1+p)^j \leq \binom{2r-2}{k}$$
$0\leq i, j < r$, $0\leq p \leq 1$. I want to know how to proof it.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The left-hand side is the coefficient of $x^k$ in $$ \left(1+(1-p)x\right)^{r-1}\left(1+(1+p)x\right)^{r-1}=\left(1+2x+(1-p^2)x^2\right)^{r-1}\ . $$ This coefficient can be obtained via the Multinomial Theorem as $$ \sum_{a,b}\mathbf{1}\left\{ \begin{array}{c} a,b\ge 0 \\ a+b\le r-1 \\ a+2b=k \end{array} \right\}\frac{(r-1)!}{(r-1-a-b)!a!b!} 2^a (1-p^2)^b $$ where $\mathbf{1}\{\cdots\}$ is the indicator function of the conditions between the braces. Now it is immediate that the left-hand side is a decreasing function of $p$ on the interval $[0,1]$. It is thus bounded above by the value at $p=0$ which is equal to the right-hand side, by the Chu-Vandermonde identity.
answered Jun 2, 2020 at 14:52
-
$\begingroup$ Nice proof. You don't need to extract the coefficient as it is already obvious from the generating function that coefficients can only decrease with $p$. So the whole series is dominated by $(1+2x+x^2)^{r-1} = (1+x)^{2r-2}$. $\endgroup$ Commented Jun 2, 2020 at 15:31
-
$\begingroup$ @BrendanMcKay: Thanks. I know, but I wanted to make this explicit for the sake of pedagogy. $\endgroup$ Commented Jun 2, 2020 at 15:33