# 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!}$

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

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

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