Easier method to extract coefficients from generating function

224 Views Asked by At

By long division I can see that given some generating function $G(x)$ that generates coefficients $\langle g_0, g_1, g_2, g_3,\ldots\rangle$, that the coefficients generated by $\frac{G(x)}{(1-x)}$ are $\langle g_0, g_0+g_1, g_0+g_1+g_2,\ldots\rangle$. That is, $[x^n]\frac{G(x)}{(1-x)}$ is the sum of all coefficients generated by $G(x)$ up to $n$.

But there must be an easier way. No?

1

There are 1 best solutions below

0
On

If $$ A(x)=\sum_{n=0}^{\infty}a_nx^n;\quad B(x)=\sum_{n=0}^{\infty}b_nx^n $$ then $$ A(x)B(x)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}a_kb_{n-k}\right)x^n. $$ In particular $$ A(x)\frac{1}{1-x}=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}a_k\times 1\right)x^n $$ as desired.