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 these ads
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: http://mathlesstraveled.com/2011/05/24/post-without-words-1/ (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 wordpress.com 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 – jonisalonen.com

Comments are closed.