![Question 8039 – GATE 2016 [Set-1]](https://solutionsadda.in/wp-content/uploads/2019/05/green-new-logo.png){kind=logo}
Question 2751 – UGC NET CS 2017 Jan -paper-2
January 22, 2024Question 8059 – GATE 2016 [Set-1]
January 22, 2024Question 8039 – GATE 2016 [Set-1]
Let an be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for an?
Correct Answer: B
Question 12 Explanation:
an = number of n-bit strings, that do not have two consecutive 1’s.
If n=1, we have {0,1}
# Occurrences = 2
If n=2, we have {00,01,10}
# Occurrences = 3
If n=3, we have {000,001,010,100,101}
# Occurrences = 5
It is evident that a3 = a1 + a2
Similarly, an = an-1 + an-2
If n=1, we have {0,1}
# Occurrences = 2
If n=2, we have {00,01,10}
# Occurrences = 3
If n=3, we have {000,001,010,100,101}
# Occurrences = 5
It is evident that a3 = a1 + a2
Similarly, an = an-1 + an-2
an = a(n-1) + 2a(n-2)
an = a(n-1) + a(n-2)
an = 2a(n-1) + a(n-2)
an = 2a(n-1) + 2a(n-2)