Gaining experience with Fibonacci sums

Recently, a friend asked me a fun math question. He’s creating a real-life RPG for artists, called illolife¹. 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\)², 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.

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:

1. The sums of Fibonacci numbers are (almost) Fibonacci again.
2. 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³. 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!