Find Infinite Series to Generating Function using Convolution Rule

Question

I'm studying for my Discrete Math final and the following problem with a solution is provided but I'm getting stuck halfway through the solution. Particularly at the step where "we can use the convolution rule to find the coefficients of the product."

Find the infinite series given by the following generating function: $$ (3x+2)(5x-7)\frac{1}{(1-x^2)} $$ We expand out to get $$ (15x^2 - 11x - 14)\frac{1}{1-x^2} $$ Using the fact that $$\frac{1}{1-x^2} = 1 + x^2 + x^4 + ⋯ $$ We can use the convolution rule $$ c_0 = -14 $$ $$ c_1 = (-14)(0) + (-11)(1) = -11 $$ $$ c_2 = (−14)(1) + (−11)(0) + (15)(1) = 1 $$ $$ c_3 = (−14)(0) + (−11)(1) + (15)(0) = −11 $$ $$ c_4 = (−14)(1) + (−11)(0) + (15)(1) = 1 $$ The series is thus $$ −14 − 11 + ^2 − 11^3 + ^4 − 11^5 + ⋯ $$

I don't see where the $c_n$ constants are coming from. We're using the MIT Mathematics for Computer Science textbook.

Answer 1

I've figured it out. It was listed in my book as the product rule. I'll add my solution for anyone else who stumbles on this.

The product rule is as follows:

For two functions $$ A(x) = \sum_{n=0}^\infty a_nx^n $$ $$ B(x) = \sum_{n=0}^\infty b_nx^n $$ Then $$ [x^n](A(x)*B(x)) = a_0b_n + a_1b_{n-1} a_2b_{n-2} + ... + a_nb_0 $$ So $$ [x^0](A(x)*B(x)) = c_0 = a_0b_0 = -14*1 = -14$$ $$ [x^1](A(x)*B(x)) = c_1 = a_0b_1 + a_1b_0 = (-14*0) + (-11*1) = -11 $$ $$ [x^2](A(x)*B(x)) = c_2 = a_0b_2 + a_1b_1 + a_2b_0 = (-14*1) + (-11*0) + (15*1) = 1$$

and so forth until you notice the pattern and can say $$ −14−11+^2−11^3+^4−11^5+⋯ $$

Answer 2

Given two generating functions $f(x) = \sum_{i} a_ix^i$ and $g(x) = \sum_{j} b_j x^j$, the generating function $h(x) = f(x)g(x)$ is of the form $h(x) = \sum_{k} c_k x^k$ where $c_k$ are of the form:

$c_0 = a_0 b_0, c_1 = a_1 b_0 + b_1 a_0, c_2 = a_2 b_0 + a_1 b_1 + b_2 a_0$, etc.

The general formula for $c_n$ is $c_n = \sum_{i=0}^{i=n} a_i b_{n-i}$

In your example, if $f(x) = 15x^2 - 11x - 14$ then $a_i$ might be written as: $-14,-11,15,0,0,0,0,0,\dots,$. Taking $g(x) = \frac{1}{1-x^2}$ we get $b_j$ as: $1,0,1,0,1,0,1,\dots,$.

From the above, $c_0 = -14 \times 1$, $c_1 = -14\times 0 -11 \times 1$, $c_2 = -14 \times 1 - 11 \times 0 + 15 \times 1$, etc. After some time a patter arises, or the $15$ and the $-14$ match with the $1$s or the $-11$ those so.

Answer 3

In this case I would write out the summation and manipulate as follows

$$\begin{align}(15x^2-11x-14)(1-x^2)^{-1}&=(15x^2-11x-14)\sum_{k\ge 0}x^{2k}\\[1ex] &=\sum_{k\ge 1}15x^{2k}-\sum_{k\ge 0}11x^{2k+1}-\sum_{k\ge 0}14x^{2k}\\[1ex] &=-14+\sum_{k\ge 1} (15-14)x^{2k}-\sum_{k\ge 0}11x^{2k+1}\\[1ex] &=-14+\sum_{k\ge 1}x^{2k}-\sum_{k\ge 0}11x^{2k+1}\end{align}$$

You can see how the series is split into the constant term $-14$ the positive even powers of $x$ (i.e. $x^{2k}$) and odd powers of $x$ (i.e. $-11x^{2k+1}$).

So

$$\begin{align}&c_0 =-14\\ &c_{2k} =1 \qquad\qquad(k\gt 0)\\ &c_{2k+1} =-11\qquad(k\ge 0) \end{align}$$