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, 2019 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$ Apr 9, 2019 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, 2019 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, 2019 at 22:06
  • $\begingroup$ Yes, that's what I'm talking about. $\endgroup$ Apr 9, 2019 at 22:23

2 Answers 2

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.