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

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.