4 ms·

I think the proof for the closed-form version is accessible to people with a background in linear algebra. The matrix is diagonalizable (not all matrixes are di

I think the proof for the closed-form version is accessible to people with a background in linear algebra. The matrix is diagonalizable (not all matrixes are diagonalizable, but this one is): M = P Δ P^-1 Here, P is some invertible matrix and Δ is a diagonal matrix. The powers of M reveal how useful this is: M^N = (P Δ P^-1) * … * (P Δ P^-1) If you adjust the parentheses, you’ll see N-1 terms of (P^-1 P), which can be removed, giving: M^N = P Δ^N P^-1 The powers of a diagonal matrix is done by taking powers of the entries on the diagonal. You see the φ values (1±√5)/2 in the matrix Δ. Diagonalization of a 2x2 matrix is simple to do on paper. The diagonal of Δ contains the eigenvalues of M, which can be found using the quadratic formula. Proving that this is a correct way to diagonalize any diagonalizable matrix is more of a chore, but for this specific 2x2 matrix, you can just show that that you’ve found the values for P and Δ. This is very elegant mathematically, but I would not use the closed-form solution if I wanted the exact answer, because you’d need a lot of precision, and that’s inconvenient.

abhi9u 3y ago
(Author of the article here) Thanks for writing this up, it's much much more intuitive than what I've read everywhere else. I primarily looked up Knuth (TAOCP Vol 1) for this part, and he showed a longish proof using generating functions which looked too long to show in the article, and I would not have done a better job than him. The thirty three miniatures book showed a more abstract proof, which would have been accessible to people deeply familiar with the concept of basis vectors.
- dietrichepp 3y ago
  My own personal experience is that, in linear algebra, there are a lot of different ways to prove the same thing. When you search for a proof of something, you may find a proof that is overly basic and verbose, or a proof that is overly advanced and terse. Finding an explanation of a linear algebra concept that strikes the right balance can be time-consuming or difficult. This is why you see, for example, a hojillion different articles explaining what quaternions are. Everybody is most comfortable at a different place on the complexity spectrum—from “a vector is (x,y,z), here are rules for how that works” to “a vector space is an abelian group V, field F, and a map in Hom(F,End(V))”.
  - abhi9u 3y ago
    That's quite true. And so many books to teach it. I am a software engineer and don't have a major in math beyond studying discrete math in college. So I really have to work hard to understand these proofs. And I certainly value proofs explained in simple terms. :)
  - onecommentman 3y ago
    I agree. In fact finding an explanation of pretty much any significant mathematical concept that strikes that balance (across the broad range of individual talents and backgrounds) is time-consuming or difficult. Which is why a significant chunk of mathematics research effort and funding should go to making such explanations less time-consuming and difficult. IMHO. It may be as simple as a vetted compilation of explanations for a single idea so the individual can find the ones that work for them, or formal development of new explanations. What’s more significant: a new incremental result in some obscure corner of math, or 100M more people understanding what an eigenvalue actually means? Or a new explanation that makes a concept more relevant in an entire application area?
- eutectic 3y ago
  The generating function proof is also really beautiful! I think I maybe like it even more than the linear algebra proof.
  - kccqzy 3y ago
    The generating function approach is the standard way of solving recurrences. In that sense, it isn't beautiful, just routine. But yes the first time I'd seen it I felt my body shudder at that sorcery.
