GATE CSE 2008 | Question: 79

Question

Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive $0$s.

The value of $x_5$ is 

• A. $5$
• B. $7$
• C. $8$
• D. $16$

Comments

For more clear picture please refer -->http://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/

---

https://gateoverflow.in/497/gate-cse-2008-question-78

Answer 1

x1 = 0, 1  [Total = 1 (since 0 is not considered)]

x2 = 10,11 [Total = 2]

x3 = 100,101,110,111 [Total = 3]

x4 = 1000,1001,1010,1011,1100,1101,1110,1111 [Total = 5]

Applying for x4 we get that [ Xn= X(n-1)+X(n-2) ] satisfies it -

x4 = x3+x2

     = 3+2 = 5

so, for x5

x5 = x4+x3 = 5+3 = 8

so option C is the correct answer

Answer 2

If suppose asked for some higher index.

$a_{n}-a_{n-1}-a_{n-2}=0$

Shifting, we get $a_{n} (A^{2}-A-1)=0$

Hence the roots are $\frac{1+\sqrt{5}}{2}$ and $\frac{1-\sqrt{5}}{2}$

Hence CF = $C_{1}(\frac{1+\sqrt{5}}{2})^{n} + C_{2}(\frac{1-\sqrt{5}}{2})^{n}$

Now we know $a_{1}=2$ and $a_{2}=3$, using this we get

$C_{1}=1.9173*(\frac{1+\sqrt{5}}{2})^{-1}$ and $C_{1}=-0.133826$

So finally $a_{n}=1.9173*(\frac{1+\sqrt{5}}{2})^{n-1}-0.133826*(\frac{1-\sqrt{5}}{2})^{n}$

Now put n=5, you get $a_{5}=13.1533 \approx 13$