Recurrence relation [closed]

Question

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}?$

• A. $a_{n}=a_{n-1}+2a_{n-2}$
• B. $a_{n}=a_{n-1}+a_{n-2}$
• C. $a_{n}=2a_{n-1}+a_{n-2}$
• D. $a_{n}=2a_{n-1}+2a_{n-2}$

Comments

https://gateoverflow.in/39636/gate2016-1-2

Check the last answer  of above question

---

The best way to solve such questions is by taking the example of strings and try for neglecting the options.

1 bit binary strings : {0,1}

2 bit binary strings :{00.01,10,11}

3-bit binary strings:{000,001,010,011,100,101,110,111}

a₁=2

a₂=3

a₃=5

Now try to calculate a₃ from the given options..

A) a_n =a_n-1 + 2a_n-2       a₃ = a₂ + 2a₁  = 3 + 2*2 =7

B) a_n = a_n-1 + a_n-2         a₃ = a₂ + a₁ = 3 + 2 = 5

C) a_n = 2a_n-1 + a_n-2      a₃ = 2*a₂ + a₁   = 2*3 + 2 =8

D) a_n =2a_n-1 +2a_n-2      a₃ = 2*a₂ + 2*a₁ =2*3 + 2*2 = 10

Only B is Correct....

---

Yes i solve this way

can i write $a_{0}=0$

             So$,a_{0}=1$

this is right??