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

- -

- The default networking stack on NixOS uses NetworkManager. - While it's a great choice for many users, I prefer a lighter setup built around systemd-networkd, systemd-resolved, and iwd. It integrates well with the rest of the systemd stack, has fewer moving pieces, and exposes powerful networking features without an additional network management daemon. -

- -

- This article focuses on laptops that connect to wifi. - If you're configuring a server, you probably don't need iwd at all; systemd-networkd and systemd-resolved are usually sufficient. -

- -

The default stack

If not configured otherwise, NixOS uses the following stack:

NetworkManager for wifi
dhcpcd for DHCP
resolvconf for DNS
a "legacy script based system" for network configuration^[1]

We'll be replacing it with:

iwd for wifi
systemd-networkd for DHCP and network configuration
systemd-resolved for DNS

- This has a few benefits. - Firstly, switching to resolved allows you to enable features like encrypted DNS over TLS (DoT) and DNSSEC validation, which reduces the potential for DNS spoofing and man-in-the-middle attacks^[2]. - Additionally, the default stack uses 3 extra packages (NM, dhcpcd, resolvconf) and some bash scripts, while this setup only uses one extra package (iwd). - Also, I'm kind of a systemd nerd, and this is a way to dig into systemd a bit more. -

- -

So the first thing we can do is disable all of the default stuff:

