58 views
Find a recurrence relation for the number of bit strings
of length n that contain a pair of consecutive 0s.
| 58 views
0
Explanation obtained from solution manual of Discrete Mathematics by Rosen is this:
Let an be the number of bit strings of length n containing a pair of consecutive O's. In order to construct
a bit string of length n containing a pair of consecutive O's we could start with 1 and follow with a string
of length n - 1 containing a pair of consecutive O's, or we could start with a 01 and follow with a string
of length n - 2 containing a pair of consecutive O's, or we could start with a 00 and follow with any string
of length n - 2. These three cases are mutually exclusive and exhaust the possibilities for how the string
might start. From this analysis we can immediately write down the recurrence relation, valid for all n 2: 2:
a(n)=a(n-1)+a(n-2)+2^(n-2)
My Doubt is shouldn't it have been 2a(n-2). There are two sequences of length as obtained above. My answer before seeing the answer was a(n)=a(n-1)+a(n-2)+2^(n-2)

No it can not be a(n-2)+ a(n-2) , because when we encountered '1' , the remaining problem is same as original but with (n-1) length so it is a(n-1) , and if it is '0' then we can not have '0' at consecutive place so it reduces to a(n-2).

so it is , a(n-1) + a(n-2)
by Active (5k points)

1
3
4
+1 vote
5
6