Recently, a friend asked me a fun math question. He's creating a real-life RPG for artists, called *illolife*^{1}. He wrote the experience point threshold for each level in terms of the previous level's threshold. His question: is there a formula to get that threshold *directly*, without computing all the levels before it?

I say it's "fun" because the level differences follow the Fibonacci sequence. Specifically: If \(X_i\) represents the experience needed for level \(i\)^{2}, and \(F_i\) is the \(i\)th Fibonacci number, then \[X_{i + 1} = X_i + 250 F_i.\] (The factor of 250 is just a scaling factor, and it's not important.)

So the question boils down to: *is there a compact way to compute sums of Fibonacci numbers*?

## Fibonacci sums are *almost* Fibonacci numbers

As it happens, Fibonacci *sums* follow the same pattern as Fibonacci *numbers*, but they're always ahead 2 spots in the sequence, and off by 1: \[\sum_{i=1}^n F_i = F_{n + 2} - 1.\] Here are a few examples.

\(n\) | \(\sum\limits_{i=1}^n F_i\) | \(F_{n + 2}\) |
---|---|---|

\(1\) |
\(\mathbf{1}\) |
\(2\) |

\(2\) |
\(1 + 1 = \mathbf{2}\) |
\(3\) |

\(4\) |
\(1 + 1 + 2 + 3 = \mathbf{7}\) |
\(8\) |

\(8\) |
\(1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 = \mathbf{54}\) |
\(55\) |

What a delightful result! It shows that Fibonacci sums are as easy to compute as Fibonacci numbers. This raises the question -- how easy are Fibonacci numbers to compute?

## Binet's formula and the golden ratio

A simple expression, known as *Binet's formula*, can directly compute the \(n\)th Fibonacci number. Using \(\varphi \equiv \left(1 + \sqrt{5}\right) / 2\), the golden ratio, we have:

\[F_n = \frac{\varphi ^ n - \left(1 - \varphi\right) ^ n}{\sqrt{5}}.\]

Here is a simple R function to compute it.

```
fib_closed_form <- function(n) {
# Compute the nth fibonacci number with Binet's formula, using the golden
# ratio 'phi'.
phi <- (1 + sqrt(5)) / 2
return ((phi ^ n - (1 - phi) ^ n) / sqrt(5))
}
```

Binet's formula surprised me at first: it's a function of *irrational* numbers which gives *integers* every time! Fortunately, it's fairly easy to work them out by hand to see why it works. I did the first few, which made it seem a lot more plausible to me.

I was worried that we might lose precision by going to floating point numbers and then coming back to integers. To check whether this is a problem, we need a "gold standard" for Fibonacci numbers to compare against. Here is another helper function which computes Fibonacci numbers directly from their definition. (Since it only uses integers, it shouldn't be affected by floating point errors.)

```
fib_direct <- function(n) {
# Compute the nth fibonacci number directly from the definition.
# (Assumes n >= 1.)
fib <- c(1, 1)
while (length(fib) < max(n)) {
fib <- c(fib, sum(tail(fib, 2)))
}
return (fib[n])
}
```

Now we can compare the results from each.

```
# A set of n-values for testing purposes.
n <- seq(from=5, to=80, by=5)
# Compute Fibonacci numbers at these n-values by both methods, and compute the
# difference between them.
fib_compare <- data.frame(n=n,
direct=fib_direct(n),
binet=fib_closed_form(n))
fib_compare$diff <- fib_compare$binet - fib_compare$direct
# Display the results.
print(fib_compare, row.names=FALSE)
```

```
## n direct binet diff
## 5 5 5 0.0000000000000008881784
## 10 55 55 0.0000000000000142108547
## 15 610 610 0.0000000000003410605132
## 20 6765 6765 0.0000000000045474735089
## 25 75025 75025 0.0000000000582076609135
## 30 832040 832040 0.0000000008149072527885
## 35 9227465 9227465 0.0000000111758708953857
## 40 102334155 102334155 0.0000001341104507446289
## 45 1134903170 1134903170 0.0000016689300537109375
## 50 12586269025 12586269025 0.0000190734863281250000
## 55 139583862445 139583862445 0.0002441406250000000000
## 60 1548008755920 1548008755920 0.0029296875000000000000
## 65 17167680177565 17167680177565 0.0371093750000000000000
## 70 190392490709135 190392490709135 0.4375000000000000000000
## 75 2111485077978050 2111485077978055 5.2500000000000000000000
## 80 23416728348467684 23416728348467744 60.0000000000000000000000
```

Looks like the concern was justified: things go awry somewhere between \(F_{70}\) and \(F_{75}\). Still, the formula works remarkably well until that point. Especially considering the application -- it'll be a long time before any illolifer hits level 70!

## A surprising connection

So far, we've used two convenient results:

- The sums of Fibonacci numbers are (almost) Fibonacci again.
- Binet's formula, \(F_n = \left(\varphi^n - (1 - \varphi)^n\right) / \sqrt{5}\), directly gives the \(n\)th Fibonacci number.

Surprisingly, these results are related!

Consider the first one: the sum over a sequence gives the same sequence^{3}. For *continuous* quantities (instead of *discrete*), we'd have integrals instead of sums, and functions instead of sequences. So, this is like saying the *integral* of a *function* gives that same *function*. This is a well-known property of exponential functions! How suggestive -- do the Fibonacci numbers grow exponentially?

They do. Look at Binet's formula, and realize that \(\left|1 - \varphi\right| < 1\); this means that the \(\left(1 - \varphi\right)^n\) term is insignificant for large \(n\). What remains is \[F_n \approx \frac{\varphi^n}{\sqrt{5}} \,\,\,\,\,\,\,\,(\text{for large }n).\] This is exponential with a base of \(\varphi\).

So we needed two properties of Fibonacci numbers, and it turns out that their hidden exponential nature underpins both of these properties.

## Finally: computing the experience for level \(n\)

Putting all the pieces together, and remembering that \(\varphi = \left(1 + \sqrt{5}\right) / 2\), we have

\[X_n = 250\left( \frac{\varphi^{n + 1} - \left(1 - \varphi\right)^{n + 1}}{\sqrt{5}} - 1 \right)\]

Sanity check: what are the first few levels?

```
X <- function(n) {
phi <- (1 + sqrt(5)) / 2
return (250 * ((phi ^ (n + 1) - (1 - phi) ^ (n + 1)) / sqrt(5) - 1))
}
cat(X(1:10))
```

`## 0 250 500 1000 1750 3000 5000 8250 13500 22000`

These numbers exactly match the ones he provided me. Success!

This is the link for illolife, but note that you have to be logged in to facebook to see anything.↩

\(X_1 = 0\), since everybody starts at level 1.↩

Well, up to a small constant offset.↩