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

 Surprised? (Posted on 2012-12-15)
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.)
 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              8910              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

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

Chatterbox: