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

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

1 Answer 1


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

  • $\begingroup$ 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 $(*)$ $\endgroup$
    – Miros
    Sep 5, 2019 at 21:39
  • $\begingroup$ 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$? $\endgroup$
    – Miros
    Sep 5, 2019 at 21:59
  • 1
    $\begingroup$ @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. $\endgroup$
    – epi163sqrt
    Sep 6, 2019 at 18:56
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 7, 2019 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.