· A recurrence relation is an equation that recursively defines a sequence: each term of the sequence is defined as a function of the preceding terms.

· The Fibonacci numbers are the numbers in the following sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, …

In mathematical terms, the sequence F_n of Fibonacci numbers is defined by the recurrence relation

with seed values

· Your question requires us to find the recurrence relation for the number of binary sequences of length n that have no consecutive 0’s.

· Let a_n be the number of such sequences with length n, where n>0.

· It’s easy to figure out a₁and a₂:  a₁=2 (0 or 1) and a₂=3 (10, 11, 01).

· There are two cases for a_n:

1. if the nth symbol is 1: the preceding n-1 symbols sequence is counted in a_n-1

2. if the nth symbol is 0: a_n ends in 10 and the preceding n-2 symbols sequence is counted in a_n-2.

· Therefore, a_n=a_n-1+a_n-2.

· a_n produces the following series:                  2, 3, 5, 8, 13, etc.

· Compare this to the Fibonacci series: 1, 1, 2, 3, 5, 8, 13, etc.

· As you can see from the above two series, a_n=F(n+2)