[Math] Counting binary strings of length n with no two adjacent 1’s

combinatorics

I need to calculate the total number of possible binary strings of length $n$ with no two adjacent 1's.

Eg.
for n = 3
f(n) = 5
000,001,010,100,101

How do I solve it?

Best Answer

Hint: Use a recurrence relation. What if the string with $k$ bits starts with a 1, how many possibilities gives this for strings with $k+1$ bits? If the string with $k$ bits starts with a 0, how many possibilities gives this for strings with $k+1$ bits?