Using mathematical induction to prove an identity related to combinatorics

Question

Using Mathematical induction on $k$, prove that for any integer $k\geq 1$,

$$(1-x)^{-k}=\sum_{n\geq 0}\binom{n+k-1}{k-1}x^n$$

How should I proceed? The tutorial teacher attempted this question and forgot halfway through... facepalm

Answer 1

The idea is that you prove it for $k=1$ (which is exactly the sum of a geometrical progression), then assuming it is true for $k$, differentiate both members of the equality and obtain the result for $k+1$. The computation must be quite elementary.

Answer 2

HINT: Your induction hypothesis is that

$$(1-x)^{-k}=\sum_{n\ge 0}\binom{n+k-1}{k-1}x^n\;.$$

For the induction step take a look at this calculation:

$$\begin{align*} \sum_{n\ge 0}\binom{n+k}kx^n&=\sum_{n\ge 0}\left(\binom{n+k-1}{k-1}+\binom{n+k-1}k\right)x^n\\ &=(1-x)^{-k}+\sum_{n\ge 0}\binom{n+k-1}kx^n\\ &=(1-x)^{-k}+\sum_{n\ge 1}\binom{n+k-1}kx^n\\ &=(1-x)^{-k}+x\sum_{n\ge 1}\binom{n+k-1}kx^{n-1}\\ &=(1-x)^{-k}+x\sum_{n\ge 0}\binom{n+k}kx^n\;. \end{align*}$$