summaryrefslogtreecommitdiff
path: root/fib.html
diff options
context:
space:
mode:
authorCollin Williams <96917990+bluedragon1221@users.noreply.github.com>2026-08-16 15:21:39 -0500
committerCollin Williams <96917990+bluedragon1221@users.noreply.github.com>2026-08-16 15:21:39 -0500
commiteef357ebc10246da0da3c8bce427991eeb3f1dce (patch)
treeb7e5cdc91798a4d0395753640683d13f1a908fff /fib.html
parent32b19799a1355805bf69222ef1abb6d806980ced (diff)
add a logo, changes to css, format older articles
Diffstat (limited to 'fib.html')
-rw-r--r--fib.html587
1 files changed, 301 insertions, 286 deletions
diff --git a/fib.html b/fib.html
index 998308e..29d5e71 100644
--- a/fib.html
+++ b/fib.html
@@ -1,55 +1,55 @@
<!DOCTYPE html>
<html>
-<head>
- <title>I accidentally derived a formula for the Fibonacci Sequence</title>
- <meta property="article:published_time" content="2026-06-11">
- <link rel="stylesheet" href="prose.css">
- <script src="article.js"></script>
-</head>
-<body>
- <article>
- <header></header>
+ <head>
+ <title>I accidentally derived a formula for the Fibonacci Sequence</title>
+ <meta property="article:published_time" content="2026-06-11">
+ <script src="article.js"></script>
+ </head>
+ <body>
+ <article>
+ <header></header>
- <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>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>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>
- <pre><code>[1 1 2 1]
+ <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>
+ <pre><code>[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]</code></pre>
- <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>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">sequences</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>&le;</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>&lfloor;</mo>
- <mfrac>
- <mi>n</mi>
- <mn>2</mn>
- </mfrac>
- <mo>&rfloor;</mo>
- </mrow>
- </math>
- </p></li>
- </ul>
- <hr>
+ <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>&le;</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>&lfloor;</mo>
+ <mfrac>
+ <mi>n</mi>
+ <mn>2</mn>
+ </mfrac>
+ <mo>&rfloor;</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>&lfloor;</mo>
- <mfrac>
- <mi>n</mi>
- <mn>2</mn>
- </mfrac>
- <mo>&rfloor;</mo>
- </mrow>
- </munderover>
- <msub><mi>m</mi><mi>t</mi></msub>
- </mrow>
- </math>
+ <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 was 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>&lfloor;</mo>
+ <mfrac>
+ <mi>n</mi>
+ <mn>2</mn>
+ </mfrac>
+ <mo>&rfloor;</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>&lfloor;</mo>
- <mfrac>
- <mi>n</mi>
- <mn>2</mn>
- </mfrac>
- <mo>&rfloor;</mo>
- </mrow>
- </munderover>
+ <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>&lfloor;</mo>
+ <mfrac>
+ <mi>n</mi>
+ <mn>2</mn>
+ </mfrac>
+ <mo>&rfloor;</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>
+ <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>&lfloor;</mo>
- <mfrac><mi>a</mi><mn>2</mn></mfrac>
- <mo>&rfloor;</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>&lfloor;</mo>
- <mfrac><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mn>2</mn></mfrac>
- <mo>&rfloor;</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>&lfloor;</mo>
- <mfrac><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mn>2</mn></mfrac>
- <mo>&rfloor;</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>
- </article>
-</body>
-</html> \ No newline at end of file
+ <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>&lfloor;</mo>
+ <mfrac><mi>a</mi><mn>2</mn></mfrac>
+ <mo>&rfloor;</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>&lfloor;</mo>
+ <mfrac><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mn>2</mn></mfrac>
+ <mo>&rfloor;</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>&lfloor;</mo>
+ <mfrac><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mn>2</mn></mfrac>
+ <mo>&rfloor;</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>
+ </article>
+ </body>
+</html>