sh3lsh one year ago Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. I'm lost on how to start this.

1. ganeshie8

The number of \(n\) bit binary strings can be thought of as two sets : 1) Strings that end in \(1\) 2) Strings that end in \(0\)

2. ganeshie8

Let \(a_n\) denote the number of \(n\) bit strings that do not have two consecutive 0's

3. ganeshie8

If the string ends in \(1\), then the \(n-1\)th bit could be either \(0\) or \(1\) so the number of \(n\) bit strings that end in \(1\) and do not have two consecutive \(0\)'s are \(a_{n-1}\) |dw:1434309606750:dw|

4. ganeshie8

If the string ends in \(0\), then the \(n-1\)th bit must be\(1\), consequently the number of \(n\) bit strings that end in \(10\) and do not have two consecutive \(0\)'s are \(a_{n-2}\) |dw:1434309743465:dw|

5. ganeshie8

So the desired recurrence relation is \[\large a_{n}~~=~~a_{n-1}+a_{n-2}\]

6. ganeshie8

see if you can work the initial conditions

7. sh3lsh

\[a_{1} = 2 \\ 0 \: and \: 1 \\ a_{2} = 3 \\ 11, 01, 10 \\ correct? \]

8. ganeshie8

Looks good!

9. sh3lsh

You're great! Thanks! Can I ask you a quick question though? Often when I look at recurrence relationship answers, they have a(n) being something along of the lines of 2^ a(n-3). Would you have any idea why one would such a thing?

10. sh3lsh
11. ganeshie8

\(2^n\) comes very naturally wgen working with binary strings because the total number of strings of length \(n\) is \(2^n\)

12. ganeshie8

Let me ask you a question. In light of the original problem, can you work a recurrence relation for the number of bit strings of length n that CONTAIN two consecutive 0s. ?

13. sh3lsh

Let me attempt

14. sh3lsh

In this case, would I separate the cases into where it ends with a 1, 10, and 00?

15. ganeshie8

use the original problem

16. sh3lsh

Oh, so still ending with a 1 and ending with a 0?

17. ganeshie8

Let \(a_n\) represents number of bit strings of length \(n\) that DO NOT have two consecutive 0's Let \(b_n\) represents number of bit strings of length \(n\) that CONTAIN two consecutive 0's

18. ganeshie8

since total bit strings of length \(n\) is \(2^n\), do we have \[a_n+b_n = 2^n\] ?

19. sh3lsh

Is that a question? I think that's true.

20. ganeshie8

Yes, that means \(a_n = 2^n-b_n\) plug that in earlier recurrence relation

21. sh3lsh

Why would you do that? We already have \[a_{n}\] Could we just do \[b_{n} = 2^{k}-(a_{n-1} + a_{n-2})\]

22. ganeshie8

we can do that, but that is not a proper recurrence relation

23. ganeshie8

we want to have a single sequence in a recurrence relation (all b_n s)

24. ganeshie8

don't want a_n s

25. ganeshie8

replace \(a_{n-1}\) and \(a_{n-2}\) also

26. sh3lsh

How?

27. sh3lsh

Unfortunately, I must leave. Thanks for helping me through this much!

28. ganeshie8

\(a_{n-1}~~=~~2^{n-1}-b_{n-1}\)