proof of the negative binomial series using induction?

Question

$$(1-x)^{-n} = \sum_{k\ge0}{k+n-1 \choose n-1}x^k$$

I'm supposed to prove this for any integer n $\ge$ 1 via induction on n. Base case where n = 1 is easy enough to prove, but what about the inductive case?

Answer 1

Suppose the formula for $n$ is known. Writing $(1-x)^{-(n+1)}=\sum_kc_kx^k$ (with certainly $c_0=1$) one must have $(1-x)^{-n}=(1-x)\sum_kc_kx^k=1+\sum_{k>0}(c_k-c_{k-1})x^k$. That gives us the recurrence relation $c_k-c_{k-1}=\binom{k+n-1}{n-1}$ with $c_0=1$. It follows from Pascal's recurrence that $c_k=\binom{k+n}n$ satisfies this recurrence relation.

---

Alternatively to the final observation, you can use the well known fact that $\sum_{i=0}^k\binom{n-1+i}{n-1}=\binom{k+n}n$ to solve the recurrence (it really amounts to the same thing, Pascal's recurrence).