fibonacci sock almost ruined my date

---

click here to skip to the math.

finding the sock

---

My partner and I were on a date in Sausalito, a quiet seaside town north of the Bay, when we came across this sock (at a sock store).

I personally assume that all code on clothing is nonsense until proven otherwise, so I got ready to make a joke about it, except that this program…actually does something.

Here, take a look:

1fn main() {
2	let root = 5_F32.0;
3	let phi = (1.0 + root)/2;
4	for n in 0.16 {
5		print!('{}', (phi.pow(n)/root).round());
6	}
7}
8

As we've hinted at in the title, this program computes the first 16 Fibonacci numbers (in Rust!). These are the numbers you get when you start with terms $1$ and $1$ (or sometimes $0$ and $1$) and add the previous two terms to get the next term. You can see that the program output across the back of the ankle,

$$1, 1, 2, 3, 5, 8\dots$$

is indeed the first couple of terms of the Fibonacci sequence.

To compute these numbers, the program is using something called Binet's formula.² Binet's formula says that the $n$th Fibonacci number is

$$F_{n}=\frac{\phi^n-\bar\phi^n}{\sqrt{5}},$$

where

$$\phi = \frac{1+\sqrt{5}}{2}, \quad \bar\phi=\frac{1-\sqrt{5}}{2}.$$

It was pretty easy to get here with a quick Wikipedia search, after which I tried very hard to be like "well, that's cool and all, I guess I'll update my priors about code on apparel, but now we can move on…"

except that my brain was like...!!! where does this formula come from???? what does it all mean???? And despite the romantic vibe and beautiful seaside view, I was not able to let it go.

nerd-sniped

---

The idea goes something like this: we know that the Fibonacci numbers $F_{0}, F_{1},F_2\dots$ satisfy the recurrence relation

$$F_{n}= F_{n-1} + F_{n-2} \quad({\color{red}{*}})$$

with the initial conditions

$$F_{0}= 0, \quad F_{1}= 1. \quad({\color{blue}\star})$$

Here's the general plan:

1. Do some guessing to find a family of sequences that satisfies the recurrence relation in $({\color{red}{*}})$.
2. Hope that one of them satisfies the initial conditions in $({\color{blue}\star})$.

We know that the Fibonacci sequence grows at least exponentially, since the sequence more than doubles every two terms. So let's try guessing³ that some exponential sequence satisfies the relation in $({\color{red}{*}})$, say $s_{n}= cx^n$ where $c$ and $x$ are fixed real numbers. Then $({\color{red}{*}})$ says that

$$s_{n}= s_{n-1} + s_{n-2},$$

which means that

$$cx^{n}=cx^{n-1}+cx^{n-2}.$$

Then we know that either $c=0$, or

$$x^{2}-x-1=0.$$

This polynomial⁴ might look familiar to you. Indeed,

$$\phi = \frac{1+\sqrt{5}}{2}, \quad \bar\phi=\frac{1-\sqrt{5}}{2}$$

are its roots! This means we actually have two families of sequences satisfy the Fibonacci relation in $({\color{red}{*}})$. These are

$$t_{n}= c_{1}\phi^{n} \quad \text{ and } \quad \bar t_{n}=c_2\bar\phi^n,$$

where $c_{1},c_2$ are some constants.

We also easily check that the sum of the two,

$$f_{n}= t_{n}+\bar t_{n} = c_{1}\phi^{n} + c_{2}\bar \phi^{n}$$

also satisfies the relation in $({\color{red}{*}})$.

Now that we've got a nice family of sequences that satisfy $({\color{red}{*}})$, let's see if any of them satisfy the initial conditions in $({\color{blue}\star})$. We should have that

$$f_{0}=c_{1}\phi^0+c_2\bar{\phi}^{0}= 0$$

and

$$f_1=c_1\phi^1+c_2\bar{\phi}^{1}= 1.$$

Simplifying a bit, we see that

$$c_1+c_{2}=0$$

and

$$c_{1}\phi+ c_{2}\bar \phi =1.$$

We can solve this system of equations, and we get that

$$c_{1}= \frac{1}{\sqrt{5}}, \quad c_{2}= -\frac{1}{\sqrt{5}}.$$

Plugging it all back in, we see that the sequence

$$f_{n}= \frac{1}{\sqrt{5}}\phi^{n}-\frac{1}{\sqrt{5}} \bar\phi^{n}= \frac{\phi^{n}- \bar{\phi}^n}{\sqrt 5}$$

satisfies the recurrence relation in $({\color{red}{*}})$ and the initial conditions in $({\color{blue}\star})$. That means that this sequence is the sequence of Fibonacci numbers! So we win, and this is why Binet's formula works!⁵

Getting here took a lot of animated yapping, and I imagine that everyone around thought that we were crazy. But hey, I understood it eventually, and the date wasn't even ruined! We got some ice cream, watched some boats, and managed not to miss the sunset.

e, thanks for telling me to write this.

footnotes

---

1. I spent far too long finding this photo because it turns out that searching "Binet's formula code sock" doesn't exactly work. I went to the sock store's Google Maps page and found the name of a company that make these novelty socks (it was the wrong one), realized I could google "novelty socks" and visited a couple novelty sock websites, continued looking until I realized that I probably should have tried "Fibonacci code sock", and finally tracked it down. ↩

2. Though, the program ignores the $\bar\phi^n$ term because $\bar\phi\approx -0.618$ is small enough to safely ignore if you're rounding to the nearest integer. ↩

3. à la solving differential equations ↩

4. This polynomial is called the characteristic polynomial of the linear recurrence relation. ↩

5. Of course, this is not the only way to get to Binet's formula. I personally like the linear algebra approach better, where you can see that $\phi$ and $\bar{\phi}$ are the eigenvalues of the matrix corresponding to the recurrence relation. ↩