Recurrence relation problem

**kkkkkk** · December 10th 2008, 09:17 AM

Find a recurrence relation for the number of ternary strings (0 s, 1 s and 2 s) of length n that contain none of the strings 101, 202, 102, or 201. What are the initial conditions? Use the recurrence to compute the number of such sequences of length 5.

I am trying this for the past 7 days. Please help me in solving this. help would be greatly appreciated.

**Opalg** · December 10th 2008, 11:59 AM

Originally Posted by kkkkkk

Find a recurrence relation for the number of ternary strings (0 s, 1 s and 2 s) of length n that contain none of the strings 101, 202, 102, or 201. What are the initial conditions? Use the recurrence to compute the number of such sequences of length 5.

Let $a_n$ be the number of such strings of length n. Now think about how to construct a string of length n+1 by taking such a string, call it s, and adding an additional number at the end of s. If s ends in a 1 or a 2 then we can add any of 0,1,2 and still have an allowable string. But if s ends in a 0 we need to look at the last two elements of s. If they are 00, we can add anything and still have an allowable string. But if s ends in 10 or 20 then we have to add a 0 as the (n+1)th element.

Another way to say that is that we can add a 0 to any string and still have an allowable string. But we have to be more careful about adding a 1 or a 2.

So the number of strings of length n ending in a 0 is $a_{n-1}$ and therefore the number ending in a 1 or a 2 is $a_n-a_{n-1}$ .

Now, how many strings of length n+1 are there? For each of the $a_{n-1}$ n-strings ending in a 0 we can get three (n+1)-strings. For each of the $a_{n-2}$ n-strings ending in 00 we can also get three (n+1)-strings. But for each of the $a_{n-1} - a_{n-2}$ n-strings ending in x0 (where x = 1 or 2) we can only get one (n+1)-string. Take that information and make it into a recurrence relation.

**kkkkkk** · December 10th 2008, 12:31 PM

thankyou for your great help

I would appreciate it.

But Finding the recurrence relation was a great difficulty. So, can you suggest me the sequence so that I can make a recurrence relation because I couldn't follow the sequence.

**tester85** · December 10th 2008, 12:46 PM

Just to add : The initial conditions are :
a1 = 3
a2 = 9
a3 = 23

**kkkkkk** · December 10th 2008, 12:53 PM

thanks for u r help. But I couldn't establish the recurrence relation. I tried some. They were working for 1 and 2 but not from 3. So, suggest a recurrence relation that would work for all

**tester85** · December 10th 2008, 06:52 PM

If i am not wrong the recurrence relation is $a_n = a_{n-1}+4a_{n-2}+2a_{n-3}$ .

**Opalg** · December 10th 2008, 11:56 PM

Originally Posted by tester85

If i am not wrong the recurrence relation is $a_n = a_{n-1}+4a_{n-2}+2a_{n-3}$ .

The relation I arrived at (following my previous hints) is $a_n = 3a_{n-1}-2a_{n-2}+2a_{n-3}$ . With the initial conditions $a_1=3$ , $a_2=9$ , $a_3=23$ , that gives the prediction $a_4=57$ , which agrees with what I get by a direct count.

**kkkkkk** · December 11th 2008, 10:23 AM

thank u very much for u r help. I will appreciate it greatly.

Thread: Recurrence relation problem

LinkBack

Thread Tools

Display

Recurrence relation problem

Similar Math Help Forum Discussions

Recurrence relation problem

recurrence relation problem!

Population recurrence relation problem.

Recurrence Relation Problem...

Recurrence Relation problem (URGENT)

Search Tags