Binomial theorem / Generating function

Question

I had trouble figuring out if the following equality holds by applying the binomial theorem and using generating functions. Could anyone please shed some light? Any help is greatly appreciated.

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

Answer 1

Here's another variation of the theme using Egorychevs formal residual calculus for power series.

Note: This powerful technique is based upon Cauchys residue theorem and was introduced by G.P. Egorychev (Integral Representation and the Computation of Combinatorial Sums) to compute binomial identies.

We use only two aspects of this theory:

Let $A(z)=\sum_{j=0}^{\infty}a_jz^j$ be a formal power series, then

• Write the binomial coeffients as residuals of corresponding formal power series

\begin{align*} \mathop{res}_{z}\frac{A(z)}{z^{j+1}}=a_j\tag{1} \end{align*}

• Apply the substitution rule for formal power series:

\begin{align*} A(z)=\sum_{j=0}^{\infty}a_jz^{j}=\sum_{j=0}^{\infty}z^j\mathop{res}_{w}\frac{A(w)}{w^{j+1}}\tag{2} \end{align*}

We observe:

\begin{align*} \sum_{x=0}^{3k}&\sum_{y=0}^{x}(-1)^x\binom{n}{3k-x}\binom{n}{y}\binom{y}{x-y}\\ &=\sum_{x=0}^{\infty}\sum_{y=0}^{\infty}(-1)^x\binom{n}{3k-x}\binom{n}{y}\binom{y}{x-y}\tag{3}\\ &=\sum_{x=0}^{\infty}\sum_{y=0}^{\infty}(-1)^x \mathop{res}_u\frac{(1+u)^n}{u^{3k-x+1}} \mathop{res}_v\frac{(1+v)^n}{v^{y+1}} \mathop{res}_z\frac{(1+z)^y}{z^{x-y+1}}\tag{4}\\ &=\mathop{res}_{u,z}\frac{(1+u)^n}{u^{3k+1}}\sum_{x=0}^{\infty}(-u)^x\frac{1}{z^{x+1}} \sum_{y=0}^{\infty}\left(z(1+z)\right)^y\mathop{res}_v\frac{(1+v)^n}{v^{y+1}}\tag{5}\\ &=\mathop{res}_{u,z}\frac{(1+u)^n}{u^{3k+1}}\sum_{x=0}^{\infty}(-u)^x\frac{1}{z^{x+1}}\left(1+z(1+z)\right)^n\tag{6}\\ &=\mathop{res}_{u}\frac{(1+u)^n}{u^{3k+1}}\sum_{x=0}^{\infty}(-u)^x\mathop{res}_z\frac{\left(1+z(1+z)\right)^n}{z^{x+1}}\tag{7}\\ &=\mathop{res}_{u}\frac{(1+u)^n}{u^{3k+1}}(1-u(1-u))^n\tag{8}\\ &=\mathop{res}_{u}\frac{(1+u^3)^n}{u^{3k+1}}\tag{9}\\ &=[u^{3k}](1+u^3)^n\tag{10}\\ &=\binom{n}{k} \end{align*}

Comment:

• In (3) we change the limit to $\infty$ without changing the value, since we add only $0$.

• In (4) we use $(1+u)^n$ as formal power series with the coefficients $\binom{n}{k}$ according to (1) and do the same for each other binomial coefficient

• In (5) we do some rearrangements to prepare the application of the substitution rule for the innermost sum

• In (6) we apply the substitution rule according to (2)

• In (7) we do some rearrangements to prepare the application of the substitution rule for the other sum

• In (8) we apply a second time the substitution rule according to (2)

• In (9) we simplify the expression

• In (10) we use the coefficient of operator $[z^{3k}]$ to denote the coefficient $a_{3k}$ in $A(z)=\sum_{n=0}^{\infty}a_nz^n$. Observe that following is valid when using the formal residual operator $\mathop{res}$

$$\mathop{res}_z\frac{A(z)}{z^{3k+1}}=[z^{-1}]z^{-3k-1}A(z)=[z^{3k}]A(z)$$

Answer 2

Start by restating the problem with a different choice of variables: we seek to show that $${n\choose k} = \sum_{p=0}^{3k} {n\choose 3k-p} (-1)^p \sum_{q=0}^p {n\choose q} {q\choose p-q}.$$

Re-write the sum as $$\sum_{q\ge 0} {n\choose q} \sum_{p\ge q} {n\choose 3k-p} (-1)^p {q\choose p-q}.$$

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

This yields for the inner sum that $$\sum_{p\ge q} {n\choose 3k-p} (-1)^p {q\choose p-q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{3k+1}} \sum_{p\ge q} {q\choose p-q} (-1)^p z^p \; dz.$$

The sum remaining in the integral is $$\sum_{p\ge q} {q\choose p-q} (-1)^p z^p = \sum_{p\ge 0} {q\choose p} (-1)^{p+q} z^{p+q} \\ = (-1)^q z^q \sum_{p\ge 0} {q\choose p} (-1)^p z^q = (-1)^q z^q (1-z)^q.$$

This yields for the inner sum the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{3k+1}} (-1)^q z^q (1-z)^q \; dz.$$

To conclude substitute this into the outer sum that we seek to evaluate to get $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{3k+1}} \sum_{q\ge 0} {n\choose q}(-1)^q z^q (1-z)^q \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{3k+1}} (1-z(1-z))^n\; dz.$$

Note that $(1+z)\times (1-z\times (1-z)) = 1 + z^3$ so this becomes $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z^3)^n}{z^{3k+1}} \; dz$$

To conclude observe that $$[z^{3k}] (1+z^3)^n = {n\choose k}.$$

A trace as to when this method appeared on MSE and by whom starts at this MSE link.