The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
58 views
Find a recurrence relation for the number of bit strings
of length n that contain a pair of consecutive 0s.
in Combinatory by Active (1.5k points) | 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)

1 Answer

0 votes
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)

Related questions

+1 vote
2 answers
5
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,781 questions
53,593 answers
185,825 comments
70,880 users