Showing ${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}$

Question

Prove that for integers $n \geq 0$ and $a \geq 1$, $${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}.$$

I figured I'd post this question, which was on an assignment I did, since I thought the solution was so nice.

Answer 1

Supposedly we should have a bijection $$f: M(n, a) \to \bigcup_{k=0}^{\left\lfloor n/2 \right\rfloor}\left( B(a, n-2k)\times M(k, a)\right)$$ (where $B(a, n-2k)$ is simply the set of all $n-2k$-element subsets of $\{1, 2, \dots, a\}$ and $M(n, a)$ is the set of $n$-element multisets with $a$ types). So take the function $$f: (c_1, \dots, c_a) \mapsto (S, (d_1, \dots, d_a))$$ where $d_i = \left\lfloor c_i/2 \right\rfloor$ and $S = \{\alpha \in \{1, \dots, a\} : \left\lfloor c_\alpha/2 \right\rfloor \neq c_\alpha/2\}$. Now, it's probably worth mentioning that the set $S$ as defined here is always going to be of size $n-2k$ for some $k$ between $0$ and $\left\lfloor n/2 \right\rfloor$, since if $n$ is even, an even number of terms in the multiset will be odd, and if $n$ is odd, an odd number of terms will have an odd value.

The inverse to this function is going to be $$g: \bigcup_{k=0}^{\left\lfloor n/2 \right\rfloor}\left( B(a, n-2k)\times M(k, a)\right) \to M(n, a)$$ defined by $$g : (S, (d_1, \dots, d_a)) \mapsto (c_1, \dots, c_a)$$ where $c_i = \begin{cases} 2d_i & i \notin S \\ 2d_i + 1 & i \in S \end{cases}$. It should be clear that this is the inverse of $f$, and so we're good.

Answer 2

We have $a$ labelled boxes and $n$ indistinguishable balls. The lefthand side is the number of ways to distribute the balls amongst the boxes. The term

$$\binom{a}{n-2k}\binom{k+a-1}{a-1}$$

on the right is the number of ways to distribute $k$ pairs of balls amongst the boxes and then choose $n-2k$ of the boxes, each of which is to receive one of the remaining $n-2k$ balls. Thus, $k = \sum_{\text{box } i} \left\lfloor \dfrac{\text{number of balls in box } i}{2} \right\rfloor$. Clearly this can be anything from $0$ through $\lfloor n/2\rfloor$, so the righthand side also gives the number of ways to distribute the balls amongst the boxes.

(This is essentially Samuel Yusim's proof, but presented in a way that at least some readers will find a bit friendlier.)

Answer 3

This one can also be done using complex variables.

Suppose we seek to evaluate $$\sum_{k=0}^{\lfloor n/2\rfloor} {a\choose n-2k} {k+a-1\choose a-1}.$$

Introduce the integral representation $${a\choose n-2k} =\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{a}}{z^{n-2k+1}} \; dz.$$

Note that this integral is zero when $k>\lfloor n/2\rfloor$ so we may extend the sum to infinity.

This gives for the sum the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{a}}{z^{n+1}} \sum_{k\ge 0} {k+a-1\choose a-1} z^{2k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{a}}{z^{n+1}} \frac{1}{(1-z^2)^a} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1-z)^a} \; dz.$$

This last one evaluates to $${n+a-1\choose a-1}$$ by inspection (Newton binomial).