GATE Computer Science (CS) 2016 Shift 1 Solved Paper

Question : 12 of 65

Marks: +1, -0

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