# Generating function of $\frac{h(x)}{(1-x)^2}$

If $$h(x)$$ is the generating function for $$a_r$$, what is the generating function of $$\frac{h(x)}{(1-x)^2}$$

Let $$h(x)$$ be written as

$$h(x) = \sum_{r} a_r x^r$$

Consider more simply

$$\frac{h(x)}{1-x} = \frac{1}{1-x} h(x) =\sum_{r} x^r \sum_{r} a_r x^r$$

I tried to expand this and see what I could get

$$(1+x+x^2+x^3+\dots+x^r+\dots)(a_0+a_1x+a_2x^2+a_3x^3+\dots+a_rx^r+\dots)$$

there are two ways to simplify the product, either

$$a_0(1+x+x^2+\dots)+a_1(x+x^2+x^3+\dots)+ a_2(x^2+x^3+x^4+\dots)+\dots= \sum_ra_r\sum_{k\ge r}x^k$$

or $$a_0 + (a_0+a_1)x+(a_0+a_1+a_2)x^2+(a_0+a_1+a_2+a_3)x^3 = \sum_r \left(\sum_{k\le r}a_k \right)x^r$$

obviously this is only for one factor of $$\frac{1}{1-x}$$ but I assume If I can get help for this I can extend it to two factors.

I'm not sure what form the answer is expected to be in? Because I could say the generating function is

$$\frac{h(x)}{1-x} = h\left(\sum_{k \ge r}x^k\right)$$

but I'm not sure that makes any sense. I was expecting to say something like

$$\frac{h(x)}{1-x} \mapsto h(x^2)$$

(the $$x^2$$ is not intentional, just some idea of what I believe the answer could look like)

Any help for the case of $$\frac{1}{1-x}$$ would be great and then I could extend it to $$\frac{1}{(1-x)^2}$$

• I think that the question must be "What sequence is $h(x)/(1-x)^2$ the generating functin of?" – Somos Apr 9 '19 at 21:56
• It probably helps a lot to note that because $\frac{d}{dx} \frac{1}{1-x} = \frac{1}{(1-x)^2}$, by taking the derivative of the geometric series we get $\frac{1}{(1-x)^2}=\sum_{n=0}^\infty (n+1)x^n$. Then you can just use one convolution of this series with the generating function for $h(x)$. – Robert Shore Apr 9 '19 at 21:57
• @Somos I'm not sure, you might be right. This is from a list of review questions for my combinatorics exam, see here a screenshot from the paper link – Hushus46 Apr 9 '19 at 22:00
• @RobertShore I have not heard the term convolution in my class but I assume you mean a new generating function where the coefficients $c_n = a_0b_n+a_1b_{n-1}+\dots+a_{n-1}b_1+a_nb_0$ ? – Hushus46 Apr 9 '19 at 22:06
• Yes, that's what I'm talking about. – Robert Shore Apr 9 '19 at 22:23

First, note that

$$\frac{d}{dx} \frac{1}{1-x}=\frac{1}{(1-x)^2}.$$

Thus, taking the derivative of the power series we have:

$$\frac{1}{(1-x)^2}=\sum_{k=0}^\infty (k+1)x^k.$$

Let

$$h(x)=\sum_{n=0}^\infty a_nx^n.$$

Then taking the convolution of these two series, we have:

$$\frac{h(x)}{(1-x)^2}=\sum_{n=0}^\infty \sum_{k=0}^n (k+1)a_{(n-k)}x^n.$$

Another way.

Since $$(1-x)^2 = 1-2x+x^2$$, if $$\dfrac{h(x)}{(1-x)^2} =\sum_{n=0}^{\infty} a_nx^n$$ then

$$\begin{array}\\ h(x) &=(1-x)^2\sum_{n=0}^{\infty} a_nx^n\\ &=(1-2x+x^2)\sum_{n=0}^{\infty} a_nx^n\\ &=\sum_{n=0}^{\infty} a_nx^n-2x\sum_{n=0}^{\infty} a_nx^n+x^2\sum_{n=0}^{\infty} a_nx^n\\ &=\sum_{n=0}^{\infty} a_nx^n-\sum_{n=0}^{\infty} 2a_nx^{n+1}+\sum_{n=0}^{\infty} a_nx^{n+2}\\ &=\sum_{n=0}^{\infty} a_nx^n-\sum_{n=1}^{\infty} 2a_{n-1}x^{n}+\sum_{n=2}^{\infty} a_{n-2}x^{n}\\ &=a_0+a_1x+\sum_{n=}^{\infty} a_nx^n-2a_0x-\sum_{n=2}^{\infty} 2a_{n-1}x^{n}+\sum_{n=2}^{\infty} a_{n-2}x^{n}\\ &=a_0+(a_1-2a_0)x+\sum_{n=}^{\infty} (a_n-2a_{n-1}+a_{n-2})x^n\\ \end{array}a_n$$

If $$h(x) =\sum_{n=0}^{\infty} h_nx^n$$ then, equating coefficients, $$h_0 = a_0$$, $$h_1 = a_1-2a_0$$, so $$a_1 = h_1+2a_0 = h_1+2h_0$$, and, for $$n \ge 2$$, $$h_n =a_n-2a_{n-1}+a_{n-2}$$ so $$a_n =h_n+2a_{n-1}-a_{n-2}$$.

The advantage of this method is that getting each new $$a_n$$ takes only 3 operations (multiply, add, subtract) instead of $$n$$.