How Do You Solve Recurrence Relations with Restricted Subsequences?

[toothpaste666]

Homework Statement

a) Find a rec. rel. for an, the number of sequences of length n formed by u's, v's, and w's with the subsequence vv not allowed.
b) Repeat part a) but now with the requirement that there is no subsequence uwv.

The Attempt at a Solution

a) the first letter in the sequence can be a u and then the rest of the sequence can be formed in an-1 ways, it can be a v with the rest of the sequence formed in an-1 ways or a w with the rest in an-1 ways. so an = an-1 + an-1 + an-1 = 3an-1 . But we haven't dealt with the restriction yet. we need to remove the ways where the sequence vv appears. which is choose the two v's and the rest of the sequence is formed in an-2 ways. so
an = 3an-1 - an-2

I am pretty sure this is right but the course website says the answer is an = 2an-1 + 2an-2 and I can't figure out why

b) this time we subtract off the ways that contain uwv. to find this number choose uwv and the rest of the sequence can be formed in an-3 ways so
an = 3an-1 - an-3

this one is apparently correct.

 

[andrewkirk]

we need to remove the ways where the sequence vv appears. which is choose the two v's and the rest of the sequence is formed in an-2 ways. so
an = 3an-1 - an-2

I am pretty sure this is right but the course website says the answer is an = 2an-1 + 2an-2 and I can't figure out why

The website is correct. Some of the sequences that are removed when you deduct a(n-2) sequences have already been removed because they have 'v' in position 2 and 3.
I think it's easier to do by adding (number of valid n-long sequences starting with u) + (number of valid n-long sequences starting with w) + (number of valid n-long sequences starting with v)

where 'valid' means 'containing no 'vv' subsequences.

 

[geoffrey159]

For (a), I think you have the right idea by fixing the first letter. Take a sequence of length $n$ with no vv subsequence.
If it starts with either u or w, then the rest of the word is a sequence of length $n-1$ that have no vv subsequence
If it starts with a v, then the following letter is either u or w, and the rest of the word is a sequence of length $n-2$ that have no vv subsequence.
Adding these cases together, you get $a_n = 2 (a_{n-1} + a_{n-2})$

 

[Ken G]

I see others have already responded, but here's how I got that the course website was right. We agree there are 2an-1 strings if you use a u or a w as the first letter you are tacking on. But if you want to tack on a v, you cannot have a v as the first letter of the n-1 string, so you must ask an independent question-- how many strings of length n-1 do not start with v and do not have vv anywhere in them? So that means look back to the n-2 strings and count all those up, and tack on either a u or a w, so that means you have 2an-2 of those. So 2an-1 + 2an-2 is correct.

Part (b) seems straightforward, does it not?

 

[Ray Vickson]

Homework Statement

a) Find a rec. rel. for an, the number of sequences of length n formed by u's, v's, and w's with the subsequence vv not allowed.
b) Repeat part a) but now with the requirement that there is no subsequence uwv.

The Attempt at a Solution

a) the first letter in the sequence can be a u and then the rest of the sequence can be formed in an-1 ways, it can be a v with the rest of the sequence formed in an-1 ways or a w with the rest in an-1 ways. so an = an-1 + an-1 + an-1 = 3an-1 . But we haven't dealt with the restriction yet. we need to remove the ways where the sequence vv appears. which is choose the two v's and the rest of the sequence is formed in an-2 ways. so
an = 3an-1 - an-2

I am pretty sure this is right but the course website says the answer is an = 2an-1 + 2an-2 and I can't figure out why

b) this time we subtract off the ways that contain uwv. to find this number choose uwv and the rest of the sequence can be formed in an-3 ways so
an = 3an-1 - an-3

this one is apparently correct.

Please either use parentheses or the subscript facility found in the menu ribbon at the top of the input page. As written you have said $a_n = 3 a_n - 1$, which cannot be what you mean. If you mean
a(n) = 3 a(n-1), you need parentheses, just like I have written; alternatively, you can use the "$x_2$" button at the top of the input panel to get a_n= 3a_n-1.

It is vital that you get in the habit of doing this, because there will be cases in which you have something like $a_n = 2 a_{n-1} - 1$, and if you write that the way you have been doing up to now it would read as an = 2 an-1-1, which of course, means that $a_n = 2 a_n - 2$, which is not what we want.

 

[toothpaste666]

Thank you everyone

I just want to test the subscript feature
a_n-1

 

[Ray Vickson]

Thank you everyone

I just want to test the subscript feature
a_n-1

Good. Even better would be to learn LaTeX, which has a partial implementation in this forum. It is faster and easier to use than the "formula/symbol" ribbon at the top of the input page, and it produces much prettier results: $a_{n-1}$, for example. Another nice aspect is that there are extensive free packages available on-line for downloading to your own machine; I use MikTeX, but many people use LyX (which is almost like using MS Word, but produces LaTeX files and compiles and typsets using the TeX package).