0
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .