# Proving an identity by induction

Can you help me prove the following identity or refer to a proof for it: $$\sum_{n=0}^{\infty}x^{n}\left(\begin{array}{c} n+1\\ i \end{array}\right)=\frac{x^{i-1}}{(1-x)^{i+1}},$$

for $\left|x\right|<1$ and $i>0$. I am trying induction on $i$ but no luck yet. Thanks.

-

The geometric series formula says that $\frac{1}{1-x} = \sum_{n=0}^\infty x^n$ when $|x| < 1$. Setting $g(x) = 1/(1-x)$, show that for all $k > 0$

\begin{align*} g'(x) &= \frac{1}{(1-x)^2}\\ g''(x) &= \frac{2}{(1-x)^3}\\ &\,\,\vdots\\ g^{(k)}(x) &= \frac{k!}{(1-x)^{k+1}}. \end{align*}

At the same time, we have an expression for $g(x)$ as a power series $g(x) = \sum_{n=0}^\infty x^n$ with radius of convergence $1$. The derivative of a power series may be computed term-by-term, and the resulting power series will be converge with the same radius of convergence as the original. For example, in this case this says that

$$\frac{k!}{(1-x)^{k+1}} = \frac{d^k}{dx^k}\sum_{n=0}^\infty x^n = \sum_{n=0}^\infty \frac{d^k}{dx^k}x^n = \sum_{n=k}^\infty n\cdot (n-1)\cdots (n-k+1) x^{n-k},$$ whenever $|x| < 1$.

Multiply both sides by $x^{k-1}/k!$ to conclude

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

for |x| < 1.

-

You can also prove this by induction using Pascal's formula.

Since $\sum_{n=0}^\infty x^n\binom{n+1}{1}=\sum_{n=0}^\infty (n+1)x^n=D_{x}\bigg(\sum_{n=0}^\infty x^{n+1}\bigg)=D_{x}\big(\frac{x}{1-x}\big)=\frac{1}{(1-x)^2}$,

the statement is true for $i=1$.

Now assume that $\sum_{n=0}^\infty x^n\binom{n+1}{i}=\frac{x^{i-1}}{(1-x)^{i+1}}$ for some integer $i>0$.

Then if $h(x)=\sum_{n=0}^\infty x^n\binom{n+1}{i+1}=\sum_{n=i}^\infty x^n\bigg[\binom{n}{i+1}+\binom{n}{i}\bigg]$, letting $m=n-1$ gives $h(x)=\sum_{m=i-1}^\infty x^{m+1}\bigg[\binom{m+1}{i+1}+\binom{m+1}{i}\bigg]=x\bigg(\sum_{m=i-1}^\infty x^m\binom{m+1}{i+1}+\sum_{m=i-1}^\infty x^m\binom{m+1}{i}\bigg)$, so

$h(x)=x\bigg(h(x)+\frac{x^{i-1}}{(1-x)^{i+1}}\bigg)$ and so $h(x)=\frac{x^i}{(1-x)^{i+2}}$.

-