Negative binomial theorem-proof by induction

Question

The binomial theorem with negative exponents is

$(1+x)^{-n}=\dfrac{1}{(1+x)^n}=\displaystyle\sum\limits_{k=0}^\infty{-n \choose k}x^k$

when $\lvert x\rvert<1$ and where $\displaystyle{-n\choose k}=(-1)^k{n+k-1 \choose k}$

I want proof it for induction on $n$:

for $n=1$ the geometric series $\dfrac{1}{1+x}=\displaystyle\sum\limits_{k=0}^\infty (-1)^kx^k$ is note. I suppose formula true for $n$ and considered $n+1$ case: A Mertens's theorem say that i multiply a absolute convergent series (as $\displaystyle\sum\limits_{k=0}^\infty (-1)^kx^k$) and a convergent series (as $\displaystyle\sum\limits_{k=0}^\infty{-n \choose k}x^k$ for inductive hypotesis) then this product is equal to Cauchy product series. Then $\dfrac{1}{(1+x)^{n+1}}=\dfrac{1}{(1+x)^n}\dfrac{1}{1+x}=$ $=\biggl(\displaystyle\sum\limits_{k=0}^\infty{-n \choose k}x^k\biggl)\biggr(\displaystyle\sum\limits_{k=0}^\infty (-1)^kx^k\biggr)=$

$=\displaystyle\sum\limits_{m=0}^\infty\sum\limits_{k=0}^m{-n \choose k}x^k(-1)^{m-k}x^{m-k}=\displaystyle\sum\limits_{m=0}^\infty\sum\limits_{k=0}^m(-1)^k{n+k-1 \choose k}x^m(-1)^{m-k}=$

$=\displaystyle\sum\limits_{m=0}^\infty x^m (-1)^m \sum\limits_{k=0}^m {n+k-1 \choose k}$.

In conclusion i want proof that $\displaystyle(-1)^m \sum\limits_{k=0}^m {n+k-1 \choose k}={-n-1 \choose m}$, i.e.$\displaystyle {n+m \choose m}=\sum\limits_{k=0}^m {n+k-1 \choose k}$.

I ask if this last formula is true and help for proof it (induction on $m$?) and if my proof of negative binomial theorem is correct. Thanks

Ps. On wikipedia's binomial coefficient page there is: $\sum\limits_{r=0}^m \displaystyle\binom {n+r} r = \binom {n+m+1}{m}.$

Answer 1

Left Hand Side

Select $n$ numbers out of the set $\{1,2,...,n+m\}$. The number of possibility is given by the LHS:

$$ \binom{n+m}{n}=\binom{n+m}{m} $$

Right Hand Side

Select the largest number first. If the largest number is $n+k$ where $k\in\{0,1,...,m\}$, then we choose the remaining $n-1$ numbers out of $\{1,2,...,n+k-1\}$. The total number of possibilities is given by the RHS:

$$ \sum_{k=0}^{m}\binom{n+k-1}{n-1}=\sum_{k=0}^{m}\binom{n+k-1}{k} $$

Conclusion

Two expressions, counting the same number of possibilities, they must be equal, i.e.,

$$ \binom{n+m}{m}= \sum_{k=0}^{m}\binom{n+k-1}{k} $$

The part preceding this expression looks good to me too.

Answer 2

We show by induction on $m$ \begin{align*} \color{blue}{\sum_{k=0}^{m}\binom{n+k-1}{k}=\binom{n+m}{m}}\tag{1} \end{align*}

Base step: $m=0$

The left-hand side of (1) is \begin{align*} \sum_{k=0}^0\binom{n-1}{k}=\binom{n-1}{0}=1 \end{align*} Here we also assume that $n$ is a positive integer so that the upper index of $\binom{n-1}{k}$ is non-negative. The right-hand side of (1) is $\binom{n+0}{0}=1$ and the base step follows.

Induction hypothesis: We assume the validity of (1)

Induction step: $m\to m+1$ We obtain \begin{align*} \color{blue}{\sum_{k=0}^{m+1}\binom{n+k-1}{k}} &=\sum_{k=0}^{m}\binom{n+k-1}{k}+\binom{n+m}{m+1}\tag{2}\\ &=\binom{n+m}{m}+\binom{n+m}{m+1}\tag{3}\\ &\,\,\color{blue}{=\binom{n+m+1}{m+1}}\tag{4} \end{align*} and the claim (1) follows.

Comment:

• In (2) we separate the term with index $k=m+1$ from the sum.

• In (3) we apply the induction hypothesis.

• In (4) we use the binomial identity $\binom{p}{q}+\binom{p}{q-1}=\binom{p+1}{q}$.

Note: The identity (1) is known as Hockey stick identity.