for n = 0,1,2,... let Sn the number of \"words\" of length n that do not contain

Question

for n = 0,1,2,...

let Sn the number of "words" of length n that do not contain the string "ab" using only the letters a and b...

For example there is only one word of length zero. i.e the "null" word So = 1

and two words of length 1 i.e {a,b}, and three words of length two; {aa,bb,ba} since we exclude ab...

Now a recursive definition of Sn is So=1 and S1=2 and Sn = S(n-1)+S(n-2)+(n-2)^2 for n greater or equal to 2.

The question asks to find a formula for Sn and to prove it correct...I found the recursive formula above...maybe that is the one to prove correct..This question comes from a section of the book that uses induction proofs...

Explanation / Answer

As I wrote in comments, your recursive formula is wrong. For example for n=3, we have only 4 words {aaa,bbb,baa,bba} but your formula gives S(3)=6. And as cchappa said, the true formula for Sn is n+1.

Assume that you want to find the number of words of length n, that have this property.

If a word of length n starts with 'a', then the rest of the letters in this word must be 'a' too, otherwise we will have an 'ab' which is against the property.

If a word of length n starts with 'b', then the rest of the (n-1) letters in this word must have this property too, i.e. we have Sn-1 words of length n that start with 'b'.

So the total number of words of length n that satisfy this property is : Sn = Sn-1 + 1

Using S0=1 , you can conclude that Sn = n + 1 .

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.