1k views

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

The value of $x_5$ is

1. $5$
2. $7$
3. $8$
4. $16$

edited | 1k views
0

Here X1 =0,1(2)

X2=01,10,11(total 3)

X3=010,011,101,110,111(total 5)

Here X3=X2+x1

X4=3+5=8

X5=5+8=13

No option matching here.
by Boss (38.4k points)
x1=2

x2=3

x3=5

x4=8.................... so on

it seems fibbonacci form so x5=5+8=13

so ans will be 13
by Active (4k points)
+1 vote
Though everyone has already given the correct answer but let me try an easier explanation.

You can do it by hit and trial method.

The smallest string you can think of in the first attempt is

Let's say x1, then it should contain either 0 or 1.

So, for x1 Answer = 2

for x2, it may contain, 11, 10 or 01 ----------> = 3

Similarly, for x3 it may contain, 111, 110, 101, 011, 010 ---------------> = 5

Now, you can see that it is forming a series like 2, 3, 5, ....and so on.

Recall, this popular series. It's nothing but the Fibonacci series.

since, f(n) = f(n-1) + f(n-2), (By fibonacci Series)

So, f(5) = f(4) + f(3), ...............(1)

f(4) = f(3) + f(2) = 5 + 3...........(2)

putting this value of equation 2 in equation 1.

f(5) = 8 + 5

by Boss (13.1k points)
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
by (45 points)