The Gateway to Computer Science Excellence
+27 votes
3.1k 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}$
in Combinatory by Loyal (7.2k points)
edited by | 3.1k views

3 Answers

+61 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$

by Veteran (56.6k points)
edited by
0
Can you please explain more.
+13

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
+8 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. 

by Loyal (9.6k 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)
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
50,650 questions
56,192 answers
193,988 comments
94,861 users