6
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ Can you add how have you came accross this sum? $\endgroup$ – Gabrielek Dec 26 '19 at 10:18
  • 2
    $\begingroup$ 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$. $\endgroup$ – Peter Foreman Dec 26 '19 at 10:23
  • 2
    $\begingroup$ oeis.org/A294435 $\endgroup$ – mathlove Dec 26 '19 at 10:56
  • $\begingroup$ @雄凤山: Interesting post, interesting references. (+1) done yesterday. $\endgroup$ – Markus Scheuer Jan 4 '20 at 9:21
6
$\begingroup$

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

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

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.