Relationship between the generating functions of sequences $(a_n),(b_n)$ given $b_n=\sum^n_{i=1}a_i$.

I am trying to find the relationship between the generating functions for these sequences given that $b_n=\sum^n_{i=1}a_i$.

I was thinking of simply multiplying both sides by $x$ and summing from $0$ to infinity, to get something like:

$$\sum_{n}^\infty b_nx^n = \left(\sum^n_{i=1}a_i\right)\left(\sum_{n=0}^\infty x^n\right)$$

I'll get $B(x)$ on the left, but i'm struggling to make sense of the right side. The solution of the text expects $B(x)=\frac{A(x)}{1-x}$, but when I try to construct this going backwards, I'm expecting something like

$\sum b_nx^n = \sum a_nx^n \sum x^n$ (I believe).

How can I see this?

  • 1
    $\begingroup$ Hint: $$\sum_{n=1}^\infty\left(\sum_{k=1}^na_k\right)c_n=\sum_{k=1}^\infty a_k\left(\sum_{n=k}^\infty c_n\right)$$ $\endgroup$ – Did Jan 14 '18 at 23:29

From what you have written, I gather that $$B(x)=\sum_nb_nx^n\\A(x)=\sum_na_nx^n\\b_n=\sum_{i=1}^na_i$$ Then $$\begin{align}B(x)&=\lim_{N\to\infty}\left\{\sum_{n=1}^N\sum_{i=1}^na_i x^n\right\}\\&=\lim_{N\to\infty}\left\{a_1x+(a_1+a_2)x^2+(a_1+a_2+a_3)x^3+\cdots+(a_1+\cdots+a_N)x^N\right\}\\&=\left\{(a_1+a_2 x+a_3x^2+\cdots)\sum_{i=1}^\infty x^i\right\}\\&=\frac{A(x)}{x}\sum_{i=1}^\infty x^i\\&=A(x)\sum_{i=0}^\infty x^i\\&=\frac{A(x)}{1-x}\end{align}$$ I used the line with the limits to make it clearer to see the steps, though you can just reorder the sum without using these two steps.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy