Counting binary strings of length n with no two adjacent 1's 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?

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? 
