Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
1  
$b_n$=$a_{n-1}$ –  noname1014 Aug 24 '12 at 7:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.