The Gateway to Computer Science Excellence
0 votes
How many bit sequences of length seven contain an even number of 0s?
I’m trying to solve this using recurrence relation

Is my approach correct?

Let T(n) be the string having even number of 0s

T(1)=1 {1}

T(2)=2 {00, 11}

T(3)=4 {001, 010, 100, 111}

Case 1-we add 1 to strings of length n-1 having even number of 0s


Case 2-we add 0 to strings of length n-1 having odd number of 0s


Hence, we have T(n)=2T(n-1)
in Combinatory by | 141 views
yes correct

1 Answer

0 votes
There is a small error in your approach which completely deviates the actual result! In the case 2(when n-1 length string contains odd number of 0) you should observe that the string is invalid and hence the number of strings available with that combinations are -

2^(n-1) - T(n-1) where T(n-1) represent valid strings of length n-1

approach for case 1 is right, so number of strings in case 1 T(n-1)

hence when you add up both of them the final result you'll be getting is rather not dependent on the recurrence relation and holds to be 2^(n-1)

Related questions

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
52,314 questions
60,436 answers
95,252 users