The sum of $\binom{n}{0}\binom{3n}{2n}-\binom{n}{1}\binom{3n-3}{2n-3}+\binom{n}{2}\binom{3n-6}{2n-6}+\cdots \cdots $

Question

The sum of $$\binom{n}{0}\binom{3n}{2n}-\binom{n}{1}\binom{3n-3}{2n-3}+\binom{n}{2}\binom{3n-6}{2n-6}-\cdots \cdots \cdots $$

$\bf{My\; Try::}$ We can write above sum as $$\sum^{n}_{k=0}(-1)^k\binom{n}{k}\binom{3n-3k}{2n-3k} = \sum^{n}_{k=0}(-1)^k\binom{n}{k}\binom{3n-3k}{n}$$

So sum $$ = \sum^{n}_{k=0}(-1)^k\cdot \frac{n!}{k!\cdot (n-k)!}\times \frac{(3n-2k)!}{n!\cdot (2n-3k)!} = \sum^{n}_{k=0}(-1)^k \cdot \frac{(3n-2k)!}{k!\cdot (n-k)!\cdot (2n-3k)!}$$

Now i did not understand how can i solve it after that , help Required, Thanks

Answer 1

Let's try to see this combinatorially in the form of picking marbles. Suppose you have a $3\times n$ grid of marbles, and you want to choose $2n$ marbles out of them. The number of ways to do so is $$\binom{3n}{2n}=\binom{n}{0}\binom{3n}{2n}.$$ The number of ways to do so with the additional requirement that we choose at least $k$ full rows can be computed as first choosing $k$ rows out of $n$, and then choosing $2n-3k$ marbles out of the remaining $3n-3k$ freely, so this number equals $$\binom{n}{k}\binom{3n-3k}{2n-3k}.$$ We're taking an alternating sum over these terms, which suggests the inclusion-exclusion principle; the alternating sum counts the number of ways to pick $2n$ marbles without picking any full row. The only way to do so is by picking exactly $2$ marbles from each row, and there are $3$ ways to do so for each row. This shows that the alternating sum equals $3^n$.

Answer 2

This also has a very simple algebraic proof. Suppose we seek to evaluate

$$S_n = \sum_{k=0}^n {n\choose k} (-1)^k {3n-3k\choose n}.$$

Introduce

$${3n-3k\choose n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-3k+1}} \frac{1}{(1-z)^{n+1}} \; dz.$$

We get for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} \frac{1}{(1-z)^{n+1}} \sum_{k=0}^n {n\choose k} (-1)^k z^{3k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} \frac{1}{(1-z)^{n+1}} (1-z^3)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} \frac{1}{1-z} (1+z+z^2)^n \; dz.$$

Now residues sum to zero so we have from the poles at zero, one and infinity

$$S_n - 3^n + \mathrm{Res}_{z=\infty} \frac{1}{z^{2n+1}} \frac{1}{1-z} (1+z+z^2)^n = 0.$$

Note that the residue at infinity is

$$-\mathrm{Res}_{z=0} \frac{1}{z^2} z^{2n+1} \frac{1}{1-1/z} (1+1/z+1/z^2)^n \\= -\mathrm{Res}_{z=0} z^{2n} \frac{1}{z-1} (1+1/z+1/z^2)^n \\ = -\mathrm{Res}_{z=0} \frac{1}{z-1} (z^2+z+1)^n = 0.$$

This leaves

$$\bbox[5px,border:2px solid #00A000]{S_n = 3^n.}$$

Answer 3

\begin{align*} &\binom{n}{0}\binom{3n}{2n}-\binom{n}{1}\binom{3n-3}{2n-3}+\binom{n}{2}\binom{3n-6}{2n-6}-\cdots \\ &=\binom{n}{0}\binom{3n}{n}-\binom{n}{1}\binom{3n-3}{n}+\binom{n}{2}\binom{3n-6}{n}-\cdots \end{align*} The right hand side is the coefficient of $x^n$ in \begin{align*} &\binom{n}{0}(1+x)^{3n} - \binom{n}{1}(1+x)^{3n-3} + \cdots \\ &= (1+x)^{3n}\left(1- \frac{1}{(1+x)^3}\right)^n \\ &= (1+x)^{3n-3}(3x+3x^2+x^3)^n \\ &= x^n(1+x)^{3n-3}(3+3x+x^2)^n \end{align*} and hence equals $3^n$.