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

  • $\begingroup$ Analysis by substituting gives me $3^n$. Hope someone will prove it. $\endgroup$ – Rohan Dec 25 '16 at 14:48
  • $\begingroup$ Coefficient of $x^{3n}$ in $$(1-x^3)^n\left\{\sum_{r=0}^n(1+x)^{3r}\right\}$$ $\endgroup$ – lab bhattacharjee Dec 25 '16 at 14:50

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

  • $\begingroup$ Brilliant reasoning. Good solution. $\endgroup$ – Rohan Dec 25 '16 at 15:06

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


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


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


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.