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!


1 Answer 1


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

Adding the two we find

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

Adding the two we find

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

  • 1
    $\begingroup$ Great and instructive contribution. (+1) I've did some analysis to find an alternate approach but wasn't successful. $\endgroup$ Jun 1, 2021 at 17:15
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 1, 2021 at 17:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .