A combinatorial identity No. 2

Question

I have no idea how to simplify ( if possible at all ) this sum

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

It would be fine if a 1-binomial expression formula would result.

Answer 1

This is too long for a comment and I don't know if this is useful, but I tried to do it with Mathematica and it gave me:

$\quad\quad\quad\quad\quad\quad$

Which in TeXForm, yields:

$$\frac{ \, _2F_1(-n,2 x-y;-n+x+1;-2) x!}{n! (x-n)!}$$

Where $_2F_1(a,b;c;d)$ and Hypergeometric2F1 are this hypergeometric function. If you need a reference for hypergeometric functions, I guess you could read Knuth/Graham/Patashnik's: Concrete Mathematics. I'm posting it because perhaps you can find the concept interesting/useful.

Answer 2

Note: I agree with @Joriki's comment and I want to provide some reasoning why we don't expect to get a closed formula for OP's expression.

We do so by translating the problem into a representation with polynomials and comparing it with the Vandermonde's Identity. While the polynomials in case of Vandermonde's identity can be easily transformed to a simple polynomial giving a closed binomial expression, we will see that this is not the case in OP's problem. As Joriki stated, the main reason is the factor $2^k$.

For convenience only we substitute $y-2x$ with $y$ in OP's expression and consider \begin{align*} \sum_{k=0}^{n}(-1)^k\binom{x}{n-k}\binom{y}{k}2^k\qquad\qquad n\geq 0\tag{1} \end{align*}

Since according to the binomial theorem

\begin{align*} (1+z)^x=\sum_{k=0}^x\binom{x}{k}z^k \end{align*} we can write $\binom{x}{k}$ as the coefficient of $z^k$ in $(1+z)^x$. We use the coefficient of operator $[z^k]$ and can write \begin{align*} \binom{x}{k}=[z^k](1+z)^x\qquad\qquad k\geq 0 \end{align*}

First step: Vandermonde's Identity

Before we analyse OP's expression let's have a look at Vandermonde's Identity

\begin{align*} \sum_{k=0}^{n}\binom{x}{n-k}\binom{y}{k}=\binom{x+y}{n}\qquad\qquad n\geq 0\tag{2} \end{align*}

We start with the LHS of (2) and obtain

\begin{align*} \sum_{k=0}^{n}\binom{x}{n-k}\binom{y}{k} &=\sum_{k=0}^{n}[z^{n-k}](1+z)^x[w^k](1+w)^y\tag{3}\\ &=\sum_{k=0}^{n}[z^{n}]z^k(1+z)^x[w^k](1+w)^y\tag{4}\\ &=[z^{n}](1+z)^x\sum_{k=0}^{n}z^k[w^k](1+w)^y\tag{5}\\ &=[z^{n}](1+z)^x(1+z)^y\tag{6}\\ &=[z^{n}](1+z)^{x+y}\\ &=\binom{x+y}{n} \end{align*}

Comment:

• In (3) we write the binomial coefficients as coefficients of corresponding polynomials

• In (4) we use the identity $[z^{n+k}]f(z)=[z^n]z^{-k}f(z)$

• In (5) we rearrange the sum to prepare for a substitution in the next line

• In (6) we consider (generally a formal series) $f(z)=\sum_{k=0}^{\infty}a_kz^k$ and observe \begin{align*} f(z)=\sum_{k=0}^{\infty}a_kz^k=\sum_{k=0}^{\infty}\left([w^k]f(w)\right)z^k \end{align*} noting that $a_k$ is the coefficient of $w^k$ in $f(w)$.

Conclusion: We see, it's easy to get a closed formula since the polynomials $(1+z)^x(1+z)^y$ can be nicely combined to $(1+z)^{x+y}$.

Now let's consider OP's expression.

Second step: OP's expression

We proceed precisely as above and obtain

\begin{align*} \sum_{k=0}^{n}(-1)^k\binom{x}{n-k}\binom{y}{k}2^k&=\sum_{k=0}^{n}[z^{n}]z^k(1+z)^x[w^k](1-2w)^y\tag{6}\\ &=[z^{n}](1+z)^x\sum_{k=0}^{n}z^k[w^k](1-2w)^y\\ &=[z^{n}](1+z)^x(1-2z)^y\tag{7}\\ \end{align*}

Comment:

• In (6) we collect $(-1)^k2^k\binom{y}{k}$ and note this is the coefficient of $w^k$ in $(1-2w)^y$.

• In (7) we observe that $(1+z)^x(1-2z)^y$ can't be further simplified.

Conclusion: Due to the expression (7) we don't expect to derive a closed formula.