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

Home > Numbers > Sequences
Surprised? (Posted on 2012-12-15) Difficulty: 3 of 5
How many binary sequences of length n exist , with no successive zeroes within the sequence?
Please provide the formula, its proof and the values for n=5, n=10 and n=50.

See The Solution Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution No Subject | Comment 1 of 2

Call the number of strings of length n f(n).

For n=1, there are two such sequences: 0 and 1.

From then on, it's best to start by considering strings (as it's more convenient to leave out commas and just make strings of the sequences) ending with zero separately from strings ending with 1. The n+1 length strings that end in 1 are in 1-to-1 correspondence with the entire set of n-length strings, while the n+1 length strings that end in zero correspond to the n-length strings that end in 1. Introducing a second parameter to the f function for these partial counts (ending in zero or 1) f(n+1,0)=f(n,1) and f(n+1,1) = f(n) = f(n,0) + f(n,1).

So f(2) = f(2,0) + f(2,1) = f(1,1) + f(n) = 1 + 2 = 3.

Let's take successive values:

 n             f(n,0)         f(n,1)           f(n)
 1               1               1               2
 2               1               2               3
 3               2               3               5
 4               3               5               8
 5               5               8              13
 6               8              13              21
 7              13              21              34
 8              21              34              55
 9              34              55              89
10              55              89             144

It seems apparent that f(n) = F(n+1) where F(x) represents the xth Fibonacci number. This follows from the fact that a given number in the f(n) column finds its way, for the next n, in the f(n,1) column as any n-length string corresponds to an n+1-length string ending in a 1.  This number is then the same for f(n+2,0) as only the strings ending in 1 can propagate to the next value of n.

In this manner, f(n,0) is merely F(n-1) while f(n,1)=F(n), making the total f(n) = F(n-1) + F(n), which is by definition the Fibonacci sequence, so long as it is true for one starting value, and we can take that to be n=1 or any particular line here, and use the induction described to prove for the higher values of n.


  Posted by Charlie on 2012-12-15 17:54:37
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 (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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