Generating Function from using sequence

Question

I am new to generating function and having a hard time figuring out generating function using sequence. The question that I am having trouble on is using the sequence a_r = $\sum_{i=0}^{n} \binom{i} {r} $, find the generating function. There is a hint using $\sum_{r>=0}{}$ a_r $x^r $. I the r in ar is lower Can you please help. Thank you.

Answer 1

The generating function for the sequence $\langle a_r:r\ge 0\rangle$ is by definition

$$g(x)=\sum_{r\ge 0}a_rx^r\,;$$

since $a_r=\sum_{i=0}^n\binom{i}r$, we can write this as

$$g(x)=\sum_{r\ge 0}\sum_{i=0}^n\binom{i}rx^r\,.$$

$\binom{i}r=0$ when $i<r$, so every term of $a_r=\sum_{i=0}^n\binom{i}r$ is $0$ when $r>n$. This means that $a_r=0$ when $r>n$, so

$$g(x)=\sum_{r=0}^n\sum_{i=0}^n\binom{i}rx^r\,:$$

it’s actually a polynomial of degree $n$.

$$\begin{align*} g(x)&=\sum_{r=0}^n\sum_{i=0}^n\binom{i}rx^r\\ &=\sum_{i=0}^n\sum_{r=0}^n\binom{i}rx^r\\ &=\sum_{i=0}^n\sum_{r=0}^i\binom{i}rx^r\cdot 1^{i-r}\\ &=\sum_{i=0}^n(x+1)^i\,. \end{align*}$$

This is a finite geometric series, so you should be able to express it in closed form; it’s not hard to simplify that closed form to a polynomial.

That approach works even if you know only the most basic facts about binomial coefficients. If you know the hockey stick identity, you can rewrite $g(x)$ as

$$\sum_{i=0}^nx^r\sum_{r=0}^n\binom{i}r$$

and apply the hockey stick identity to get the polynomial directly.