Generating function of a convolution

590 Views Asked by At

If I need to find generating function of such a sum: $\sum_{k=0}^{n} (n-k) a_k$,

can I write $\sum_{k=0}^{n} (n-k) a_k = \sum_{n\ge 0} nx^n \cdot \sum_{n\ge 0} a_nx^n \cdot \frac{1}{1-x}$ and then multiply the closed forms of the two generating functions and $\frac{1}{1-x}$ and then use partial fraction expansion to turn it into a series? Would that be correct?

1

There are 1 best solutions below

0
On BEST ANSWER

You’re thinking in the right direction, but the details are a bit off. It makes no sense to write $$\sum_{k=0}^{n} (n-k) a_k = \sum_{n\ge 0} nx^n \cdot \sum_{n\ge 0} a_nx^n \cdot \frac{1}{1-x}\;:$$ the lefthand side is a constant, and the righthand side is a non-constant function of $x$. What is true is that

$$\left(\sum_{n\ge 0}nx^n\right)\left(\sum_{n\ge 0}a_nx^n\right)=\sum_{n\ge 0}\left(\sum_{k=0}^n(n-k)a_k\right)x^n\;.$$

We know that $$\frac{x}{(1-x)^2}=\sum_{n\ge 0}nx^n\;,$$ so if $g$ is the generating function for $\langle a_n:n\in\Bbb N\rangle$, then $\sum_{k=0}^n(n-k)a_k$ is the coefficient of $x^n$ in the power series expansion of

$$\frac{xg(x)}{(1-x)^2}\;.\tag{1}$$

If $g(x)$ is a rational function, you can in principle expand $(1)$ into partial fractions, expand in power series, and combine to get the desired coefficient.