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.

  • $\begingroup$ 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. $\endgroup$ Apr 14 '19 at 20:01
  • $\begingroup$ @MartinHansen Starting the fibonacci sequence from 0 still give a number greater than 158 which is the stated solution $\endgroup$
    – dreamin
    Apr 15 '19 at 14:29
  • $\begingroup$ 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. $\endgroup$ 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.

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.


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


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.