# Binomial coefficients identity with cases

Let $$i,j,k$$ be non-negative integers such that $$i$$ is even, $$j \leq \frac{i}{2}$$, and $$k < i$$. I would like to show the following identity: $$\binom{i-j+k}{k} - \sum_{\ell = 0}^{\lfloor\frac{k}{2}\rfloor} \frac{i-2j+k}{\frac{i}{2}-j+k-\ell} \binom{\frac{i}{2}+\ell}{2\ell} \binom{\frac{i}{2}-j+k-\ell}{k-2\ell} = \begin{cases} 0 & \text{if }j < k \\ (-1)^{k+1}\binom{j}{k} & \text{if } j \geq k \end{cases}.$$

We can change the summation into $$\sum_{\ell=0}^{\lfloor\frac{k}{2}\rfloor}\binom{\frac{i}{2} + \ell}{2\ell}\left(\binom{\frac{i}{2}-j+k-\ell}{k-2\ell} + \binom{\frac{i}{2}-j+k-\ell-1}{k-2\ell} \right)$$ but I don't know of any identities that could help here. I've also tried induction on $$k$$, but couldn't see a good way for the induction hypothesis to be used. I would appreciate any ideas!

In seeking to evaluate

$${q-j+k\choose k} - \sum_{\ell=0}^{\lfloor k/2 \rfloor} {q/2+\ell\choose 2\ell} \left({q/2-j+k-\ell\choose k-2\ell} + {q/2-j+k-\ell-1\choose k-2\ell} \right)$$

We get for the first piece of the sum

$$\sum_{\ell=0}^{\lfloor k/2 \rfloor} {q/2+\ell\choose 2\ell} {q/2-j+k-\ell\choose k-2\ell} \\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{1}{z^{k+1}} (1+z)^{q/2-j+k} \sum_{\ell=0}^{\lfloor k/2 \rfloor} {q/2+\ell\choose 2\ell} \frac{z^{2\ell}}{(1+z)^\ell} \; dz.$$

Now here the residue vanishes when $$2\ell \gt k$$ so it enforces the upper limit of the sum and we obtain

$$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{q/2-j+k}}{z^{k+1}} \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{q/2}}{w} \sum_{\ell\ge 0} \frac{z^{2\ell}}{(1+z)^\ell} \frac{(1+w)^\ell}{w^{2\ell}} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{q/2-j+k}}{z^{k+1}} \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{q/2}}{w} \frac{1}{1-z^2(1+w)/(1+z)/w^2} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{q/2-j+k+1}}{z^{k+1}} \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} (1+w)^{q/2} \frac{w}{(w-z)(w(1+z)+z)} \; dw \; dz.$$

The pole at $$w=0$$ has been canceled. Now observe that for the geometric series to converge we must have $$|z^2(1+w)/w^2/(1+z)|\lt 1.$$ We will choose a contour that includes both simple poles. The first pole is at $$-z/(1+z).$$ We thus require $$|z/(1+z)| \lt \gamma.$$ With $$|z/(1+z)| \le \varepsilon/(1-\varepsilon)$$ we get $$\varepsilon/(1-\varepsilon) \lt \gamma$$ and we furthermore need $$|z^2/(1+z)| \lt |w^2/(1+w)|.$$ The latter holds if $$\varepsilon^2 / (1-\varepsilon) \lt \gamma^2/(1+\gamma).$$ Both hold if $$\varepsilon \gamma \lt \gamma^2/(1+\gamma)$$ or $$\varepsilon \lt \gamma/(1+\gamma).$$ So $$\varepsilon = \gamma^2/(1+\gamma)$$ will work. Observe that this contour also includes the pole at $$w=z.$$

First pole. Now to extract the residue at $$w=-z/(1+z)$$ we write

$$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{q/2-j+k}}{z^{k+1}} \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} (1+w)^{q/2} \frac{w}{(w-z)(w+z/(1+z))} \; dw \; dz$$

and obtain

$$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{q/2-j+k}}{z^{k+1}} (1+z)^{-q/2} \frac{-z/(1+z)}{-z/(1+z)-z} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{k-j}}{z^{k+1}} \frac{1}{z+2} \; dz.$$

Repeating for the second sum we get

$$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{k-j-1}}{z^{k+1}} \frac{1}{z+2} \; dz.$$

$$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{k-j-1} (1+(1+z))}{z^{k+1}} \frac{1}{z+2} \; dz = {k-j-1\choose k}.$$

Second pole. For the residue at $$w=z$$ we obtain for the first sum

$$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{q/2-j+k+1}}{z^{k+1}} (1+z)^{q/2} \frac{z}{(z(1+z)+z)} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{q-j+k+1}}{z^{k+1}} \frac{1}{z+2} \; dz.$$

Repeating for the second sum we get

$$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{q-j+k}}{z^{k+1}} \frac{1}{z+2} \; dz.$$

$$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{q-j+k}(1+(1+z))}{z^{k+1}} \frac{1}{z+2} \; dz = {q-j+k\choose k}.$$

Conclusion. Collecting everything we obtain

$${q-j+k\choose k} - {q-j+k\choose k} - {k-j-1\choose k}.$$

This is $$- (k-j-1)^{\underline{k}}/k!.$$ Now if $$0\le j\lt k$$ this is indeed zero because the falling factorial hits the zero value. If $$j\ge k$$ all $$k$$ terms are negative and we get $$-(-j)^{\overline{k}}/k!.$$

We have at last

$$\bbox[5px,border:2px solid #00A000]{ (-1)^{k+1} {j\choose k}.}$$

as claimed.

Remark. The potential square roots that appeared in the above all use the principal branch of the logarithm with branch cut $$(-\infty, -1]$$ which means everything is analytic in a neighborhood of zero as required.

• Great and instructive contribution. (+1) I've did some analysis to find an alternate approach but wasn't successful. Jun 1, 2021 at 17:15
• @MarkusScheuer It is an honor, thank you very much for looking into it. The factorization of the geometric series is what makes this problem so special. Jun 1, 2021 at 17:20