Evaluate: $\sum_{j=0}^{k}\sum_{i=0}^{j}{k \choose j}^2{k \choose i}$ 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$$
 A: 
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.

