I accidentally derived a formula for the Fibonacci Sequence

+ + 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

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.

[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]
+			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]
@@ -57,247 +57,262 @@
 [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.
+			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} - ⌋ - -$ 
-            
-        
-        
+			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} - -$ 
+			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}^{+} + 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}^{-} +			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!
-        
+					
+						(
+						
+							
+								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}^{-} - - (- \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!
-

# 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

# 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


-
-
\ No newline at end of file
+			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!
+