# Prove that $\sum _{k=0}^n \left(\sum _{j=0}^k \binom{n}{j}\right)^3=\left(\frac{n}{2}+1\right) 8^n-\frac{3}{4} n 2^n \binom{2 n}{n}$

Define $$S(m,n):=\sum _{k=0}^n \left(\sum _{j=0}^k \binom{n}{j}\right)^m$$

Then $$S(1,n)$$ is trivial and by elementary manipulations $$S(2,n)=\left(\frac{n}{2}+1\right) 4^n-\frac{1}{2} n \binom{2 n}{n}$$.

The first problem: How to prove $$S(3,n)=\left(\frac{n}{2}+1\right) 8^n-\frac{3}{4} n 2^n \binom{2 n}{n}$$ as mentioned by Foreman?

The second problem: Is there a general closed-form for $$S(m,n)$$? According to OEIS the answer is probably no, so a recurrence formula on $$m$$ is also welcomed. Thanks in advance!

• Can you add how have you came accross this sum? – Gabrielek Dec 26 '19 at 10:18
• For $m=3$ we have$$S(3,n)=(n+2)\cdot 2^{3n-1}-3n\cdot 2^{n-2}\cdot\binom{2n}{n}$$A closed form doesn't seem to be known for $m\gt3$. – Peter Foreman Dec 26 '19 at 10:23
• oeis.org/A294435 – mathlove Dec 26 '19 at 10:56
• @雄凤山: Interesting post, interesting references. (+1) done yesterday. – Markus Scheuer Jan 4 '20 at 9:21

Here we follow closely the proof provided in this paper by M. Hirschhorn and show \begin{align*} S(3,n)=\sum_{k=0}^n\left(\sum_{j=0}^k\binom{n}{j}\right)^3=(n+2)2^{3n-1}-3\cdot2^{n-2}n\binom{2n}{n}\tag{1} \end{align*}

We denote with $$A_k=\sum_{j=0}^k\binom{n}{j}$$ and have to show $$S(3,n)=\sum_{k=0}^nA_k^3$$. We need two intermediate results which are interesting by its own and which are shown at the end of this post:

The following is valid for $$0\leq k\leq n-1$$:

\begin{align*} A_k+A_{n-1-k}&=2^n\tag{2}\\ \sum_{k=0}^{n-1}A_kA_{n-1-k}&=\frac{n}{2}\binom{2n}{n}\tag{3} \end{align*}

We obtain \begin{align*} \color{blue}{S(3,n)}&=\sum_{k=0}^nA_k^3\\ &=\frac{1}{2}\sum_{k=0}^{n-1}\left(A_k^3+A_{n-1-k}^3\right)+A_n^3\tag{4}\\ &=\frac{1}{2}\sum_{k=0}^{n-1}\left(A_k+A_{n-k+1}\right)\left(A_k^2-A_kA_{n-1-k}+A_{n-1-k}^2\right)+A_n^3\tag{5}\\ &=\frac{1}{2}\sum_{k=0}^{n-1}2^n\left(A_k^2-A_kA_{n-1-k}+A_{n-1-k}^2\right)+A_n^3\tag{6}\\ &=2^n\sum_{k=0}^{n-1}A_k^2-2^{n-1}\sum_{k=0}^{n-1}A_kA_{n-1-k}+2^nA_n^2\tag{7}\\ &=2^nS(2,n)-n2^{n-2}\binom{2n}{n}\tag{8}\\ &\,\,\color{blue}{=(n+2)2^{3n-1}-3\cdot2^{n-2}n\binom{2n}{n}}\tag{9} \end{align*} and the claim (1) follows.

Comment:

• In (4) we use the symmetry $$\sum_{k=0}^nA_k^3=\sum_{k=0}^{n}A_{n-k}^3$$.

• In (5) we apply $$x^3-y^3=(x-y)\left(x^2-xy+y^2\right)$$.

• In (6) we use the identity from (2).

