2
$\begingroup$

I have to evaluate this expression $\sum \limits_{k=0}^n(-1)^k\binom{n}{k}\binom{m+n-k}{n-k}$ using snake oil and convolutions. The problem is that I got two different results, could you help me to find the mistake?

(Notation: $[x^n]$ is the operator "take the coefficient of $x^n$.")

Convolution: $ \begin{eqnarray*} \sum_{k=0}^n (-1)^k \binom{n}{k} \binom{m+n-k}{n-k} &=& [x^n] \left( \sum_k(-1)^k \binom{n}{k}x^k \right) \left( \sum\binom{m+k}{k}x^k \right) \\ &=& [x^n] (1-x)^n \frac{1}{(1-x)^{m+1}} \\ &=& [x^n] (1-x)^{n-m-1} \\ &=& (-1)^n\binom{n-m-1}{n} \end{eqnarray*} $

Snake oil: $ \begin{eqnarray*} \sum_m \sum_{k=0}^n (-1)^k \binom{n}{k} \binom{m+n-k}{n-k} x^m &=& \sum_{k=0}^n (-1)^k \binom{n}{k} \sum_m \binom{m+n-k}{n-k} x^m \\ &=& \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{(1-x)^{n-k}} \\ &=& \frac{1}{(1-x)^n} \sum_{k=0}^n (-1)^k \binom{n}{k}(1-x)^k \\ &=& \frac{x^n}{(1-x)^n} \\ &=& \sum_m \binom{m-1}{n-1} x^m , \end{eqnarray*} $ and so the value should be $\binom{m-1}{n-1}$.

Could you help me to find the mistake, please?

1 Answers 1

4

I think there's an error in the "snake oil" part. You should have

$\sum_{m = 0}^{\infty} \binom{m+n-k}{n-k} x^m = \frac{1}{(1-x)^{n+1-k}}$

Which leads you to

$\sum_{m = 0}^{\infty} \sum_{k = 0}^n (-1)^k \binom{n}{k} \binom{m+n-k}{n-k} x^m = \frac{x^n}{(1-x)^{n+1}} = \sum_{m = 0}^{\infty} \binom{m}{n} x^m$

And finally, it's easy to check

$\binom{m}{n} = (-1)^n \binom{n-m-1}{n}$