Showing $\sum_{k=3}^{n} (-1)^{k}{n\choose k}\sum_{j=1}^{k-2}{j(n+1)+k-3\choose n-2}=(-1)^{n-1} \left[\binom{n}{2}-\binom{2n+1}{n-2}\right]$

I would like to prove the following binomial identity $$(*)\quad\quad\sum_{k=3}^{n} (-1)^{k}{n\choose k}\sum_{j=1}^{k-2}{j(n+1)+k-3\choose n-2}=(-1)^{n-1} \left[\binom{n}{2}-\binom{2n+1}{n-2}\right]$$ for every $$n\geq 3$$. Let me say that $$(*)$$ is implied by the following binomial identity $$(**)\quad\quad\quad\quad \sum_{k=0}^{n} (-1)^{k}{n\choose k}F(k)=0$$ which seems holding, for any $$n\geq 0$$, when defining $$F(k):=\sum_{j=1}^{k-2}{j(n+1)+k-3\choose n-2}\quad \text{for k\geq 3}$$ and $$F(2)=0\ ,\quad F(k):=-\sum_{j=k-1}^0{j(n+1)+k-3\choose n-2}\quad \text{for k=0,1}$$ (latest definitions are given coherently with the principle of domain additivity, that is $$\sum_{i=a}^bf(i)+\sum_{i=b+1}^cf(i)=\sum_{i=a}^cf(i)$$, see e.g. the Phira's answer to Upper limit of summation index lower than lower limit?). Anyway, I'm not able to prove identity $$(**)$$, as well!

Notice that $$(**)$$ is equivalent to say that there exist a polynomial $$P(x)$$ of degree $$\deg P\leq n-1$$ such that $$\forall\,k=0,\ldots,n\quad P(k)=F(k)$$
by $$n$$-th finite difference. This fact seems not to be trivial, as the number of monomials of $$F(k)$$ depends on $$k$$, so $$F$$ is not directly a polynomial in $$k$$.

• If we could ping @MarkusScheuer. He has some powerful magic in this area. Sep 2, 2019 at 19:58

We seek to verify that

$$\sum_{k=3}^n (-1)^k {n\choose k} \sum_{j=1}^{k-2} {j(n+1)+k-3\choose n-2} = (-1)^{n-1} \left[ {n\choose 2} - {2n+1\choose n-2} \right].$$

where $$n\ge 3.$$ Now for

$$\sum_{k=3}^n (-1)^k {n\choose k} {k-3\choose n-2}$$

to be non-zero we would need $$k-3\ge n-2$$ or $$k\ge n+1$$, which is not in the range, so it is zero and we may work with

$$\sum_{k=3}^n (-1)^k {n\choose k} \sum_{j=0}^{k-2} {j(n+1)+k-3\choose n-2} \\ = \sum_{k=3}^n (-1)^k {n\choose k} \sum_{j\ge 0} {j(n+1)+k-3\choose n-2} [[0\le j\le k-2]] \\ = \sum_{k=3}^n (-1)^k {n\choose k} \sum_{j\ge 0} {j(n+1)+k-3\choose n-2} \;\underset{z}{\mathrm{res}}\; \frac{1}{z^{k-1}} \frac{z^j}{1-z} \\ = \;\underset{z}{\mathrm{res}}\; \frac{z}{1-z} \sum_{k=3}^n (-1)^k {n\choose k} \frac{1}{z^k} \sum_{j\ge 0} {j(n+1)+k-3\choose n-2} z^j \\ = \;\underset{z}{\mathrm{res}}\; \frac{z}{1-z} \sum_{k=3}^n (-1)^k {n\choose k} \frac{1}{z^k} \sum_{j\ge 0} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} (1+w)^{j(n+1)+k-3} z^j \\ = \;\underset{z}{\mathrm{res}}\; \frac{z}{1-z} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \sum_{k=3}^n (-1)^k {n\choose k} \frac{1}{z^k} (1+w)^{k-3} \sum_{j\ge 0} (1+w)^{j(n+1)} z^j \\ = \;\underset{z}{\mathrm{res}}\; \frac{z}{1-z} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{1-z(1+w)^{n+1}} \sum_{k=3}^n (-1)^k {n\choose k} \frac{1}{z^k} (1+w)^{k-3} \\ = \;\underset{z}{\mathrm{res}}\; \frac{z}{1-z} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{(1+w)^3} \frac{1}{1-z(1+w)^{n+1}} \\ \times \sum_{k=3}^n (-1)^k {n\choose k} \frac{1}{z^k} (1+w)^{k}.$$

We compute this by lowering the index to $$k=0$$ and subtracting the values for $$k=0,1$$ and $$k=2$$ from this completed sum. First (piece $$A$$), extending to $$k=0$$ we find

$$\;\underset{z}{\mathrm{res}}\; \frac{z}{1-z} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{(1+w)^3} \frac{1}{1-z(1+w)^{n+1}} \left(1-\frac{1+w}{z}\right)^n \\ = \;\underset{z}{\mathrm{res}}\; \frac{1}{z^{n}} \frac{z}{1-z} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{(1+w)^3} \frac{1}{1-z(1+w)^{n+1}} (z-1-w)^n.$$

We introduce $$z/(1+w-z) = v$$ so that $$z = v(1+w)/(1+v)$$ and $$dz = (1+w)/(1+v)^2 \; dv$$ as well as $$z/(1-z) = v(1+w)/(1-vw)$$ to get

$$\;\underset{v}{\mathrm{res}}\; \frac{(-1)^n}{v^n} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{(1+w)^3} \frac{v(1+w)}{1-vw} \frac{1}{1-v(1+w)^{n+2}/(1+v)} \frac{1+w}{(1+v)^2} \\ = \;\underset{v}{\mathrm{res}}\; \frac{(-1)^n}{v^{n-1}} \frac{1}{1+v} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{1+w} \frac{1}{1-vw} \frac{1}{1-v((1+w)^{n+2}-1)}.$$

