Sequence of ones a zeroes This question was found in a CSAT entrance exam for Cambridge computer science course, and I had a look at it but I'm not really sure where to start with it:
Given a sequence of zeros and ones of length $n$, let $L_n$ be the number of sequences that have no adjacent zeros. Give a recursive formula for $L_n$
 A: I hope it can help you
let $L_{n}$ be the number of bit strings of length n that do not have two consecutive zeros.
To obtain a recurrence relation for $L_{n}$ , note that the number of bit strings of length n that do not have two consecutive $0$s equal the number of such bit strings ending in $0$ plus the number of bit strings ending in $1$.
We can assume that n is greater than or equal to three, so that only bit strings of length three or more need be considered.
The valid bit strings of length n ending with $1$ are precisely the bits strings of length $n - 1$ with no consecutive zeros with a $1$ appended onto the end. 
Consequently, there are $L_{n−1}$ such bit strings. 
Valid bit strings of length n ending in a zero must have $1$ as their second to last bit; otherwise, they would end with a pair of $0$s, and that just can’t be.
It follows that the legal bit strings of length n ending in zero are the valid bit strings of length $n - 2$ with '$10$' tacked on to the end. Consequently, there are $L_{n−2}$ such bit strings.
We conclude that, for n greater than or equal to $3$, that:
$L_{n} =L_{n−1}+L_{n−2}$
The initial conditions are $L_{1} = 2$ , since both bit strings of length one, $0$ and $1$, do not have two consecutive
$0$s, and $L_{2} = 3$ . 
To obtain $L_{5}$ , we simply use the recurrence relation three more times to find that:
$L_{3} =L_{2}+L_{1} =3+2=5 $
$L_{4} =L_{3} +L_{2} =5+3=8$
$L_{5} =L_{4}+L_{3} =8+5=13$

Recurrence Relations examples
A: Let $Z_{n}$ be the number of sequences length $n$ with no adjacent zeros that end in zero. Let $O_n$ be the number with no adjacent zeros that end in one. Now, consider taking length $n-1$ strings and adding on one more digit to get a new string with no adjacent zeros. You can add a one to either type, so $$ O_n = O_{n-1} + Z_{n-1}$$ but you can only add a zero to the strings that end in one (or you'd be making an adjacent zero) so $$ Z_n = O_{n-1}$$ Combining gives the fibonacci reccurance $$ O_{n} = O_{n-1} + O_{n-2}.$$
We have $O_1 = 1$, $O_2 = 2$ so $O_n = F_{n+1}$ and $Z_n = O_{n-1} = F_{n},$ so the total number is $$L_n = O_n + Z_n = F_{n+1} + F_{n} = F_{n+2} $$
