1″ and 2″ Jumps → Fibonacci

Count the number of sequences of 1-unit and 2-unit jumps whose total distance is \(n\).

1. Define the problem

Let \(a_n\) be the number of ordered sequences consisting of jumps of size \(1\) and \(2\) whose total is \(n\).

\[ a_n = a_{n-1} + a_{n-2}, \qquad a_0 = 1,\quad a_1 = 1 \]

Why? Every valid sequence must end in exactly one of two ways:

2. Interactive example

n = 5
\(a_n =\) 8

3. Why does the recurrence work?

Sequences ending in 1

Remove the final \(1\). The remaining sequence must sum to \(n-1\).

Sequences ending in 2

Remove the final \(2\). The remaining sequence must sum to \(n-2\).

4. Compare with Fibonacci

\(n\) 0 1 2 3 4 5 6 7 8
\(a_n\)
\(F_{n+1}\)
\[ 1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\ldots \]

5. Why exactly Fibonacci?

The standard Fibonacci sequence satisfies

\[ F_{k}=F_{k-1}+F_{k-2}, \qquad F_0=0,\quad F_1=1. \]

Therefore

\[ F_1=1,\qquad F_2=1. \]

These match our initial values

\[ a_0=1,\qquad a_1=1. \]

Both sequences have the same initial values and obey the same recurrence, except that the Fibonacci indices are shifted by one.

Therefore, \[ \boxed{a_n = F_{n+1}}. \] For example, \[ a_5 = 8 = F_6. \]