Evaluate: $\sum_{j=0}^{k}\sum_{i=0}^{j}{k \choose j}^2{k \choose i}$

binomial theoremsequences-and-series

Can anybody help me to evaluate this sum $(1)$?

$$\sum_{j=0}^{k}\sum_{i=0}^{j}{k \choose j}^2{k \choose i}\tag1$$

I have manage to figure out:

$$\sum_{j=0}^{k}\sum_{i=0}^{j}{k \choose j}{k \choose i}=\frac{4^k+{2k \choose k}}{2}\tag2$$
and

$$\sum_{j=0}^{k}\sum_{i=0}^{j}{k+1 \choose j+1}^2{k \choose i}=2^k{2k \choose k}\frac{2k+1}{k+1}\tag3$$

Best Answer

We start with \begin{align*} \color{blue}{\sum_{j=0}^k}&\color{blue}{\sum_{i=0}^k\binom{k}{j}^2\binom{k}{i}}\\ &=2^k\sum_{j=0}^k\binom{k}{j}\binom{k}{k-j}\\ &=2^k\sum_{j=0}^k\binom{k}{j}[z^{k-j}](1+z)^k\tag{1}\\ &=2^k[z^k](1+z)^k\sum_{j=0}^k\binom{k}{j}z^j\tag{2}\\ &=2^k[z^k](1+z)^{2k}\\ &\,\,\color{blue}{=2^k\binom{2k}{k}}\tag{3} \end{align*}

Comment:

  • In (1) we use the coefficient of operator $[z^p]$ to denote the coefficient of $z^p$.

  • In (2) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

  • In (3) we select the coefficient of $z^k$.

We obtain from (3)

\begin{align*} \sum_{j=0}^k&\sum_{i=0}^j\binom{k}{j}^2\binom{k}{i}=2^k\binom{2k}{k}-\sum_{j=0}^k\sum_{i=j+1}^k\binom{k}{j}^2\binom{k}{i}\tag{4} \end{align*}

The right-hand sum of (4) gives

\begin{align*} \color{blue}{\sum_{j=0}^k}&\color{blue}{\sum_{i=j+1}^k\binom{k}{j}^2\binom{k}{i}}\\ &=\sum_{j=0}^k\sum_{i=k-j+1}^k\binom{k}{j}^2\binom{k}{i}\tag{5}\\ &=\sum_{j=0}^k\sum_{i=-j+1}^0\binom{k}{j+k}^2\binom{k}{i}\tag{6}\\ &=\sum_{j=0}^k\sum_{i=0}^{j-1}\binom{k}{k-j}^2\binom{k}{i}\tag{7}\\ &=\sum_{j=0}^k\sum_{i=0}^{j-1}\binom{k}{j}^2\binom{k}{i}\\ &\,\,\color{blue}{=\sum_{j=0}^k\sum_{i=0}^j\binom{k}{j}^2\binom{k}{i}-\sum_{j=0}^k\binom{k}{j}^3}\tag{8} \end{align*}

Comment:

  • In (5) we change the order of the outer sum $j\to k-j$.

  • In (6) we shift the index $i$ by $k$.

  • In (7) we replace $i$ with $-i$.

We conclude from (4) and (8)

\begin{align*} \color{blue}{\sum_{j=0}^k\sum_{i=0}^j\binom{k}{j}^2\binom{k}{i}=2^{k-1}\binom{2k}{k}+\frac{1}{2}\sum_{j=0}^k\binom{k}{j}^3} \end{align*}

with $\sum_{j=0}^k\binom{k}{j}^3$ the Franel numbers stored as A000172 in OEIS.

Related Question