All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 2Z out (Posted on 2018-10-05)
Provide a formula for number of binary sequences of length n that have no consecutive 0's.

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 1 of 2
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

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: