I accidentally derived a formula for the Fibonacci Sequence

Last night my brother pitched me this math problem over dinner (which he later revealed came from this video). It goes something like this:

There is a flight of $n$ stairs in front of you.

You can only ascend in steps of 1 or 2 stairs.

How many different ways are there for you to go up the stairs?

For the rest of the article, I will go over my thought process (and stupidity) when solving the problem. Enjoy!

First, I drew out some stairs and some tables to get base-cases and a feel for the problem.

# of stairs	# of ways to ascend
1	1
2	2
3	3
4	5
5	8

Now, if you already see a familiar pattern in these numbers, shh! I somehow failed to see it, although it's obvious in hindsight, but I guess that's a good thing since it led me to the results of this article.

Next, I decided to take a look at the lengths of jumps. I made a list of numbers, where each number represented a jump of that height. So, for example, one ascent of the 10-stair staircase example might look like:

[1 2 2 1 2 1 1]

Since this list encodes a sequence of jumps that would climb 10 stairs, it's trivial to say the list must sum to 10.

This allowed me to rewrite the problem as the following:

For any $n$ , how many unique sequences of 2s and 1s add to $n$ ?

While this was definitely more abstract, it reframed the problem using numbers, which I could play with using math.

Next, since I had no idea how I would go about counting the sequences, I looked at how I could group them, in hoping that would make them easier to count.

Arbitrarily, I decided to group the sequences by how many 2s were in them.

For the 5-stair staircase example, all of the possible sequences of 1s and 2s that sum to 5 look like:

[1 1 2 1]
[2 1 2]
[1 2 1 1]
[1 1 1 1 1]
[2 1 1 1]
[1 2 2]
[1 1 1 2]
[2 2 1]

Grouping each sequence by the number of 2s in it yields the table:

# of 2s ( $t$ )	0	1	2	3
sequences	`[1 1 1 1 1]`	`[2 1 1 1] [1 2 1 1] [1 1 2 1] [1 1 1 2]`	`[1 2 2] [2 1 2] [2 2 1]`
length of sequences ( $k_{t}$ )	5	4	3
# of sequences ( $m_{t}$ )	1	4	3	0

This adds to a grand total of 8 sequences for a 5-stair staircase.

From the table, I made a few insights:

Any two sequences with the same number of 2s have the same length. This made sense because sequences with the same number of 2s always have the same number of 1s, so their total length must be the same.
$k$ seemed to follow the pattern $k = n - t$ . This made sense because with each introduction of one more 2, then length of the list must decrease by 1 to still sum to 5.
The pattern $k = n - t$ only worked for $2 t \leq n$ . This made sense because if the sequence must sum to 5, then it can not contain 3 2s. This allowed me to define a general maximum for $t$ . $t_{\max} = ⌊ \frac{n}{2} ⌋$

Okay, so now that I had a way to split the sequences into pieces, I just needed a way to count the number of sequences for each value of $t$ , and sum those together.

The sum was the easy part. I knew the final number would be the the sum of all of the $m_{t}$ s, or:

\sum_{t = 0}^{t_{\max}} m_{t}

Plugging in our definition for $t_{\max}$ ,

\sum_{t = 0}^{⌊ \frac{n}{2} ⌋} m_{t}

After thinking about the sequences for a while, I realized that the number of sequences boils down to the question "how many ways can you uniquely arrange a list of $t$ special items out of $k$ total items?"

Then I realized: this was a combinatorics problem! Specifically, I remembered the Binomial Coefficient, or " $n$ choose $k$ ", which counts "the number of ways to choose a subset of k elements from a larger set of n elements."

Each sequence of length $k$ contained exactly $t$ 2s. So counting the number of sequences $m_{t}$ for some $t$ was equivelant to counting the number of ways to choose $t$ elements from a larger set of $k$ elements. By this definition,

m_{t} = (\binom{k}{t})

Plugging in the prior definition for $k$ , and using the summation from above, I arrived at a final equation:

f (n) = \sum_{t = 0}^{⌊ \frac{n}{2} ⌋} (\binom{n - t}{t})

Yay!

Okay, if you didn't see the pattern from the beginning, [1 2 3 5 8] is the Fibonacci Sequence, starting at the 2nd element. You might be more familiar with it starting from the 1st element [1 1 2 3 5 8 ...].

So we really just derived a formula for the $n + 1$ th Fibonacci number!

When I first learned this, I thought I was some kind of genius or something, but a quick check on ProofWiki told that a very similar function was already discovered in 1971, so I guess I'm 55 years late to the party.

The formula on ProofWiki is for the $n$ th fibonacci number, so here's how you could arrive at the real Fibonacci Number as Sum of Binomial Coefficients function:

Begin with the derived formula, replacing $n$ for $a$ to avoid variable conflicts later.

f (a) = \sum_{t = 0}^{⌊ \frac{a}{2} ⌋} (\binom{a - t}{t})

Since this is really for the $n + 1$ th Fibonacci number, substitute $a = n - 1$ .

f (n) = \sum_{t = 0}^{⌊ \frac{n - 1}{2} ⌋} (\binom{n - t - 1}{t})

The original function uses $k$ instead of $t$ .

f (n) = \sum_{k = 0}^{⌊ \frac{n - 1}{2} ⌋} (\binom{n - k - 1}{k})

This is the exact same function that appears on ProofWiki!