# proving an inequality for combinatorial sum

The following inequality comes from the literature: N. Alon, Y. Caro, On the number of subgraphs of prescribed type of planar graphs with a given number of vertices //North-Holland Mathematics Studies. North-Holland, 1984, 87: 25-36. This inequality plays a pivotal role in proving an upper bound on the number of copies of $$K_{1,k}$$ in planar graphs.

If $$\bar{y}=\left(y_1, y_2, \ldots, y_n\right)$$ and $$\bar{z}=\left(z_1, \ldots, z_n\right)$$ are nondecreasing sequences of positive integers, and if there exist $$i$$ and $$j, 1 \leqslant i, such that $$z_i=y_i-1$$, $$z_i=y_i+1$$ and $$z_l=y_l$$, for all $$l \neq i, j$$, then we say that $$\bar{z}$$ is obtained from $$\bar{y}$$ by a simple improvement. It is easily checked that in this case $$\sum_{i=1}^n\left(\begin{array}{l} y_i \\ k \end{array}\right) \leqslant \sum_{i=1}^n\left(\begin{array}{l} z_i \\ k \end{array}\right), \text { for all } k \geqslant 2,$$ and the inequality is strict iff $$y_j \geqslant k-1$$.

The author states that it is easily verifiable, but I haven't yet conceived a rigorous proof for this inequality.

We wish to prove that $$\sum{z_i\choose k}-\sum{y_i\choose k}\ge0$$; by the conditions given this amounts to showing that $${y_j+1\choose k}-{y_j\choose k}+{y_i-1\choose k}-{y_i\choose k}\ge0.$$ Now \begin{align*} {y_j+1\choose k}-{y_j\choose k} &={(y_j+1)\dots(y_j-k+2)\over k!}-{y_j\dots(y_j-k+1)\over k!}\\ &={y_j\dots(y_j-k+2)\over k!}(y_j+1-(y_j-k+1))\\ &={y_j\dots(y_j-k+2)\over(k-1)!}; \end{align*} similarly we have $${y_i-1\choose k}-{y_i\choose k} =-{(y_i-1)\dots(y_i-k+1)\over(k-1)!}.$$ Thus we are left to prove that $$y_j\dots(y_j-k+2)\ge(y_i-1)\dots(y_i-k+1),$$ which follows from the fact that $$y_j\ge y_i$$.
• Sorry. I still don't understand why proving ${y_j+1\choose k}-{y_j\choose k}+{y_i-1\choose k}-{y_i\choose k}\ge0$ is sufficient. Commented Nov 12, 2023 at 13:56
• I see. It is my mistake. I mistakenly interpreted all $l \neq i,j$ with $y_l=z_l$ as the existence of $l$ where $l \neq i,j$ with $y_l=z_l$. Commented Nov 12, 2023 at 13:59