How to create the generating function for this sequence

This is a question from my discrete math exam of last semester. And I don't really know how to tackle this question.

$$a_i$$ is the number of different sequences of i symbols (i >= 0) chosen from {0,1,2}, where no 2 1's appear next to each other (so xxx11xx would be impossible), nor two 2's appearing next to eachother. For example 1200 is a valid sequence for 4 symbols. We assume that $$a_0 = 1$$ (the empty row for i = 0)

Question: (a) What do $$a_1, a_2, a_3$$ equal to?

(b) Make the recurrent equation (with initial values) for the sequence $${a_i}$$ For i from 0 to infinity. Explain your answer (c) Calculate the normal generating function of $${a_i}$$ i from 0 to infinity

• What did you do? Question (a) does not seem that difficult... – Did Aug 24 '12 at 7:07
• I have a part of the solution on paper. (a) and (b) aren't the 'biggest' problems, it's especially part (c) that I don't know how to do (but the correct solution for a and b would help to) – Spyral Aug 24 '12 at 7:09
• Then add them to your question. – Did Aug 24 '12 at 7:11

You can calculate $a_n$ by computing $a_n=2a_{n-1}+a_{n-2}$:

Any string of length $n-1$ can extended in at least two different ways to a string of length $n$, namely by choosing a number which is different to the last one in the string. Therefore we get $2a_{n-1}$ strings.

We forgot those which end with two $0$. How many are there? In fact such a string consists of an arbitrary string of length $n-2$, and of course the two $0$.

We end up with $a_n=2a_{n-1}+a_{n-2}$.

I suggest you work with this explicit recursion. Finding the generating function should be purely technical from here.

Hint: Define $b_n$ as the number of admissible sequences of length $n$ ending with 0 and $c_n$ as the number of admissible sequences of length $n$ ending with 1 or 2. Write $a_n$, $b_{n+1}$ and $c_{n+1}$ in terms of $b_n$ and $c_n$. Deduce that $a_{n+1}=2a_n+b_n$ for every $n\geqslant0$, with the convention that $b_0=0$, and that $(a_n)_{n\geqslant0}$ solves a second order difference equation with the initial condition $a_0=a_{-1}=1$. Conclude.

• $b_n$=$a_{n-1}$ – noname1014 Aug 24 '12 at 7:40