# Compact form of sum (binomial coefficients)

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

• Is the sum really over all the integers? – Lord Soth Apr 2 '13 at 18:38
• Yes, I checked twice and it is over all integers. – JosephConrad Apr 2 '13 at 18:39
• Have you tried convolution method? – i707107 Apr 2 '13 at 19:20
• I got $2^{3n-1}$. – i707107 Apr 2 '13 at 19:23
• If you think there are $3n$ balls, and you are going to get even number of balls from them. – Yimin Apr 2 '13 at 21:26

$$\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}$.
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)$$