Induction HockeyStickFormula GeneratingFunction Difficult

Problem - 4284

Show that $$\frac{1}{(1-x)^n}=\sum_{k=0}^{\infty}\binom{n-1+k}{n-1}x^k$$


This identity can be proved using mathematical induction.

When $n=1$, the to-be-proved relation becomes $$\frac{1}{(1-x)}=\sum_{k=0}^{\infty}\binom{k}{0}x^k=\sum_{k=0}^{\infty}x^k$$

which holds .

Assuming the relation holds for $n=m$, i.e. $$\frac{1}{(1-x)^m}=\sum_{k=0}^{\infty}\binom{m-1+k}{m-1}x^k$$

then, when $n=m+1$, $$\begin{align*}\frac{1}{(1-x)^{m+1}}=\ &\frac{1}{(1-x)^{m}}\cdot\frac{1}{(1-x)} \\ \\=\ &\left(\sum_{k=0}^{\infty}\binom{m-1+k}{m-1}x^k\right)\left(\sum_{k=0}^{\infty}x^k\right)\\ \\=\ & \sum_{k=0}^{\infty}\left(\sum_{j=0}^k\binom{m-1+j}{m-1}\right)x^k \\ \\=\ &\sum_{k=0}^{\infty}\binom{m+k}{m}x^m \end{align*}$$

The last step relies on the hockey stick identity.

Therefore, by the principle of mathematical induction, we find the to-be-proved relation holds for any positive integer $n$.

It is worth pointing out that this identity means that the generating function of $\binom{n}{n}$, $\binom{n+1}{n}$, $\binom{n+2}{n}$, $\cdots$, $\binom{n+k}{n}$, $\cdots$ is $$\frac{1}{(1-x)^{n+1}}$$

report an error