in Combinatory edited by
9,399 views
45 votes
45 votes

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}$
in Combinatory edited by
9.4k views

2 Comments

7
7

$\color{red}{\text{Detailed Video Solution of this GATE question}}$(Click Below):

Detailed Video Solution

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

Complete Recurrence Relations Playlist 

5
5

4 Answers

81 votes
81 votes
Best answer

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

edited by

4 Comments

a suffix n is fibonacci series
0
0
Sir, why can't we take a0=0. Please explain
0
0
It is evident that a3 = a1 + a2
Similarly, an = an-1 + an-2
0
0
13 votes
13 votes

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. 

2 Comments

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

What do you mean by this line?!

0
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) ...

0
0
3 votes
3 votes
$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}$)
2 votes
2 votes

[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 ‘0’ to all the (n-1)length strings and ‘01’ 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 ‘00’ to all (n-2) length strings. Yes, but that case will be covered by appending ‘0’ to all (n-1)length strings.

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

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

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

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

Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true