1
$\begingroup$

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}$

$\endgroup$
8
  • $\begingroup$ I think that the question must be "What sequence is $h(x)/(1-x)^2$ the generating functin of?" $\endgroup$ – Somos Apr 9 '19 at 21:56
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Robert Shore Apr 9 '19 at 21:57
  • $\begingroup$ @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 $\endgroup$ – Hushus46 Apr 9 '19 at 22:00
  • $\begingroup$ @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$ ? $\endgroup$ – Hushus46 Apr 9 '19 at 22:06
  • $\begingroup$ Yes, that's what I'm talking about. $\endgroup$ – Robert Shore Apr 9 '19 at 22:23
2
$\begingroup$

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.$$

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.