Proof of an identity with generating function

Question

I have some trouble with an exercise in discrete mathematics:

Show for $0\leq i\leq r-1$:

$$ \sum^{\infty}_{n=1}\binom{n-1}{r-i-1}t^n=\left(\frac{t}{1-t}\right)^{r-i}=\frac{t^{r-i}(1-t)^{i-1}}{(1-t)^{r-1}}. $$

I really have some trouble to start on this on and every help is highly appreciated!

Kind regards.

Answer 1

We obtain \begin{align*} \color{blue}{\left(\frac{t}{1-t}\right)^{r-i}}&=t^{r-i}\cdot\frac{1}{(1-t)^{r-i}}\\ &=t^{r-i}\sum_{n=0}^\infty\binom{-(r-i)}{n}(-t)^n\tag{1}\\ &=t^{r-i}\sum_{n=0}^\infty\binom{n+r-i-1}{n}t^n\tag{2}\\ &=\sum_{n=0}^\infty\binom{n+r-i-1}{r-i-1}t^{n+r-i}\tag{3}\\ &=\sum_{n=r-i}^\infty\binom{n-1}{r-i-1}t^{n}\tag{4}\\ &\color{blue}{=\sum_{n=1}^\infty\binom{n-1}{r-i-1}t^{n}}\tag{5} \end{align*}

Comment:

• In (1) we apply the binomial series expansion.

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

• In (3) we collect the terms in $t$ and use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

• In (4) we shift the index to start from $n=r-i$.

• In (5) we observe $\binom{n-1}{r-i-1}=0$ for $1\leq n\leq r-i-1$ and start with $n=1$.

Answer 2

First note that $$ \frac{1}{(1-x)^k}=\sum_{n=0}^\infty \binom{k+n-1}{k-1}x^n\tag{1} $$ by differentiating the geometric series (where $k\geq 1$). In particular $$ \frac{1}{(1-x)^{r-i}}=\sum_{n=0}^\infty \binom{r-i+n-1}{r-i-1}x^n\tag{2} $$ and hence $$ \frac{x^{r-i}}{(1-x)^{r-i}} =\sum_{n=0}^\infty \binom{r-i+[n-(r-i)]-1}{r-i-1}x^n =\sum_{n=0}^\infty \binom{n-1}{r-i-1}x^n\tag{3} $$ since multiplying by $x^m$ ($m\geq 1$) shifts the coefficient from $a_n$ to $a_{n-m}$.