3.6k views

Let $a_n$ be the number of $n$-bit strings that do NOT contain two consecutive $1's$. Which one of the following is the recurrence relation for $a_n$?

1. $a_n = a_{n-1}+ 2a_{n-2}$
2. $a_n = a_{n-1}+ a_{n-2}$
3. $a_n = 2a_{n-1}+ a_{n-2}$
4. $a_n = 2a_{n-1}+ 2a_{n-2}$

edited | 3.6k views

\begin{array}{|c|l|l|l|} \hline \textbf{n} & \text{n-bit strings that do NOT}\\ &\text{ contain consecutive}\;11& \textbf{a_{n}} & \textbf{\text{those containing}\; 11} \\\hline \textbf{1} & \text{\{0,1\}}& \text{a_{1}=2} & \text{\{\}}\\\hline \textbf{2} & \text{\{00,01,10\}}& \text{a_2=3} & \text{\{11\}}\\\hline \textbf{3} & \text{\begin{align}\{000,001,010,&100,101\}\end{align}}& \text{a_{3}=5} & \text{\{011,110,111\}}\\\hline \end{array}

$a_n=a_{n-1} +a_{n-2}$

Rest of the options are already out.

Alternatively, we can get a string in $a_n$ by appending "$0$" to any string in $a_{n-1}$ as well as by appending "$01$" to any string in $a_{n-2}$ and the two cases are mutually exclusive (no common strings) as well as exhaustive (covers all cases).

Correct Answer: $B$

by Veteran (57.1k points)
edited
0
Can you please explain more.
+18

For every string of length n to start with a 0 , we can append every string of length n-1 , and have no problem.
And For every string of length n to start with a 1, we can only append strings starting with 0 of length n-1 , which is the same as number of strings of length n-2.
Hence , an=an-1+an-2

+1
Note that here by append Praveen means to add 0 on the right hand side of recursive string $a_{n-1}$, and to add 01 on RHS of recursive string $a_{n-2}$. Alternatively you can add 0 on LHS of string $a_{n-1}$ or add 10 on LHS of string $a_{n-2}$.
0
a suffix n is fibonacci series
0
Sir, why can't we take a0=0. Please explain
0
It is evident that a3 = a1 + a2
Similarly, an = an-1 + an-2

The least value of 'n' for the recursion would be 3.

For n = 1, number of strings = 2 (0, 1)

For n = 2, number of strings = 3 (00, 01, 10)

For n = 3, number of strings = 5 (000, 001, 010, 100, 101)

For n = 4, number of strings = 8 (0000, 0001, 0010, 0100, 1000, 0101, 1010, 1001) ...

This seems to follow Fibonacci series and the recurrence relation for it is an = an−1 + an−2. Thus, B is the correct choice.

by Boss (10k points)
0

### The least value of 'n' for the recursion would be 3.

What do you mean by this line?!

0

The least value of 'n' for the recursion would be 3.

I think for n=1 and n=2 the values are not repeating. But for n=3 and above the 0's and 1's are repeating recursively!!

For n = 3, number of strings = 5 (000, 001, 010, 100, 101)

For n = 4, number of strings = 8 (0000, 0001, 0010, 0100, 1000, 0101, 1010, 1001) ...

+1 vote
$a_{n} = a_{n}^{(0)} + a_{n}^{(1)}$ i.e nth term can be either 0 or 1

=  $a_{n-1} + a_{n-1}^{(0)}$  i.e if nth term contains 0 then (n-1)th term can contain either 0 or 1(for that $a_{n-1}$ ) and if                                                                     nth term contain 1 then (n-1)th term has to be 0 (for that $a_{n-1}^{0}$)

= $a_{n-1} + a_{n-2}$   // here also if (n-1)th term contain 0 then (n-2)th term can be either 0 or 1 (for that $a_{n-2}$)
by Active (1.1k points)