Question about product of generating functions in a proof that for positive integer $n$, $\sum_{k=0}^n(-1)^k\binom nk\binom{2n-k}n=1$.

binomial-coefficientsgenerating-functionsproof-explanationsummation

I was recently looking at a copy of the Mathematics Magazine from 2004 and was reading Q944 (here). It asks this:

Show that for positive integer $n$, $$\sum_{k=0}^n(-1)^k\binom nk\binom{2n-k}n=1.$$

The solution is here. Basically, if we let $S_n$ be the sum, we find that we can write $$S_n=\sum_{k=0}^na_{n-k}b_k,$$ where $a_k=(-1)^k\binom nk$ and $b_k=\binom{n+k}n$. Then we can find generating functions for $a_k$ and $b_k$. In particular, we find that $$\sum_{k=0}^na_kx^k=(1-x)^n$$ and $$\sum_{k=0}^\infty b_kx^k=\frac1{(1-x)^{n+1}}.$$

So far, all of this makes sense to me. Now for the final step of the solution, we note that $$\sum_{n=0}^\infty S_nx^n=\sum_{n=0}^\infty\left(\sum_{k=0}^na_{n-k}b_k\right)x^n=(1-x)^n\cdot\frac1{(1-x)^{n+1}}.$$

This last step doesn't really make a lot of sense to me. After all, aren't the generating functions for $a_k$ and $b_k$ dependent on $n$? And so, for example, don't we get that $a_1$ means different things depending on what $n$ is?

Sorry if I'm not being clear here–I'm having a bit of trouble formulating exactly what my confusion is. But, basically, if somebody could explain the last step in a bit more detail, that'd be fantastic.

Best Answer

I’d carry out the last step a bit differently. What the first part shows is that $S_n$ is the coefficient of $x^n$ in the product

$$(1-x)^n\cdot\frac1{(1-x)^{n+1}}\;,\tag{1}$$

something that is often written

$$S_n=[x^n]\left((1-x)^n\cdot\frac1{(1-x)^{n+1}}\right)$$

with the $[x^n]$ operator. Clearly, then,

$$\begin{align*} S_n&=[x^n]\left(\frac{(1-x)^n}{(1-x)^{n+1}}\right)\\ &=[x^n]\left(\frac1{1-x}\right)\\ &=[x^n]\sum_{k\ge 0}x^k\\ &=1\;. \end{align*}$$

The $n$ in $(1)$ really does depend on which $S_n$ we’re computing, but $(1)$ simplifies to $\frac1{1-x}$ for all $n$, so in the end we really are looking at one power series.

Related Question