1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
|
<!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>
<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>
<pre><code>[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]</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>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>
</article>
</body>
</html>
|
