How prove binomial cofficients $\sum_{k=0}^{[\frac{n}{3}]}(-1)^k\binom{n+1}{k}\binom{2n-3k}{n}=\sum_{k=[\frac{n}{2}]}^n\binom{n+1}{k}\binom{k}{n-k}$

Solution 1:

Start from the RHS. We are counting the number of ways to choice $k$ elements among $n+1$, then choice $n-k$ elements among the $k$ elements previously chosen. If we imagine to assign a $+1$ weight in the first step, then increase the weight in the second step, we are counting the number of ways to assign a $+1$ or $+2$ weigth to the elements of a subset of $\{1,\ldots,n+1\}$ in such a way that the sum of the weights is just $n$. Rephrasing in the analytic combinatorics framework: $$RHS=\sum_{k=\lfloor n/2\rfloor}^{n}\binom{n+1}{k}\binom{k}{n-k}=[x^n]\,\left((1+x+x^2)^{n+1}\right).\tag{1}$$ Now $1+x+x^2 =(1+x)^2-x$, so, for istance: $$[x^n](1+x+x^2)^{n+1} = [x^n]\sum_{j=0}^{n+1}\binom{n+1}{j}(-1)^j x^j(x+1)^{2n+2-2j}=\sum_{j=0}^{n+1}(-1)^j\binom{n+1}{j}\binom{2n+2-2j}{n-j},$$ just like $1+x+x^2=\frac{1-x^3}{1-x}$ and $$\frac{1}{(1-x)^m}=\sum_{j=0}^{+\infty}\binom{m+j-1}{j}x^j,$$ give: $$[x^n](1+x+x^2)^{n+1}=[x^n]\left(\sum_{j=0}^{n+1}\binom{n+1}{j}(-1)^j x^{3j}\right)\cdot\left(\sum_{j=0}^{+\infty}\binom{n+j}{j}x^j\right).\tag{2}$$ Regarding $(2)$ as a Cauchy product gives $RHS=LHS$, QED. The saddle-point method gives also: $$[x^n](1+x+x^2)^{n+1}=\frac{3^{n+2}}{\sqrt{\pi(12n+30)}}\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right).$$

Solution 2:

By way of enrichment here is another algebraic proof using basic complex variables, quite similar to the accepted answer.

Note that the second binomial coefficient in both sums controls the range of the sum, so we can write our claim like this: $$\sum_{k=0}^{n+1} {n+1\choose k} (-1)^k {2n-3k\choose n-3k} = \sum_{k=0}^{n+1} {n+1\choose k} {k\choose n-k}.$$

To evaluate the LHS introduce the integral representation $${2n-3k\choose n-3k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n-3k}}{z^{n-3k+1}} \; dz.$$ We can check that this really is zero when $k>\lfloor n/3\rfloor.$

This gives for the sum the representation $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \sum_{k=0}^{n+1} {n+1\choose k} (-1)^k \left(\frac{z^3}{(1+z)^3}\right)^k \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \left(1-\frac{z^3}{(1+z)^3}\right)^{n+1} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1+z)^{n+3}} \left(3z^2+3z+1\right)^{n+1} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1+z)^{n+3}} \sum_{q=0}^{n+1} {n+1\choose q} 3^q z^q (1+z)^q \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{q=0}^{n+1} {n+1\choose q} 3^q z^{q-n-1} (1+z)^{q-n-3} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{q=0}^{n+1} {n+1\choose q} 3^q \frac{1}{z^{n+1-q}} \frac{1}{(1+z)^{n+3-q}} \; dz.$$

Computing the residue we find $$\sum_{q=0}^{n+1} {n+1\choose q} 3^q (-1)^{n-q} {n-q+n+2-q\choose n+2-q} = \sum_{q=0}^{n+1} {n+1\choose q} 3^q (-1)^{n-q} {2n-2q+2\choose n-q+2}.$$

Now introduce the integral representation $${2n-2q+2\choose n-q+2} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n-2q+2}}{z^{n-q+3}} \; dz$$ which gives for the sum the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+2}}{z^{n+3}} \sum_{q=0}^{n+1} {n+1\choose q} 3^q (-1)^{n-q} \left(\frac{z}{(1+z)^2}\right)^q \; dz \\ = - \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+2}}{z^{n+3}} \left(\frac{3z}{(1+z)^2}-1\right)^{n+1} \; dz \\ = - \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+3}} (-1+z-z^2)^{n+1} \; dz.$$ Put $w=-z$ which just rotates the small circle to get $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(-w)^{n+3}} (-1-w-w^2)^{n+1} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+3}} (1+w+w^2)^{n+1} \; dw.$$ We get for the final answer $$[w^{n+2}] (1+w+w^2)^{n+1}$$ but we have $2n+2-n-2 = n$ and thus exploiting the symmetry of $1+w+w^2$ we get $$[w^n] (1+w+w^2)^{n+1}.$$

To evaluate the RHS introduce the integral representation $${k\choose n-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^k}{z^{n-k+1}} \; dz.$$

This gives for the sum the representation $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{k=0}^{n+1} {n+1\choose k} \left((1+z)z\right)^k \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z(1+z))^{n+1} \; dz .$$ The answer is $$[z^n] (1+z+z^2)^{n+1},$$ the same as the LHS, and we are done.

We have not made use of the properties of complex integrals here so this computation can also be presented using just algebra of generating functions.

This MSE link has another computation in the same spirit.

Apparently this method is due to Egorychev although some of it is probably folklore.