A nice identity involving urns and balls problem

Question

Prove the identity: $$\frac{\displaystyle\sum_{k=0}^{a} {n+a-k-2\choose n-2}}{\displaystyle {n+a-1\choose a}} = 1$$ where $C_{i}^{j}$ is defined as the number of ways to simultaneously choose $j$ objects from $i$ objects.

My attempt: I was trying to use a combinatorial argument by saying that out of the given $n$ balls, each of the terms within the summation is the probability of a given urn containing exactly $k$ balls for $k = 0,1,2,...,n$. Thus, the sum reflects the sum of all the probabilities of that urn having exactly $k$ balls, so it must be $1$.

My question: I would like to see an algebraic proof for this identity. Could someone please help with such a proof? In case my argument above is incorrect, please help point out the mistake.

Answer 1

Here is a variation based upon the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write e.g. \begin{align*} [x^k](1+x)^n=\binom{n}{k} \end{align*}

We obtain \begin{align*} \sum_{k=0}^n\binom{n+a-k-2}{n-2}&=\sum_{k=0}^n\binom{-n+1}{a-k}(-1)^{a-k}\tag{1}\\ &=\sum_{k=0}^\infty[x^{a-k}](1+x)^{-n+1}(-1)^{a-k}\tag{2}\\ &=(-1)^a[x^a](1+x)^{-n+1}\sum_{k=0}^\infty (-x)^k\tag{3}\\ &=(-1)^a[x^a](1+x)^{-n}\tag{4}\\ &=(-1)^a\binom{-n}{a}\tag{5}\\ &=\binom{n+a-1}{a}\tag{6} \end{align*} and the claim follows.

Comment:

• In (1) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$ with $p=n-1$ and $q=a-k$.

• In (2) we apply the coefficient of operator.

• In (3) we use the linearity of the coefficient of operator and apply the rule $$[x^{p-q}]A(x)=[x^p]x^qA(x)$$ We also extend the upper range of the series to $\infty$ without changing anything since we are adding zeros only.

• In (4) we use the geometric series expansion.

• In (5) we select the coefficient of $x^a$.

• In (6) we use again the binomial identity as we did in (1).

Answer 2

${n+a-1 \choose n-1}={n+a-1 \choose a}$ is the number of non-negative integer solutions to:

$x_1+x_2+\ldots+x_n=a$

Let $x_1=k$ with $k \in \{0,1,\ldots,a\}$. Then the corresponding number of solutions is ${n+a-k-2 \choose n-2}$.