• In (7) we use again the symmetry as we did in (4).

• In (8) we use the identity from (3) and write $$S(2,n)=\sum_{k=0}^nA_k^2$$.

• In (9) we use the result $$S(2,n)=(n+2)2^{2n-1}-\frac{n}{2}\binom{2n}{n}$$.

Proof of (2):

We have \begin{align*} \color{blue}{A_k+A_{n-1-k}}&=\sum_{j=0}^k\binom{n}{j}+\sum_{j=0}^{n-1-k}\binom{n}{j}\\ &=\sum_{j=0}^k\binom{n}{j}+\sum_{j=0}^{n-1-k}\binom{n}{k+1+k}\tag{10}\\ &=\sum_{j=0}^k\binom{n}{j}+\sum_{j=k+1}^n\binom{n}{j}\tag{11}\\ &\,\,\color{blue}{=2^n} \end{align*} and the claim (2) follows.

Comment:

• In (10) we change the order of summation in the second sum $$j\to n-1-k-j$$ and use the identity $$\binom{p}{q}=\binom{p}{p-q}$$.

• In (11) we shift the index in the second sum to start with $$k+1$$.

Proof of (3):

We have \begin{align*} \color{blue}{\sum_{k=0}^{n-1}}\color{blue}{A_kA_{n-1-k}} &=\sum_{k=0}^{n-1}\sum_{j=0}^k\binom{n}{j}\sum_{l=0}^{n-1-k}\binom{n}{l}\\ &=\sum_{k=0}^{n-1}\sum_{j=0}^k\binom{n}{j}\sum_{l=0}^{n-1-k}\binom{n}{k+1+l}\tag{12}\\ &=\sum_{j=0}^{n-1}\binom{n}{j}\sum_{k=j}^{n-1}\sum_{l=k+1}^{n}\binom{n}{l}\tag{13}\\ &=\sum_{j=0}^{n-1}\binom{n}{j}\sum_{l=j+1}^{n}\binom{n}{l}\sum_{k=j}^{l-1}1\tag{14}\\ &=\sum_{0\leq j

Comment:

• In (12) we change the order of summation $$l\to n-1-k-l$$ and we use the identity $$\binom{p}{q}=\binom{p}{p-q}$$.

• In (13) we exchange the two left-most sums respecting the index region $$0\leq j\leq k\leq n-1$$ and factor out $$\binom{n}{j}$$.

• In (14) we exchange the two right-most sums respecting the index region $$j\leq k and factor out $$\binom{n}{l}$$.

• In (15) we simplify and write the index region somewhat more conveniently.

• In (16) we substitute $$q=l-j$$.

• In (17) we apply the identity $$\binom{p}{q}=\binom{p}{p-q}$$.

• In (18) we apply Vandermonde's identity.

• In (19) we write $$q\binom{2n}{n+q}=(n+q-n)\binom{2n}{n+q}$$ and apply the identity $$\binom{p}{q}=\binom{p-1}{q}+\binom{p-1}{q-1}$$.

• In (20) we use the telescoping property of the sums.

• In (21) we use the identity $$\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$$.

Note: In the cited paper we also find that the reduction from $$S(3,n)$$ to $$S(2,n)$$ in (8) can be generalized to derive a recurrence relation for $$S(m,n)$$. We have for $$m\geq 1$$: \begin{align*} S(2m,n)&=\sum_{k=1}^m(-1)^{k-1}\binom{m}{k}2^{kn}S(2m-k,n)+(-1)^m\sum_{k=0}^{n-1}A_k^mA_{n-1-k}^m\\ S(2m+1,n)&=\sum_{k=1}^m(-1)^{k-1}\binom{m}{k}2^{kn}S(2m+1-k,n)+(-1)^m2^{n-1}\sum_{k=0}^{n-1}A_k^mA_{n-1-k}^m\\ \end{align*}

• @雄凤山: Many thanks for your nice comment. – Markus Scheuer Jan 5 '20 at 6:51