Prove $\sum_{i=0}^{\min(x,y)}\binom{x}{i}\binom{y}{i}2^{x+y-(i+1)}=\sum_{i=0}^{\min(x,y)}2^{x+y-(i+1)} (-1)^i \frac{(x+y-i)!}{(x-i)!(y-i)!i!}$

Question

I found the formula below counting the path on the grid (link). $$\sum_{i=0}^{\min(x,y)}\binom{x}{i}\binom{y}{i}2^{x+y-(i+1)}=\sum_{i=0}^{\min(x,y)}2^{x+y-(i+1)} (-1)^i \frac{(x+y-i)!}{(x-i)!(y-i)!i!}$$ How to prove this (I prefer more intuitive way)? I check this formula by a program up to $x,y\leq10$ and this seems correct.

My idea:

Suppose that $x>y$. There is a formula which looks similar to this question. \begin{align} &[t^y] (1+t)^x(1+t)^y \\ =&\sum_{i=0}^{\min(x,y)}\binom{x}{i}\binom{y}{i} \\ =&\binom{x+y}{y} \end{align} Note that $[t^y] f(t)$ corresponds to the coefficient of the term $t^y$ of $f(t)$. Let's change the coefficients to meet our formula. \begin{align} &[t^y] \frac{1}{2}(2+t)^x(2+2t)^y \\ =&\sum_{i=0}^{\min(x,y)}\binom{x}{i}\binom{y}{i}2^{x+y-(i+1)} \end{align} I expect that by counting the coefficient of $t^y$ nicely, we can get $\sum_{i=0}^{\min(x,y)}2^{x+y-(i+1)} (-1)^i \frac{(x+y-i)!}{(x-i)!(y-i)!i!}$.

Answer 1

Using the symmetry in the problem statement we may suppose that $x\le y.$ With $m,n$ for $x,y$ we then seek to prove

$$\sum_{q=0}^m {m\choose q} {n\choose q} 2^{-q} = \sum_{q=0}^m {m+n-q\choose m-q} {n\choose q} 2^{-q} (-1)^q.$$

Start with the RHS to get

$$\sum_{q=0}^m {n\choose q} 2^{-q} (-1)^q [z^{m-q}] (1+z)^{m+n-q} \\ = [z^m] (1+z)^{m+n} \sum_{q=0}^m {n\choose q} 2^{-q} (-1)^q z^q (1+z)^{-q}.$$

Now the coefficient extractor $[z^m]$ combined with the factor $z^q$ enforces the range and we may continue with

$$[z^m] (1+z)^{m+n} \sum_{q\ge 0} {n\choose q} 2^{-q} (-1)^q z^q (1+z)^{-q} \\ = [z^m] (1+z)^{m+n} \left(1 - \frac{z}{2(1+z)}\right)^n \\ = \frac{1}{2^n} [z^m] (1+z)^{m} (2+z)^n.$$

On the other hand we have for the LHS

$$\sum_{q=0}^m {m\choose m-q} {n\choose q} 2^{-q} \\ = \sum_{q=0}^m {n\choose q} 2^{-q} [z^{m-q}] (1+z)^m \\ = [z^{m}] (1+z)^m \sum_{q=0}^m {n\choose q} 2^{-q} z^q.$$

The coefficient extractor once more enforces the range:

$$[z^{m}] (1+z)^m \sum_{q\ge 0} {n\choose q} 2^{-q} z^q \\ = [z^{m}] (1+z)^m \left(1+ \frac{z}{2}\right)^n \\ = \frac{1}{2^n} [z^{m}] (1+z)^m (2+z)^n.$$

The LHS and the RHS have an identical constant factor, the same coefficient extractor and the same argument thereto, and we have the claim.