Find compact formula of the following sum:
$$ \sum_{i,j,k \in \Bbb Z} {{n}\choose{i+j}}{{n}\choose{j+k}}{{n}\choose{k+i}} $$
Could you give me any HINT how to start it?
I've tried this way:
$$ \sum_i \sum_j {{n}\choose{i+j}} \sum_k {{n}\choose{j+k}}{{n}\choose{k+i}}, $$
but I still do not know how to solve this part:
$$\sum_k {{n}\choose{j+k}}{{n}\choose{k+i}} $$
The compact formula for this sum is $$ \sum_{i,j,k \in \Bbb Z} {{n}\choose{i+j}}{{n}\choose{j+k}}{{n}\choose{k+i}} = \frac{1}{2} \left( 8^n + \delta_{n,0} \right) $$ Indeed, let $i+j = m_1$, $i+k = m_2$ and $j+k = m_3$, then $$ i = \frac{1}{2}\left(m_1+m_2-m_3\right), \quad j = \frac{1}{2}\left(m_1-m_2+m_3\right), \quad k = \frac{1}{2}\left(-m_1+m_2+m_3\right) $$ clearly each $m_k$ is an integer, and must be between $0$ and $n$ for binomials to be non zero. The formulas above maps integers $m_k$ into half-integers, so we need to project those out, using $k \mapsto \frac{1}{2} \left( 1 + \cos(2 \pi k)\right) = \Re\left(\frac{1}{2}\left(1+ \mathrm{e}^{i 2 \pi k}\right)\right)$. Thus $$ \sum_{i,j,k \in \Bbb Z} {{n}\choose{i+j}}{{n}\choose{j+k}}{{n}\choose{k+i}} = \frac{1}{8} \Re \sum_{m_1=0}^n \sum_{m_2=0}^n\sum_{m_3=0}^n \binom{n}{m_1} \binom{n}{m_2} \binom{n}{m_3}\cdot \\ \cdot \left(1 + \mathrm{e}^{i \pi(m_1+m_2-m_3)} \right) \left(1 + \mathrm{e}^{i \pi(m_1-m_2+m_3)} \right) \left(1 + \mathrm{e}^{i \pi(-m_1+m_2+m_3)} \right) $$ Now writing out each cosine as a sum of exponentials, and expanding the series we end up with $8$ terms of the form $$ \sum_{m_1=0}^n \sum_{m_2=0}^n\sum_{m_3=0}^n \binom{n}{m_1} \binom{n}{m_2} \binom{n}{m_3} \mathrm{e}^{i \pi (k_1 m_1 + k_2 m_2 + k_3 m_3)} = \left( \left(1+\mathrm{e}^{i \pi k_1} \right) \left(1+\mathrm{e}^{i \pi k_2} \right) \left(1+\mathrm{e}^{i \pi k_3} \right) \right)^n $$ Thus $$ \sum_{i,j,k \in \Bbb Z} {{n}\choose{i+j}}{{n}\choose{j+k}}{{n}\choose{k+i}} = \frac{1}{8} \Re\left( 4 \left(8\right)^n + 4 \delta_{n,0} \right) = \frac{1}{2} \left( 8^n + \delta_{n,0} \right) $$
I use convolution method to get the inner sum,
$$ \sum_k {{n}\choose{j+k}}{{n}\choose{k+i}}=\sum_k\binom{n}{j+k}\binom{n}{n-k-i}$$
First write down the generating function $$ \sum_k\binom{n}{j+k}x^k=\frac{(1+x)^n}{x^j},\textrm{ } \sum_k\binom{n}{-i+k}x^k=(1+x)^nx^i$$ Then the inner sum is the $n$-th coefficient of $ {(1+x)^{2n}}x^{i-j}$, which is $\binom{2n}{j-i+n}$. Then we treat the sum $\sum_i$. $$\sum_i \binom{n}{j+i}\binom{2n}{j-i+n}$$ is the $n$-th coefficient of $(1+x)^nx^{-j}(1+x)^{2n}x^{-j}=(1+x)^{3n}x^{-2j}$, which is $\binom{3n}{n+2j}$. Now $\sum_j$ remains, when $n\geq 1$, $\sum_j \binom{3n}{n+2j} = 2^{3n-1}$.
