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

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

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

  • $\begingroup$ Yes, great solution. Thanks a lot! $\endgroup$ – JosephConrad Apr 2 '13 at 23:19

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


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.