Computing Fibonacci Numbers

Take a second to let things settle and recover from the mess of square roots and Greek letters. A couple things I'll point out:

The approach we've taken works for any linear recurrence: if you have some sequence $S(n) = a S(n - 1) + b S(n - 2) + \dots$ with a fixed number of terms, you can apply this method and find a closed form. (The number of terms on the right determines the degree of the polynomial we had to solve to get the values of $\lambda$ , so the more terms you have there the less likely you'll be able to get a clean solution.)
Rather surprisingly, this is always an integer for natural $n$ : everything cancels out.¹
Binet's formula provides a neat extension of the Fibonacci sequence to other numbers, and it can be modified to support even complex numbers! If you've ever seen clickbait videos about how 1 + 2 + 3 + 4 + ... = -1/12, this is essentially what is being done there: we're taking a definition and then extending it beyond the original bounds.
$\psi \approx -0.618$ . Because of this, for all natural $n$ , $|\frac{\psi^n}{\sqrt{5}}| < \frac{1}{2}$ . This means you can skip computing it entirely and just round to the nearest integer when you're done.

Take a second to let things settle and recover from the mess of square roots and Greek letters. A couple things I'll point out:

The approach we've taken works for any linear recurrence: if you have some sequence $S(n) = a S(n - 1) + b S(n - 2) + \dots$ with a fixed number of terms, you can apply this method and find a closed form. (The number of terms on the right determines the degree of the polynomial we had to solve to get the values of $\lambda$ , so the more terms you have there the less likely you'll be able to get a clean solution.)
Rather surprisingly, this is always an integer for natural $n$ : everything cancels out.¹
Binet's formula provides a neat extension of the Fibonacci sequence to other numbers, and it can be modified to support even complex numbers! If you've ever seen clickbait videos about how 1 + 2 + 3 + 4 + ... = -1/12, this is essentially what is being done there: we're taking a definition and then extending it beyond the original bounds.
$\psi \approx -0.618$ . Because of this, for all natural $n$ , $|\frac{\psi^n}{\sqrt{5}}| < \frac{1}{2}$ . This means you can skip computing it entirely and just round to the nearest integer when you're done.