Observe that

$$\frac{1}{1+v} \frac{1}{1-vw} = \frac{1}{1+w} \frac{1}{1+v} + \frac{w}{1+w} \frac{1}{1-vw}.$$

We thus have piece $$A_1:$$

$$\;\underset{v}{\mathrm{res}}\; \frac{(-1)^n}{v^{n-1}} \frac{1}{1+v} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{(1+w)^2} \frac{1}{1-v((1+w)^{n+2}-1)} \\ = \;\underset{w}{\mathrm{res}}\; \frac{(-1)^n}{w^{n-1}} \frac{1}{(1+w)^2} \sum_{q=0}^{n-2} (-1)^{n-2-q} ((1+w)^{n+2}-1)^q \\ = \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{(1+w)^2} \sum_{q=0}^{n-2} (1-(1+w)^{n+2})^q \\ = \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{(1+w)^2} \frac{1-(1-(1+w)^{n+2})^{n-1}}{(1+w)^{n+2}} \\ = [w^{n-2}] \frac{1-(-(n+2)w-\cdots-w^{n+2})^{n-1}}{(1+w)^{n+4}} = (-1)^{n-2} {n-2+n+3\choose n-2} \\ = (-1)^n {2n+1\choose n-2}.$$

We have one correct piece. Continuing with $$A_2$$ (which we conjecture to be zero) we find

$$\;\underset{v}{\mathrm{res}}\; \frac{(-1)^n}{v^{n-1}} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-2}} \frac{1}{(1+w)^2} \frac{1}{1-vw} \frac{1}{1-v((1+w)^{n+2}-1)} \\ = \;\underset{w}{\mathrm{res}}\; \frac{(-1)^n}{w^{n-2}} \frac{1}{(1+w)^2} \sum_{q=0}^{n-2} w^{n-2-q} ((1+w)^{n+2}-1)^q \\ = \;\underset{w}{\mathrm{res}}\; \frac{(-1)^n}{w^{n-2}} \frac{1}{(1+w)^2} \sum_{q=0}^{n-2} w^{n-2-q} ((n+2)w+\cdots+w^{n+2})^q \\ = \;\underset{w}{\mathrm{res}}\; \frac{(-1)^n}{w^{n-2}} \frac{1}{(1+w)^2} \sum_{q=0}^{n-2} ((n+2)^q w^{n-2} +\cdots+w^{(n+1)q+n-2}) \\ = \;\underset{w}{\mathrm{res}}\; \frac{(-1)^n}{(1+w)^2} \sum_{q=0}^{n-2} ((n+2)^q +\cdots+w^{(n+1)q}) = 0.$$

Continuing with the second piece $$B$$ which corresponds to $$k=0$$

$$\;\underset{z}{\mathrm{res}}\; \frac{z}{1-z} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{(1+w)^3} \frac{1}{1-z(1+w)^{n+1}}.$$

This is zero by inspection because there is no pole at $$z=0.$$ More formally,

$$\;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{(1+w)^3} \\ \times \;\underset{z}{\mathrm{res}}\; z ( 1 + z + z^2 + \cdots) (1 + z (1 + w)^{n+1} + z^2 (1+w)^{2n+2}+\cdots) = 0.$$

For the third piece $$C$$ which corresponds to $$k=1$$ we get a factor of $$-n (1+w)/z$$ for

$$-n \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{(1+w)^2} \\ \times \;\underset{z}{\mathrm{res}}\; ( 1 + z + z^2 + \cdots) (1 + z (1 + w)^{n+1} + z^2 (1+w)^{2n+2}+\cdots) = 0.$$

The factor for the fourth piece $$D$$ is $${n\choose 2} (1+w)^2/z^2:$$

$${n\choose 2} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{1+w} \\ \times \;\underset{z}{\mathrm{res}}\; \frac{1}{z} ( 1 + z + z^2 + \cdots) (1 + z (1 + w)^{n+1} + z^2 (1+w)^{2n+2}+\cdots) \\ = {n\choose 2} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n-1}} \frac{1}{1+w} = (-1)^n {n\choose 2}.$$

Subtracting $$B, C$$ and $$D$$ from $$A$$ we finally obtain

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

• Dear Marko,thank you for your interesting and deep answer. I spent some time to understand it in the detail. Given your proof of identity $(*)$ Sep 5, 2019 at 21:39
• Given your proof of identity $(*)$, identity $(**)$ immediately follows. By solving a linear system, it is then possible to exhibiting a polynomial $P$ of degree $n-1$ and satisfying condition $P(k)=F(k)$, for any $0\leq k\leq n$. Viceversa, the existence of $P$ implies both $(*)$ and $(**)$. Exhibiting $P$ seems a purely algebraic task and I would be astonished if the only way to get it should pass through complex analysis... Someone have an algebraic proof of either $(*)$ or the existence of $P$? Sep 5, 2019 at 21:59
• @MarkoRiedel: Great answer. I went through it in a rather detailed way and verified it step by step. I appreciate the elegance how the Iverson brackets are treated and the instructive substitution as well as the creative split into the pieces $A1$ and $A2$. (+1) of course. I found a good motivation for each of the steps besides the creative split. Would you mind to provide your thoughts about it. Sep 6, 2019 at 18:56
• Thank you for the kind remark and for vetting the calculation. At the point where I do the split I did not know yet whether I had the right path. A product of three geometric series turns into two nested sums, while a product of two gives just one sum. So I decided to try the latter and then I discovered I could in fact evaluate the two simple sums. Sep 7, 2019 at 13:45