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

Home > Numbers > Sequences
2Z out (Posted on 2018-10-05) Difficulty: 3 of 5
Provide a formula for number of binary sequences of length n that have no consecutive 0's.

No Solution Yet Submitted by Ady TZIDON    
Rating: 5.0000 (1 votes)

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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (11)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information