Question

An n-bit binary string is a sequence of length n over the alphabet {0,1}.

1. How many n-bit binary strings are there?
2. How many n-bit binary strings b1,…,bn are there such that b1b2≠00? In other words, how many n-bit binary strings don't begin with 00?
3. How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and b2b3≠11?
4. How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and such that b2b3≠01?

Answer 1

Q1

Each position has 2 choices either it is 0 or it is 1 so there are 2^n possible strings

Q2

Rest n-2 positions can be filled in ways and the first two positions can be filled by 11,10,01

So the answer is ways

Q3

Then among the 8 possibilities, we have for first 3 bits we have to reject 000,001,011,111 rest of the strings are acceptable hence the answer is

Q4

For this similarly, we reject the strings which have 000,001,101 in the beginning rest 5 combinations out of the 8 are acceptable hence the answer is

Do give a thumbs up and in case there are doubts leave a comment.