# Multiplying two generating functions

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.

• You are essentially doing this correctly and using the method asked for in the question. The reason it's not working is that that generating function for the Fibonacci numbers starts with a zero. That is, $0, 1, 1, 2, 3, 5, 8, 13, 21,...$ If you still can't get it to work, ask, and I'll post an answer. Apr 14 '19 at 20:01
• @MartinHansen Starting the fibonacci sequence from 0 still give a number greater than 158 which is the stated solution Apr 15 '19 at 14:29
• OK, I've just put a full solution up; hope it makes sense. A green tick if you are happy with it would be marvellous ! Ask if anything's still not clear. Apr 15 '19 at 16:24

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