Simplifying the sum $\sum_{ \substack{i,j,k\geq 0;\\ i+j+2k=r}} (-1)^i {n\choose i}{n \choose j}{n \choose k}$

59 Views Asked by At

We assume that $n,r\in \mathbb{N}$. I've been pondering on this on and off for a few weeks now. Negating the index with $i$ doesn't seem to help.

$$ \sum_{ \substack{i,j,k\geq 0;\\ i+j+2k=r}} {i - 1- n\choose i}{n \choose j}{n \choose k} $$

I also don't see a nice combinatorial argument or a substitution that would help. We can rearrange the constraint to get $i+j+k=r-k$ and look at it as: $$ \sum_{ \substack{i,j,k\geq 0;\\ i+j+k=r-k}} (-1)^i{n\choose i}{n \choose j}{n \choose r-i-j-k} $$ Then maybe we could use something like Cauchy's identity equivalent for trinomials. However I couldn't find or think of such an identity. There's also Vandermonde's identity, also for binomials.

1

There are 1 best solutions below

0
On BEST ANSWER

Write $$\begin{align*}\sum_{r\geq 0} y^r\sum_{i,j,k\geq 0 \\ i+j+2k=r} (-1)^i\binom{n}{i}\binom{n}{j}\binom{n}{k} &= \sum_{i,j,k \geq0} y^{i+j+2k}(-1)^i\binom{n}{i}\binom{n}{j}\binom{n}{k} \\ &= \left(\sum_{i\geq 0}(-y)^i\binom{n}{i}\right)\left(\sum_{j\geq 0}y^j\binom{n}{j}\right)\left(\sum_{k\geq 0}(y^2)^k\binom{n}{k}\right) \\ &= (1-y)^n(1+y)^n(1+y^2)^n \\ &= (1-y^4)^n \\ &= \sum_{m=0}^n (-y^4)^m\binom{n}{m} \\ &= \sum_{m=0}^n y^{4m}(-1)^m\binom{n}{m}\end{align*}$$

We conclude that if $r$ is a multiple of $4$ and $r/4 \leq n$, then the answer is $(-1)^{r/4}\binom{n}{r/4}$. Otherwise, the answer is $0$.