## 8 Answers

$01 \ 10 \ 11 -3$

$010 \ 011 \ 101 \ 110 \ 111 -5$

$0101 \ 0110 \ 0111 \ 1010 \ 1011 \ 1101 \ 1110 \ 1111 -8$

So, $x_n = x_{n-1} + x_{n-2}$ (For all the strings ending in $1$, we get two new strings ending in either $0$ or $1$ and for all strings ending in $0$, we get a new string ending in $1$. So, the new set of strings for $x_{n}$, will have exactly $x_{n-1}$ strings ending in $1$ and $x_{n-2}$ strings ending in $0)$

$x_{5}= 8+5 = 13$

Correct Answer: $D$

### 7 Comments

$x_n$ denote the no. of the binary string of length n that contains no consecutive 0's.

Either the string can end with 0 or 1.

If the string ends with 1 then we will find $x_{n-1}$. (The no. of the binary string of length n - 1 that contains no consecutive 0's.).

$\underbrace{ x_{n - 1} }$ 1

If the string ends with 0, then second last string must be 1. (Think !). Now, we will find $x_{n-2}$, the no. of the binary string of length n - 2 that contains no consecutive 0's.

$\underbrace{ x_{n-2}}$ 10.

Recurrence relation,

$x_1$ = 2

$x_2$ = 3

$x_n$ = $x_{n-1}$ + $x_{n-2}$ | n > 2.

$n=1$

0

1

$n=2$

00 = fails

01

10

11

$n=3$

so here we will make possible combinations with the above three valid strings of previous case(n=2) only; and to get new strings of length 3, we can put either zero or 1 on the front of valid strings of the previous case, so we get:

0 01 = fails

0 10

0 11

1 01

1 10

1 11

here in this case we get 5 strings; pattern which option D says resembles here.

answer for **Q.78 = option D**

answer for Q.79 = $x_5 = x_4 + x_3 = 8 + 5 = 13$ but no option matches so we select the closest which is option D

its wrong to do like this but.. we are out of choices here.

{Here $a_{n}$ represents every n-bit string that is counted by $x_{n}$}

We start thinking how can we construct $a_n$ from $a_{n-1}$, such that there are no adjacent zeroes..

When using $a_{n-1}$, we know that the $zero^{th} place$ digit can be $0$ or $1$.

And to construct $a_{n}$, we must choose from among { $0a_{n-1}$ , $1a_{n-1}$ }, where exactly those strings where $a_{n-1}$ has $0$ at the $zero^{th} place$ and from the group $0a_{n-1}$ have a repeating zero.

So we can write $x_{n} = x_{n-1} + (No. \ of \ strings \ with\ '01'\ fixed \ at \ start) $

Since, only $n-2$ bits are changing,it's as good as counting $x_{n-2}$ bit strings

$x_{n} = x_{n-1} + x_{n-2} $

*[The question has been answered very nicely by seniors already, so here I am just adding the common doubt people have been asking.]*

If we append ‘1’ to all the (n-1)length strings and ‘10’ to all the strings of (n-2)length then we will be able to cover all cases. **HOW?**

Now you might think that we can also append ‘11’ to all (n-2) length strings. Yes, but that case will be covered by appending ‘1’ to all (n-1)length strings.

**1st QUESTION**: Why are we just appending ‘1’ to all the (n-1)length strings?

**Ans**: Because some (n-1) length string might end with 0 and we don’t want to have consecutive 0s.

**2nd QUESTION**: So when will we cover cases of (n-1)length string, where we can append 0 without conflict?

**Ans**: That will be taken care when we append ‘10’ to all the (n-2)length strings.