{
+	
+		Minimal Laptop Networking with NixOS
+		
+		
+	
+	
+		
+			
+
+			
+				The default networking stack on NixOS uses NetworkManager.
+				While it's a great choice for many users, I prefer a lighter setup built around systemd-networkd, systemd-resolved, and iwd. It integrates well with the rest of the systemd stack, has fewer moving pieces, and exposes powerful networking features without an additional network management daemon.
+			
+
+			
+				This article focuses on laptops that connect to wifi.
+				If you're configuring a server, you probably don't need iwd at all; systemd-networkd and systemd-resolved are usually sufficient.
+			
+
+			
+
+			The default stack
+			If not configured otherwise, NixOS uses the following stack:
+			
+				NetworkManager for wifi
+				dhcpcd for DHCP
+				resolvconf for DNS
+				a "legacy script based system" for network configuration^[1]
+			
+			We'll be replacing it with:
+			
+				iwd for wifi
+				systemd-networkd for DHCP and network configuration
+				systemd-resolved for DNS
+			
+			
+				This has a few benefits.
+				Firstly, switching to resolved allows you to enable features like encrypted DNS over TLS (DoT) and DNSSEC validation, which reduces the potential for DNS spoofing and man-in-the-middle attacks^[2].
+				Additionally, the default stack uses 3 extra packages (NM, dhcpcd, resolvconf) and some bash scripts, while this setup only uses one extra package (iwd).
+				Also, I'm kind of a systemd nerd, and this is a way to dig into systemd a bit more.
+			
+
+			So the first thing we can do is disable all of the default stuff:
+			{
   networking = {
     networkmanager.enable = false;
     dhcpcd.enable = false;
@@ -55,14 +52,14 @@
   };
 }
 
-        And let's get to configuring!
+			And let's get to configuring!
 
-        iwd
-        
-            First up is iwd.
-            The important parts of the configuration are delegating network configuration to networkd, delegating name resolution (DNS) to resolved, and configuring MAC randomization for some extra privacy.
-        
-        {
+			iwd
+			
+				First up is iwd.
+				The important parts of the configuration are delegating network configuration to networkd, delegating name resolution (DNS) to resolved, and configuring MAC randomization for some extra privacy.
+			
+			{
   networking.wireless.iwd = {
     enable = true;
     settings = {
@@ -76,28 +73,28 @@
   };
 }
 
-    
-        At this point, we don't have any network configuration yet, so internet access won't work. However, you can verify that iwd is functioning correctly:
-    
-    
-        iwctl station wlan0 scan: Scans for new wifi networks
-        iwctl station wlan0 get-networks: lists the networks that it found
-        iwctl station wlan0 connect "<SSID>": connects to the network, prompting for a PSK if necessary
-    
-
-    systemd-networkd
-    
-        Next up is systemd-networkd.
-        Networkd has lots of advanced options for things like static IP config, Wireguard tunnels, VLANs, domain-based DNS routing, and more.
-        However, here we'll just do a basic configuration to enable DHCP and deny DHCP-advertised DNS.
-    
-    
-      why disable DHCP-advertised DNS?
-      By default, most networks advertise their own DNS resolver via DHCP.
-      Since we'll configure our own encrypted upstream DNS servers in the next section, we tell networkd to ignore the ones provided by the network.
-    
-
-    {
+			
+				At this point, we don't have any network configuration yet, so internet access won't work. However, you can verify that iwd is functioning correctly:
+			
+			
+				iwctl station wlan0 scan: Scans for new wifi networks
+				iwctl station wlan0 get-networks: lists the networks that it found
+				iwctl station wlan0 connect "<SSID>": connects to the network, prompting for a PSK if necessary
+			
+
+			systemd-networkd
+			
+				Next up is systemd-networkd.
+				Networkd has lots of advanced options for things like static IP config, Wireguard tunnels, VLANs, domain-based DNS routing, and more.
+				However, here we'll just do a basic configuration to enable DHCP and deny DHCP-advertised DNS.
+			
+			
+				why disable DHCP-advertised DNS?
+				By default, most networks advertise their own DNS resolver via DHCP.
+				Since we'll configure our own encrypted upstream DNS servers in the next section, we tell networkd to ignore the ones provided by the network.
+			
+
+			{
   systemd.network = {
     enable = true;
 
@@ -113,27 +110,28 @@
   networking.useNetworkd = true;
 }
 
-    
-      The name = "wl*" refers to the network interface name that this configuration applies to.
-      According to the systemd docs, wireless LAN devices should start with the two-character prefix "wl"^[3].
-      Here we use a glob (*) to match all wireless interfaces.
-    
-
-    You can verify that your configuration worked with a few commands:
-    
-      ip addr: make sure that there's an IP address associated with your wireless interface. That means DHCP is working.
-      networkctl status: make sure there's no significant errors in the logs.
-    
-
-    systemd-resolved
-    
-        Now all we have left is DNS configuration, then we're done.
-        This is probably the part where you can nerd out the hardest, but I try to keep it pretty minimal.
-        The important parts are selecting upstream DNS servers that support secure DNS protocols (like DNS over TLS and DNSSEC) and that respect your privacy.
-        For these reasons, I use quad9, but do your own research and find the best upstream DNS server for you!
-        Some other options include Cloudflare DNS, Google's DNS, or AdGuard Public DNS.
-    
-    {
+			
+				The name = "wl*"
+				refers to the network interface name that this configuration applies to.
+				According to the systemd docs, wireless LAN devices should start with the two-character prefix "wl"^[3].
+				Here we use a glob (*) to match all wireless interfaces.
+			
+
+			You can verify that your configuration worked with a few commands:
+			
+				ip addr: make sure that there's an IP address associated with your wireless interface. That means DHCP is working.
+				networkctl status: make sure there's no significant errors in the logs.
+			
+
+			systemd-resolved
+			
+				Now all we have left is DNS configuration, then we're done.
+				This is probably the part where you can nerd out the hardest, but I try to keep it pretty minimal.
+				The important parts are selecting upstream DNS servers that support secure DNS protocols (like DNS over TLS and DNSSEC) and that respect your privacy.
+				For these reasons, I use quad9, but do your own research and find the best upstream DNS server for you!
+				Some other options include Cloudflare DNS, Google's DNS, or AdGuard Public DNS.
+			
+			{
   networking.nameservers = [
     "9.9.9.9#dns.quad9.net"
     "149.112.112.112#dns.quad9.net"
@@ -151,23 +149,25 @@
   };
 }
 
-        You can verify your DNS configuration by using the resolvectl status command or by just opening a website.
-
-        P.S. Captive Portals
-        
-            Captive portals are those wifi login pages that pop up when you connect to some public wifi networks.
-            Some captive portals don't behave correctly when you're using an encrypted third-party DNS server instead of the network's advertised resolver.
-            To get around this, I use Captive Browser (nixpkgs), which launches an instance of Chromium through a SOCKS5 proxy, avoiding the system DNS configuration altogether.
-            This allows you to access a captive portal for long enough to log in and gain internet access.
-            Pretty neat!
-        
-
-        P.P.S. I miss nm-applet
-        
-          Probably the biggest downside to this setup is the lack of desktop integration.
-          GNOME and Plasma only support NetworkManager in their network configuration menu, so you're kinda out of luck.
-          For tiling window manager people, I can recommend iwmenu, which is a launcher (dmenu, rofi, fuzzel)-based menu for connecting to wifi networks via iwd.
-        
-    

-
-
\ No newline at end of file
+			You can verify your DNS configuration by using the resolvectl status
+				command or by just opening a website.
+
+			P.S. Captive portals
+			
+				Captive portals are those wifi login pages that pop up when you connect to some public wifi networks.
+				Some captive portals don't behave correctly when you're using an encrypted third-party DNS server instead of the network's advertised resolver.
+				To get around this, I use Captive Browser
+				(nixpkgs), which launches an instance of Chromium through a SOCKS5 proxy, avoiding the system DNS configuration altogether.
+				This allows you to access a captive portal for long enough to log in and gain internet access.
+				Pretty neat!
+			
+
+			P.P.S. I miss nm-applet
+			
+				Probably the biggest downside to this setup is the lack of desktop integration.
+				GNOME and Plasma only support NetworkManager in their network configuration menu, so you're kinda out of luck.
+				For tiling window manager people, I can recommend iwmenu, which is a launcher (dmenu, rofi, fuzzel)-based menu for connecting to wifi networks via iwd.
+			
+

The default stack

The default stack

iwd

iwd

systemd-networkd

systemd-networkd

systemd-resolved

systemd-resolved

P.S. Captive Portals

P.P.S. I miss nm-applet

P.S. Captive portals

P.P.S. I miss nm-applet

Math basis

First Combinators

Under