diff options
Diffstat (limited to 'fib.html')
| -rw-r--r-- | fib.html | 318 |
1 files changed, 318 insertions, 0 deletions
diff --git a/fib.html b/fib.html new file mode 100644 index 0000000..1d38013 --- /dev/null +++ b/fib.html @@ -0,0 +1,318 @@ +<!DOCTYPE html> +<html> +<head> + <title>I accidentally derived a formula for the Fibonacci Sequence</title> + <link rel="stylesheet" href="prose.css"> + <style> + table { + border-collapse: collapse; + margin: 0 auto; + th { + color: #e6e6e6; + text-align: center; + border: solid; + padding: 0 1.5ch; + border-width: 0 0 1px 0; + + &[scope="row"] { + border-width: 0 1px 0 0; + } + } + td { + color: #00ff78; + text-align: center; + padding: 0 1.5ch; + } + } + </style> +</head> +<body> + <div class="content"> + <h1>I accidentally derived a formula for the Fibonacci Sequence</h1> + <p class="comment">Published June 11, 2026</p> + <hr> + + <p>Last night my brother pitched me this math problem over dinner (which he later revealed came from <a href="https://www.youtube.com/watch?v=XeOTNEb-QsM">this video</a>). It goes something like this:</p> + <blockquote> + <p>There is a flight of <math><mi>n</mi></math> stairs in front of you.</p> + <p>You can only ascend in steps of 1 or 2 stairs.</p> + <p>How many different ways are there for you to go up the stairs?</p> + </blockquote> + <p>For the rest of the article, I will go over my thought process (and stupidity) when solving the problem. Enjoy!</p> + <hr> + <p>First, I drew out some stairs and some tables to get base-cases and a feel for the problem.</p> + <table> + <thead> + <tr> + <th><strong># of stairs</strong></th> + <th><strong># of ways to ascend</strong></th> + </tr> + </thead> + <tbody> + <tr><td>1</td><td>1</td></tr> + <tr><td>2</td><td>2</td></tr> + <tr><td>3</td><td>3</td></tr> + <tr><td>4</td><td>5</td></tr> + <tr><td>5</td><td>8</td></tr> + </tbody> + </table> + + <p>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.</p> + <p>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:</p> + <pre><code>[1 2 2 1 2 1 1]</code></pre> + <p>Since this list encodes a sequence of jumps that would climb 10 stairs, it's trivial to say the list must sum to 10.</p> + <p>This allowed me to rewrite the problem as the following:</p> + <blockquote> + <p>For any <math><mi>n</mi></math>, how many unique sequences of 2s and 1s add to <math><mi>n</mi></math>?</p> + </blockquote> + <p>While this was definitely more abstract, it reframed the problem using numbers, which I could play with using math.</p> + <hr> + + <p>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.</p> + <p>Arbitrarily, I decided to group the sequences by how many 2s were in them.</p> + <p>For the 5-stair staircase example, all of the possible sequences of 1s and 2s that sum to 5 look like:</p> + <code>[1 1 2 1]<br>[2 1 2]<br>[1 2 1 1]<br>[1 1 1 1 1]<br>[2 1 1 1]<br>[1 2 2]<br>[1 1 1 2]<br>[2 2 1]</code> + <p>Grouping each sequence by the number of 2s in it yields the table:</p> + <table> + <tbody> + <tr> + <th scope="row"># of 2s (<math><mi>t</mi></math>)</th> + <td>0</td> + <td>1</td> + <td>2</td> + <td>3</td> + </tr> + <tr> + <th scope="row"></th> + <td><code>[1 1 1 1 1]</code></td> + <td><code>[2 1 1 1]<br>[1 2 1 1]<br>[1 1 2 1]<br>[1 1 1 2]</code></td> + <td><code>[1 2 2]<br>[2 1 2]<br>[2 2 1]</code></td> + <td></td> + </tr> + <tr> + <th scope="row">length of sequences (<math><msub><mi>k</mi><mi>t</mi></msub></math>)</th> + <td>5</td> + <td>4</td> + <td>3</td> + </tr> + <tr> + <th scope="row"># of sequences (<math><msub><mi>m</mi><mi>t</mi></msub></math>)</th> + <td>1</td> + <td>4</td> + <td>3</td> + <td>0</td> + </tr> + </tbody> + </table> + <p>This adds to a grand total of 8 sequences for a 5-stair staircase.</p> + + <p>From the table, I made a few insights:</p> + <ul> + <li><p> + 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. + </p></li> + <li><p> + <math><mi>k</mi></math> seemed to follow the pattern <math><mi>k</mi><mo>=</mo><mn>n</mn><mo>-</mo><mn>t</mn></math>. + 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. + </p></li> + <li><p> + The pattern <math><mi>k</mi><mo>=</mo><mn>n</mn><mo>-</mo><mn>t</mn></math> only worked for <math><mn>2</mn><mi>t</mi><mo>≤</mo><mi>n</mi></math>. + 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 <math><mi>t</mi></math>. + <math display="block"> + <mrow> + <msub> + <mi>t</mi> + <mi>max</mi> + </msub> + <mo>=</mo> + <mo>⌊</mo> + <mfrac> + <mi>n</mi> + <mn>2</mn> + </mfrac> + <mo>⌋</mo> + </mrow> + </math> + </p></li> + </ul> + <hr> + + <p>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 <math><mi>t</mi></math>, and sum those together.</p> + <p>The sum is the easy part. I knew the final number would be the the sum of all of the <math><msub><mi>m</mi><mi>t</mi></msub></math>s, or:</p> + <math display="block"> + <mrow> + <munderover> + <mo>∑</mo> + <mrow> + <mi>t</mi> + <mo>=</mo> + <mn>0</mn> + </mrow> + <msub> + <mi>t</mi> + <mi>max</mi> + </msub> + </munderover> + <msub><mi>m</mi><mi>t</mi></msub> + </mrow> + </math> + <p>Plugging in our definition for <math><msub><mi>t</mi><mi>max</mi></msub></math>,</p> + <math display="block"> + <mrow> + <munderover> + <mo>∑</mo> + <mrow> + <mi>t</mi> + <mo>=</mo> + <mn>0</mn> + </mrow> + <mrow> + <mo>⌊</mo> + <mfrac> + <mi>n</mi> + <mn>2</mn> + </mfrac> + <mo>⌋</mo> + </mrow> + </munderover> + <msub><mi>m</mi><mi>t</mi></msub> + </mrow> + </math> + + <p>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 <math><mi>t</mi></math> special items out of <math><mi>k</mi></math> total items?"</p> + <p>Then I realized: this was a combinatorics problem! Specifically, I remembered the Binomial Coefficient, or "<math><mi>n</mi></math> choose <math><mi>k</mi></math>", which counts "the number of ways to choose a subset of k elements from a larger set of n elements."</p> + <p>Each sequence of length <math><mi>k</mi></math> contained exactly <math><mi>t</mi></math> 2s. So counting the number of sequences <math><msub><mi>m</mi><mi>t</mi></msub></math> for some <math><mi>t</mi></math> was equivelant to counting the number of ways to choose <math><mi>t</mi></math> elements from a larger set of <math><mi>k</mi></math> elements. By this definition,</p> + <math display="block"> + <mrow> + <msub><mi>m</mi><mi>t</mi></msub> + <mo>=</mo> + <mo>(</mo> + <mfrac linethickness="0"> + <mrow> + <mi>k</mi> + </mrow> + <mi>t</mi> + </mfrac> + <mo>)</mo> + </mrow> + </math> + <p>Plugging in the prior definition for <math><mi>k</mi></math>, and using the summation from above, I arrived at a final equation:</p> + <math display="block"> + <mi>f</mi><mo>(</mo><mi>n</mi><mo>)</mo> + <mo>=</mo> + <mrow> + <munderover> + <mo>∑</mo> + <mrow> + <mi>t</mi> + <mo>=</mo> + <mn>0</mn> + </mrow> + <mrow> + <mo>⌊</mo> + <mfrac> + <mi>n</mi> + <mn>2</mn> + </mfrac> + <mo>⌋</mo> + </mrow> + </munderover> + + <mrow> + <mo>(</mo> + <mfrac linethickness="0"> + <mrow> + <mi>n</mi> + <mo>-</mo> + <mi>t</mi> + </mrow> + <mi>t</mi> + </mfrac> + <mo>)</mo> + </mrow> + </mrow> + </math> + <p>Yay!</p> + <hr> + + <p>Okay, if you didn't see the pattern from the beginning, <code>[1 2 3 5 8]</code> is the <strong>Fibonacci Sequence</strong>, starting at the 2nd element. You might be more familiar with it starting from the 1st element <code>[1 1 2 3 5 8 ...]</code>.</p> + <p>So we really just derived a formula for the <math><mi>n</mi><mo>+</mo><mn>1</mn></math>th Fibonacci number!</p> + <p>When I first learned this, I thought I was some kind of genius or something, but a quick check on ProofWiki told that <a href="https://proofwiki.org/wiki/Fibonacci_Number_as_Sum_of_Binomial_Coefficients">a very similar function was already discovered in 1971</a>, so I guess I'm 55 years late to the party.</p> + <p>The formula on ProofWiki is for the <math><mi>n</mi></math>th fibonacci number, so here's how you could arrive at the real Fibonacci Number as Sum of Binomial Coefficients function:</p> + <p>Begin with the derived formula, replacing <math><mi>n</mi></math> for <math><mi>a</mi></math> to avoid variable conflicts later.</p> + <math display="block"> + <mi>f</mi><mo>(</mo><mi>a</mi><mo>)</mo> + <mo>=</mo> + <mrow> + <munderover> + <mo>∑</mo> + <mrow><mi>t</mi><mo>=</mo><mn>0</mn></mrow> + <mrow> + <mo>⌊</mo> + <mfrac><mi>a</mi><mn>2</mn></mfrac> + <mo>⌋</mo> + </mrow> + </munderover> + <mrow> + <mo>(</mo> + <mfrac linethickness="0"> + <mrow><mi>a</mi><mo>-</mo><mi>t</mi></mrow> + <mi>t</mi> + </mfrac> + <mo>)</mo> + </mrow> + </mrow> + </math> + <p>Since this is really for the <math><mi>n</mi><mo>+</mo><mn>1</mn></math>th Fibonacci number, substitute <math><mi>a</mi><mo>=</mo><mi>n</mi><mo>-</mo><mn>1</mn></math>.</p> + <math display="block"> + <mi>f</mi><mo>(</mo><mi>n</mi><mo>)</mo> + <mo>=</mo> + <mrow> + <munderover> + <mo>∑</mo> + <mrow><mi>t</mi><mo>=</mo><mn>0</mn></mrow> + <mrow> + <mo>⌊</mo> + <mfrac><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mn>2</mn></mfrac> + <mo>⌋</mo> + </mrow> + </munderover> + <mrow> + <mo>(</mo> + <mfrac linethickness="0"> + <mrow><mi>n</mi><mo>-</mo><mi>t</mi><mo>-</mo><mn>1</mn></mrow> + <mi>t</mi> + </mfrac> + <mo>)</mo> + </mrow> + </mrow> + </math> + <p>The original function uses <math><mi>k</mi></math> instead of <math><mi>t</mi></math>.</p> + <math display="block"> + <mi>f</mi><mo>(</mo><mi>n</mi><mo>)</mo> + <mo>=</mo> + <mrow> + <munderover> + <mo>∑</mo> + <mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow> + <mrow> + <mo>⌊</mo> + <mfrac><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mn>2</mn></mfrac> + <mo>⌋</mo> + </mrow> + </munderover> + <mrow> + <mo>(</mo> + <mfrac linethickness="0"> + <mrow><mi>n</mi><mo>-</mo><mi>k</mi><mo>-</mo><mn>1</mn></mrow> + <mi>k</mi> + </mfrac> + <mo>)</mo> + </mrow> + </mrow> + </math> + <p>This is the exact same function that appears on ProofWiki!</p> + </div> +</body> +</html>
\ No newline at end of file |