Provide a formula for number of binary sequences of length n that have no consecutive 0's.
Keeping separate track of strings ending in 1 and strings ending in 0:
length ending in 1 ending in 0 total
1 1 1 2
2 2 1 3
3 3 2 5
4 5 3 8
5 8 5 13
6 13 8 21
Each entry in the first result column is the sum of the number above it with the number in the next column in the preceding row. Each entry in the second result column repreats the entry in the previous row of the previous column.
All three of the result columns show the Fibonacci sequence.
The formula sought is the total column, showing F(n+1), having been arrived at by adding F(n) and F(n-1).
Correction: Since 2 is the third, rather than the second, Fibonacci number, the answer is F(n+2).
Edited on October 6, 2018, 9:29 am
|
|
Posted by Charlie
on 2018-10-05 14:52:53 |
solution
