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 |
No Subject
