0
$\begingroup$

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 ^^

  • 0
    Then add them to your question.2012-08-24

2 Answers 2

3

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.

0

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.

  • 1
    $b_n$=$a_{n-1}$2012-08-24