Why is the fibonacci sequence generated in this "game"?

Okay, lets say you choose a number N.How many possible sequences are there from 0 to N such as the next term is 1 or 2 more than the term before. For example, choose N=3 Than there are 3 possible sequences: 0,1,2,3 0,2,3 0,1,3. If N=4 than there are 5 possibilities: 01234 0134 0234 024 0124. If N=0 there there is 1 possibility 0, if N=1 P=1, if N=2 P=2 and so on. The sequence of the number of possible sequences is: 112358... which is the Fibonacci sequence, but why is it generated here?

2 Answers

Let $$A_n$$ be the number of "good" sequences for a given $$n$$. Any such sequence either contains $$n$$ or it does not. If it does not then it is a contributor to $$A_{n-1}$$. And clearly every contributor to $$A_{n-1}$$ is a contributor to $$A_n$$. If it does then the sequence with $$n$$ deleted must be a contributor to $$A_{n-2}$$. And, conversely, if you take any contributor to $$A_{n-2}$$ then you get a contributor to $$A_n$$ by adjoining $$n$$. Thus $$A_n=A_{n-1}+A_{n-2}$$ which is the defining recursion for the Fibonacci numbers. To prove equality you need only check the initial conditions.

Let's look at the number of sequences that can end with, say, $$5$$, and see if we can recognize where the Fibonacci recurrence appears.

Any sequence that ends with $$5$$ will have the second-to-last term either $$3$$ or $$4$$. This partitions the set of sequences that end in $$5$$ into two sets: the ones that end in $$35$$ and the ones that end in $$45$$. How large are each of those? Well, the first set is just all sequences that end in $$3$$, with a $$5$$ at the end, while the second set is all sequences that end in $$4$$, with a $$5$$ at the end. So the number of sequences that end in $$5$$ is equal to the number of sequences that end in $$3$$ plus the number of sequences that end in $$4$$.

There is, of course, nothing special about $$5$$ here. For any $$n\geq 2$$, the number of sequences that end in $$n$$ is equal to the number of sequences that end in $$n-2$$ plus the number of sequences that end in $$n-1$$, since

• You can take any such sequence and put an $$n$$ at the end of it
• Those are all the sequences that end with $$n$$
• There is no overlap between the two