394 views

We want those bit strings of length $10$ which

1. Start and end with the symbol $1.$
2. No two zeroes are consecutive.

How many such bit strings are there?

### 1 comment

One more method, if the length is small enough –

Kenneth Rosen 7th edition pg. 415

## 3 Answers

Best answer

Okay so for this one i request to go through this previous year gate question where it shows an beautiful application of Fibonacci series .

So for bit string of length $n$ , the number of string which not contain two consecutive 0’s are there follow Fibonacci series where$f1 =2 ,f2=3,f3=5 …..fn=fn-1+fn-2$

GATE CSE 2016 Set 1 | Question: 2 - GATE Overflow for GATE CSE

So we can think think this problem as , given first and last bit as 1  for a string of length $10$ we are remaining with $8$ bit .

so the problem reduce to “the number of 8 bit string  that do not contain two consecutive 0’s” which is $f8$.

$f4=f3+f2=5+3=8$

$f5=f4+f3=8+5=13$

$f6=f5+f4=13+8=21$

$f7=f5+f6=13+21=34$

$f8=f7+f6=34+21=55$

So our required number of string is $55$.

### 4 Comments

Not only in gate, rosen is also having example and question for both: no two consecutive 0s and no  two consecutive 1s . Fibonacci sequence is not only related to this question but it is connected to our daily life too. Something is mentioned here and we can also find it on youtube by searching “Fibonacci in nature”.

@ankitgupta.1729, Rightly said.

We have covered all the Recurrence Relations questions from Kenethe Rosen in the following playlist on GO Classes YouTube channel.

$\color{red}{\text{Detailed Video Solution of this GATE question}}$(Click Below):

Detailed Video Solution

$\color{red}{\text{Complete Recurrence Relation Playlist}}$(Click Below):

@Kabir5454 Excellent answer and presence of mind.

@Deepak Poonia Thank you sir.

@ankitgupta.1729 Yes sir There are many real life application of Fibonacci Its just amazing to think they exist beautifully in nature.

Put $1$'s in the left-most and right position directly. Now we have $8$-bit positions such that No two zeroes are consecutive.

So, we can have No $0$'s OR exactly one $0$ Or exactly two $0$'s Or exactly three $0$'s Or exactly four $0$'s.

So, No $0$'s $=1$ Way $/$ String

• exactly one $0=8$ ways (No problem when we have exactly one 0, So, 8 ways)
• exactly two $0$'s $=\;^{7} \mathrm{C}_{2}=21$ ways (Two 0’s cannot be consecutive, So, we have six 1’s, and two 0’s and 0’s should not be consecutive)
• exactly three $0$'s $=\;^{6} \mathrm{C}_{3}=20$ Ways (No two 0’s can be consecutive, So, we have five 1’s, and three 0’s and 0’s should not be consecutive)
• exactly four $0$'s $= \;^{5} \mathrm{C}_{4}=5$ Ways (No two 0’s can be consecutive, So, we have four 1’s, and four 0’s and 0’s should not be consecutive)

Total $=55$.

### 4 Comments

Exactly two 0’s means there are six 1’s.

Six 1’s can be ordered like _1_1_1_1_1_1_.

If you see, there are 7 gaps for two 0’s (only one 0 allowed in any of the gaps). You can put two 0’s in 7 gaps in C(7,2) ways.

All six 1’s are identical, so only 1 way to arrange. Hence, 1*C(7,2) ways.

Similarly, you can do the rest of the cases.

Understood. Thanks a lot.

I have put more details in the answer to understand it better.

okay have done it for no consecutive zeroes recurrence. Now one can find what a8 is. Fibonacci shows up.

by

Good job🙂
🙂
Answer:

3 votes
1 answer
1
277 views
8 votes
1 answer
2
2 votes
1 answer
3
200 views
3 votes
3 answers
4
204 views