Find generating function of a sequence if A(x) is generating function of sequence $a_n$.

Question

Let $A(x)$ be generating function of sequence $a_n$. What's the generating function of $s_n=a_0+a_1+a_2+...+a_n$?

Answer 1

Hint:

• $A(x) = a_0+a_1x+a_2x^2+a_3x^3+\cdots$
• You want to find $a_0 + (a_0+a_1)x+(a_0+a_1+a_2)x^2+\cdots$
• How about $(a_0+a_1x+a_2x^2+\cdots) + (a_0x+a_1x^2+\cdots)+ (a_0x^2+\cdots) +\cdots$?
• Can you factorise this? Can you simplify the factorisation?

Answer 2

$$\frac{A(x)}{1-x}$$

To prove it, write out $\sum_{n=0}^\infty s_n x^n$ as a double sum and interchange the order of summations.