kragen 3y ago
what if you use the closed-form answer, but without any floating-point or other approximations i mean it all comes out to an integer in the end, all the radicals cancel i see tromp already suggested a form of this
- abhi9u 3y ago
  But that seems to be computationally same amount of work as the matrix form, so we get similar performance?
  - kragen 3y ago
    hmm, maybe? i haven't tried it so i can't be sure, but it's plausible
  - kmill 3y ago
    Yes, I believe so, up to some multiplicative factor. You can carry out the exponentiations in the field Q[sqrt(5)], which is two-dimentional over Q. The interesting thing here is that diagonalization is trading one 2d vector space for another -- one with a very well-behaved multiplication operation (it's distributive, commutative, associative, and invertible). There's no need to do this to quickly compute fibonacci numbers, but it's pretty neat.
    - finite_depth 3y ago
      [dead]
  - jfarmer 3y ago
    I did this years ago to demonstrate to my students that the "exact solution" can still be written in code. There are implementations in Ruby and Python, with some benchmarking code: https://github.com/jfarmer/fib-bench/ https://github.com/jfarmer/fib-bench/ Code winds up looking like: def fib_phi(n) ((PhiRational(0,1)**n - PhiRational(1,-1)**n)/PhiRational(-1, 2)).a.to_i end The exponentiation operation uses basic exponentiation by squaring for performance: https://en.wikipedia.org/wiki/Exponentiation_by_squaring https://en.wikipedia.org/wiki/Exponentiation_by_squaring (Technically implemented arithmetic over Q(ϕ) not Q(√5) because it simplifies the code a bit.)
brian_cloutier 3y ago
If anyone wants to read this in book form, Linear Algebra Done Right includes it as an exercise at the end of a very short and readable chapter 5.C on eigenspaces and diagonal matricies. The treatment in thirty-three miniatures describes the steps you take but doesn't mention what you are actually doing (finding eigenvalues) or leave you with any intuition for why this was a natural thing to have tried
- abhi9u 3y ago
  Yes, that book (thirty three miniatures) has great content, but a hard read. Basically someone like me needs to go back, read other sources, and spend time on paper to get it.
jpfr 3y ago
Yes! This is close the explanation I first encountered in Hubbard & Hubbard. One of the nicest math textbooks and going from zero up to differential forms. https://matrixeditions.com/5thUnifiedApproach.html https://matrixeditions.com/5thUnifiedApproach.html

abhi9u 3y ago

(Author of the article here) Thanks for writing this up, it's much much more intuitive than what I've read everywhere else. I primarily looked up Knuth (TAOCP Vol 1) for this part, and he showed a longish proof using generating functions which looked too long to show in the article, and I would not have done a better job than him. The thirty three miniatures book showed a more abstract proof, which would have been accessible to people deeply familiar with the concept of basis vectors.

dietrichepp 3y ago
My own personal experience is that, in linear algebra, there are a lot of different ways to prove the same thing. When you search for a proof of something, you may find a proof that is overly basic and verbose, or a proof that is overly advanced and terse. Finding an explanation of a linear algebra concept that strikes the right balance can be time-consuming or difficult. This is why you see, for example, a hojillion different articles explaining what quaternions are. Everybody is most comfortable at a different place on the complexity spectrum—from “a vector is (x,y,z), here are rules for how that works” to “a vector space is an abelian group V, field F, and a map in Hom(F,End(V))”.
- abhi9u 3y ago
  That's quite true. And so many books to teach it. I am a software engineer and don't have a major in math beyond studying discrete math in college. So I really have to work hard to understand these proofs. And I certainly value proofs explained in simple terms. :)
- onecommentman 3y ago
  I agree. In fact finding an explanation of pretty much any significant mathematical concept that strikes that balance (across the broad range of individual talents and backgrounds) is time-consuming or difficult. Which is why a significant chunk of mathematics research effort and funding should go to making such explanations less time-consuming and difficult. IMHO. It may be as simple as a vetted compilation of explanations for a single idea so the individual can find the ones that work for them, or formal development of new explanations. What’s more significant: a new incremental result in some obscure corner of math, or 100M more people understanding what an eigenvalue actually means? Or a new explanation that makes a concept more relevant in an entire application area?
eutectic 3y ago
The generating function proof is also really beautiful! I think I maybe like it even more than the linear algebra proof.
- kccqzy 3y ago
  The generating function approach is the standard way of solving recurrences. In that sense, it isn't beautiful, just routine. But yes the first time I'd seen it I felt my body shudder at that sorcery.

kragen 3y ago

what if you use the closed-form answer, but without any floating-point or other approximations i mean it all comes out to an integer in the end, all the radicals cancel i see tromp already suggested a form of this

abhi9u 3y ago
But that seems to be computationally same amount of work as the matrix form, so we get similar performance?
- kragen 3y ago
  hmm, maybe? i haven't tried it so i can't be sure, but it's plausible
- kmill 3y ago
  Yes, I believe so, up to some multiplicative factor. You can carry out the exponentiations in the field Q[sqrt(5)], which is two-dimentional over Q. The interesting thing here is that diagonalization is trading one 2d vector space for another -- one with a very well-behaved multiplication operation (it's distributive, commutative, associative, and invertible). There's no need to do this to quickly compute fibonacci numbers, but it's pretty neat.
  - finite_depth 3y ago
    [dead]
- jfarmer 3y ago
  I did this years ago to demonstrate to my students that the "exact solution" can still be written in code. There are implementations in Ruby and Python, with some benchmarking code: https://github.com/jfarmer/fib-bench/ https://github.com/jfarmer/fib-bench/ Code winds up looking like: def fib_phi(n) ((PhiRational(0,1)**n - PhiRational(1,-1)**n)/PhiRational(-1, 2)).a.to_i end The exponentiation operation uses basic exponentiation by squaring for performance: https://en.wikipedia.org/wiki/Exponentiation_by_squaring https://en.wikipedia.org/wiki/Exponentiation_by_squaring (Technically implemented arithmetic over Q(ϕ) not Q(√5) because it simplifies the code a bit.)

brian_cloutier 3y ago

If anyone wants to read this in book form, Linear Algebra Done Right includes it as an exercise at the end of a very short and readable chapter 5.C on eigenspaces and diagonal matricies. The treatment in thirty-three miniatures describes the steps you take but doesn't mention what you are actually doing (finding eigenvalues) or leave you with any intuition for why this was a natural thing to have tried

abhi9u 3y ago
Yes, that book (thirty three miniatures) has great content, but a hard read. Basically someone like me needs to go back, read other sources, and spend time on paper to get it.

jpfr 3y ago

Yes! This is close the explanation I first encountered in Hubbard & Hubbard. One of the nicest math textbooks and going from zero up to differential forms. https://matrixeditions.com/5thUnifiedApproach.html https://matrixeditions.com/5thUnifiedApproach.html