# proof of the negative binomial series using induction?

$$(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?

• Hint: $(1-x)^{-(n+1)}=\frac{(1-x)^{n}}{(1-x)}$ – AvZ Jan 21 '15 at 10:06
• Does it really..? – Gudushen Jan 21 '15 at 10:32
• I said this because if you use this result initially, you can prove this by induction. – AvZ Jan 21 '15 at 10:34
• What i meant is that doesnt (1-x)^n / (1-x) = (1-x)^n-1 instead of (1-x)^-n-1? or you meant that this is just a step in the induction process – Gudushen Jan 21 '15 at 10:35
• My bad. You're cprrect – AvZ Jan 21 '15 at 10:36

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).