Fibonacci multiples

I haven’t written anything here in a while, but hope to write more regularly now that the semester is over—I have a series on combinatorial proofs to finish up, some books to review, and a few other things planned. But to ease back into things, here’s a little puzzle for you. Recall that the Fibonacci numbers are defined by

F_0 = 0; F_1 = 1; F_{n+2} = F_{n+1} + F_n.

Can you figure out a way to prove the following cute theorem?

If m evenly divides n, then F_m evenly divides F_n.

(Incidentally, the existence of this theorem constitutes good evidence that the “correct” definition of F_0 is 0, not 1.)

For example, 5 evenly divides 10, and sure enough, F_5 = 5 evenly divides F_{10} = 55. 13 evenly divides 91, and sure enough, F_{13} = 233 evenly divides F_{91} = 4660046610375530309 (in particular, 4660046610375530309 = 233 \times 20000200044530173).

I know of two different ways to prove it; there are probably more! Neither of the proofs I know is particularly obvious, but they do not require any difficult concepts.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, challenges, fibonacci, number theory, pattern and tagged , . Bookmark the permalink.

12 Responses to Fibonacci multiples

  1. Dennis says:

    I wonder…

  2. Matt Gardner Spencer says:

    Sounds exciting! I’m guessing that neither of your proofs uses the closed form of fibonacci and symmetric polynomials. But how about induction and monimos and dominos?

    • Brent says:

      Nope, but if you know of such a proof I’d love to hear it! One of the proofs definitely uses induction, and can probably be formulated in terms of dominos, though I haven’t thought about the details. The other one is more elementary.

      I would also like to see a proof involving monimos, dominos, and geronimos.

      • Matt Gardner Spencer says:

        The key to my proof is using pictures like those here: (especially those posted by Xander in the comments) to prove
        F_{mn}=F_n\cdot F_{(m-1)n+1}+F_{n-1}\cdot F_{(m-1)n} and then using induction.

        • Brent says:

          Yes, I can see how that would work. It’s different from both of my proofs (one of which can also be formulated in terms of those pictures, now that I have thought about it more carefully).

          Now, how about that proof using the closed form of fibonacci and symmetric polynomials? 😉

  3. Joseph Nebus says:

    I’d never heard of this theorem before and I’m captivated by it. I’d have expected to run across it in those occasional lists of cool mathematics trivia.

  4. Joseph Nebus says:

    Reblogged this on nebusresearch and commented:
    I have not, as far as I remember, encountered this theorem before. And for the time I’ve had to think about it I realize I’ve got no idea how to prove it. However, it’s a neat little result that makes me smile to hear about, and theorems that bring smiles are certainly worth sharing.

  5. JRH says:

    For M = \left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right], M^{n} = \left[\begin{array}{ll} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{array}\right]. (Proof by induction left as an exercise for the reader.)

    Now assume that F_{km} = K_{k}F_{m} for k \geq 1, which can be proven for the base cases of 1 and 2 with K_{1} = 1 and K_{2} = [F_{m+1}+F_{m-1}] by expanding M^{2m} = M^{m}M^{m}.

    Then M^{(k+1)m} = M^{km}M^{m} and so F_{(k+1)m} = F_{km+1}F_{m} + F_{km}F_{m-1} = K_{k+1}F_{m}, with K_{k+1} = [F_{km+1} + K_{k}F_{m-1}].

    I really wish there were a “preview comment” button so I could double check all of that LaTeX before posting.

    • Brent says:

      Cool proof!

      I really wish there were a “preview comment” button too. But does not support it. =(

  6. Pingback: Nature by Numbers | The Math Less Traveled

  7. Pingback: Fibonacci multiples, solution 1 | The Math Less Traveled

  8. Pingback: An Interesting Golden Ratio Identity –

Comments are closed.