Rosen 7e Recurrence Relation Exercise-8.1 Question no-25 page no-511

Question

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)

Comments

yes correct

Answer 1

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)