Finding the closed form of a generating function

Question

Given that $k$ is a positive integer and $f(x)$ is the generating function of the sequence $(b_0,b_1,b_2,...)$ where $b_n = {n \choose k}\;\, \forall \;n$, show that: $$f(x)=\frac{x^k}{(1-x)^{k+1}}$$ I tried writing a few terms of $f(x)$:$$f(x)=x^k+{k+1 \choose k}x^{k+1}+{k+2 \choose k}x^{k+2}+...$$$$\;\;\;\;\;\;\;\;\;=x^k\left(1+{k+1 \choose k}x^1+{k+2 \choose k}x^2+...\right)$$$$=x^k\cdot h(x)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; $$ Where $h(x)$ is defined as the expression in parenthesis, then I tried some manipulation, for example I computed $h(x)-xh(x)$, since: ${k+n+1 \choose k}-{k+n \choose k}={k+n \choose k-1}$ we have:

$h(x)-xh(x)=1+{k \choose k-1}x+{k+1 \choose k-1}x^2+...$

But I'm stuck, not sure how I should procede

Answer 1

Here is a variation based upon the coefficient of operator $[x^n]$ which denotes the coefficient of $x^n$ of a series.

We obtain \begin{align*} \color{blue}{b_n=[x^n]f(x)}&=[x^n]\frac{x^k}{(1-x)^{k+1}}\\ &=[x^{n-k}](1-x)^{-k-1}\tag{1}\\ &=[x^{n-k}]\sum_{j=0}^\infty \binom{-k-1}{j}(-x)^j\tag{2}\\ &=[x^{n-k}]\sum_{j=0}^\infty \binom{k+j}{j}x^j\tag{3}\\ &=\binom{n}{n-k}\tag{4}\\ &\,\,\color{blue}{=\binom{n}{k}}\tag{5} \end{align*}

and the claim follows.

Comment:

• In (1) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

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

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

• In (4) we select the coefficient of $x^{n-k}$.

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

Answer 2

HINT:

Inductive hypothesis \begin{eqnarray*} f_k(x)= \sum_{n=k}^{\infty} \binom{n}{k} x^n = \frac{x^k}{(1-x)^{k+1}} \end{eqnarray*} and use \begin{eqnarray*} \binom{n}{k} + \binom{n}{k+1}= \binom{n+1}{k+1}. \end{eqnarray*}

More detail available on request.

Further Hint :

\begin{eqnarray*} f_{k+1}(x) &=& \sum_{n=k+1}^{\infty} \binom{n}{k+1} x^n = \sum_{n=k}^{\infty} \binom{n+1}{k+1} x^{n+1} \\ &=& \sum_{n=k}^{\infty} \binom{n}{k} x^{n+1} + \sum_{n=k}^{\infty} \binom{n}{k+1} x^{n+1} \\ \cdots \end{eqnarray*}