One more method, if the length is small enough –

Kenneth Rosen 7^{th} edition pg. 415

Dark Mode

394 views

15 votes

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$.

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”.

1

@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):

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

Complete Recurrence Relations Playlist

@Kabir5454 Excellent answer and presence of mind.

1

@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.

1

8 votes

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$.

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.

2