1
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Commented Apr 14, 2019 at 20:01
  • $\begingroup$ @MartinHansen Starting the fibonacci sequence from 0 still give a number greater than 158 which is the stated solution $\endgroup$ Commented Apr 15, 2019 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$ Commented Apr 15, 2019 at 16:24

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.