I accidentally derived a formula for the Fibonacci Sequence

Published June 11, 2026

+ +

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
	`[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} + ⌋ + +$ +

+ +

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 is the easy part. I knew the final number would be the the sum of all of the $m_{t}$ s, or:

+ + +_{\sum}^{+} + m_{t} + +

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

+ + +_{\sum}^{+} + 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 +} +) + +

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

+ f (n) + = + + +_{\sum}^{+} +
+ + (+ \binom{+}{+ n + - + 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}^{+} + + (+ \binom{+}{a - t} +) + + +

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

+ f (n) + = + + +_{\sum}^{+} + + (+ \binom{+}{n - t - 1} +) + + +

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

+ f (n) + = + + +_{\sum}^{+} + + (+ \binom{+}{n - k - 1} +) + + +

This is the exact same function that appears on ProofWiki!