How to create the generating function for this sequence

Question

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

Please help ^^

Answer 1

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.

Answer 2

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.