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

Question

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!

Answer 1

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<l\leq n}\binom{n}{j}\binom{n}{l}(l-j)\tag{15}\\ &=\sum_{q=1}^nq\sum_{j=0}^{n-q}\binom{n}{j}\binom{n}{q+j}\tag{16}\\ &=\sum_{q=0}^nq\sum_{j=0}^{n-q}\binom{n}{j}\binom{n}{n-q-j}\tag{17}\\ &=\sum_{q=0}^nq\binom{2n}{n+q}\tag{18}\\ &=n\sum_{q=0}^n\binom{2n-1}{n+q-1}-n\sum_{q=0}^n\binom{2n-1}{n+q}\tag{19}\\ &=n\binom{2n-1}{n-1}\tag{20}\\ &\,\,\color{blue}{=\frac{n}{2}\binom{2n}{n}}\tag{21} \end{align*}

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<l\leq n$ 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*}