Multiplying two generating functions

771 Views Asked by At

I am trying to complete exercise 10 from here. It says to find $a_7$ of the sequence with generating function $\frac{2}{(1−x)^2} \cdot \frac{x}{1−x−x^2}$. I wrote down the first $7$ numbers of both sequences and got $2, 4, 6, 8, 10, 12, 14$ and $1, 1, 2, 3, 5, 8, 13, 21$. I then tried to multiply it out as using distribution as described on the page $$AB = a_0b_0 + (a_0b_1 + a_1b_0)x + (a_0b_2 + a_1b_1 + a_2b_0)x^2 + \dots$$ where $A = a_0 + a_1x + a_2x^2 + \ldots$ and $B = b_0 + b_1x + b_2x^2 + \ldots$.

However, this is incorrect in addition to coming up with closed forms for each of the individual generating functions and adding them.

2

There are 2 best solutions below

0
On BEST ANSWER

The two sequences are, $$2, 4, 6, 8, 10, 12, 14, 16, \dots$$ and, $$0, 1, 1, 2, 3, 5, 8, 13, 21, \dots$$ Note that with generating functions the initial term is $a_0$, "term zero".

So, $a_7$ is actually the $8^{th}$ term.

The convolution of these two sequences, also called the Cauchy product, is found by multiplying the generating series associated with these sequences together.

In other words we're going to multiply, $$2+4x+6x^2+8x^3+10x^4+12x^5+14x^6+16x^7+\dots$$ by, $$0+x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+...$$ I'll do all eight terms up to $a_7$ as it'll make the pattern more obvious, $$(0\times 2)$$ $$+(1\times 2+0\times 4)x$$ $$+(1\times 2+1\times 4+0\times 2)x^2$$ $$+(2\times 2+1\times 4+1\times 6+0\times 8)x^3$$ $$+(3\times 2+2\times 4+1\times 6+1\times 8+0\times 10)x^4$$ $$+(5\times 2+3\times 4+2\times 6+1\times 8+1\times 10+0\times 12)x^5$$ $$+(8\times 2+5\times 4+3\times 6+2\times 8+1\times 10+1\times 12+0\times 14)x^6$$ $$+(13\times 2+8\times 4+5\times 6+3\times 8+2\times 10+1\times 12+1\times 14+0\times 16)x^7$$ $$+\dots$$ It's the coefficient of $x^7$ we are after, $$(26+32+30+24+20+12+14)x^7$$ $$=(158)x^7$$ which is, indeed, 158, as you were expecting.

Not the easiest of examples on account of the 0 and pair of 1s at the start of the Fibonacci sequence.

0
On

If you don't want to use the Cauchy product as you've described it, find constants $a,\,b\ne a,\,A,\,B,\,C,\,D$ such that $$\frac{1}{1-x-x^2}=\frac{-1}{(a-x)(b-x)},\,\frac{2x}{(1-x)^2(1-x-x^2)}=\frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{a-x}+\frac{D}{b-x}.$$Then the $x^n$ coefficient is $A+(n+1)B+\frac{C}{a^{n+1}}+\frac{D}{b^{n+1}}.$