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

  • $\begingroup$ What did you do? Question (a) does not seem that difficult... $\endgroup$ – Did Aug 24 '12 at 7:07
  • $\begingroup$ 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) $\endgroup$ – Spyral Aug 24 '12 at 7:09
  • $\begingroup$ Then add them to your question. $\endgroup$ – 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.

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

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.