Negative binomial theorem 
I have been supplied with a combinatorical proof based on the n'th power, however I am trying to prove this by induction. I have no problem with the base case, or assuming that n=N. However, for n=N+1, I am not sure what to do. I have tried to use Pascal's identity, but the final answer doesn't seem to 'drop out'.
 A: Maybe induction is not the best way to prove this.  But assuming you want to use induction, here is a hint:  To go from the $(1+x)^{-N}$ case to the $(1+x)^{-(N+1)}$ case, you have to divide both sides by $1+x$.  Then you will need a series for $1/(1+x)$, a geometric series.  Then multiply two series.  And hope you get the correct right-hand-side.
A: Assume as an induction hypothesis that
$$\frac1{(1+x)^n}=\sum_{k\ge 0}(-1)^k\binom{n+k-1}kx^k\;.$$
Then
$$\begin{align*}
\sum_{k\ge 0}(-1)^k\binom{(n+1)+k-1}kx^k&=\sum_{k\ge 0}(-1)^k\left(\binom{n+k-1}k+\binom{n+k-1}{k-1}\right)x^k\\\\
&=\frac1{(1+x)^n}+\sum_{k\ge 0}(-1)^k\binom{n+k-1}{k-1}x^k\\\\
&=\frac1{(1+x)^n}+\sum_{k\ge 1}(-1)^k\binom{n+k-1}{k-1}x^k\\\\
&=\frac1{(1+x)^n}+\sum_{k\ge 0}(-1)^{k+1}\binom{n+k}kx^{k+1}\\\\
&=\frac1{(1+x)^n}-x\sum_{k\ge 0}(-1)^k\binom{n+k}kx^k\\\\
&=\frac1{(1+x)^n}-x\sum_{k\ge 0}(-1)^k\binom{(n+1)+k-1}kx^k\;,
\end{align*}$$
so
$$(1+x)\sum_{k\ge 0}(-1)^k\binom{(n+1)+k-1}kx^k=\frac1{(1+x)^n}\;,$$
and
$$\sum_{k\ge 0}(-1)^k\binom{(n+1)+k-1}kx^k=\frac1{(1+x)^{n+1}}\;,$$
as desired.
