784 views
0 votes
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

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)

1 Answer

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

0 votes
0 votes
2 answers
1
aditi19 asked Apr 28, 2019
3,134 views
Find a recurrence relation for the number of bit strings of length n that contain the string 01.
0 votes
0 votes
0 answers
2
0 votes
0 votes
0 answers
3
aditi19 asked May 13, 2019
630 views
Consider the nonhomogeneous linear recurrence relation $a_n$=$3a_{n-1}$+$2^n$in the book solution is given $a_n$=$-2^{n+1}$but I’m getting $a_n$=$3^{n+1}-2^{n+1}$
1 votes
1 votes
2 answers
4
admin asked May 2, 2020
329 views
How many bit sequences of length seven contain an even number of $0s?$