0
$\begingroup$

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?

$\endgroup$
  • 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
2
$\begingroup$

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.

$\endgroup$

Your Answer

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