The Gateway to Computer Science Excellence
0 votes
64 views
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

T(n)=T(n-1)

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

T(n)=T(n-1)

Hence, we have T(n)=2T(n-1)
in Combinatory by Active (5.1k points) | 64 views
0
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)
by (11 points)

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
50,647 questions
56,492 answers
195,439 comments
100,708 users