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.

View all posts by Brent →

12 Responses to Fibonacci multiples

Dennis says:

May 15, 2012 at 12:59 pm

I wonder…
Matt Gardner Spencer says:

May 15, 2012 at 5:28 pm

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:
  
  May 15, 2012 at 7:11 pm
  
  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:
    
    May 16, 2012 at 9:48 am
    
    The key to my proof is using pictures like those here: https://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:
      
      May 16, 2012 at 9:56 am
      
      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? 😉
Joseph Nebus says:

May 15, 2012 at 9:46 pm

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.
Joseph Nebus says:

May 15, 2012 at 9:48 pm

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.
JRH says:

May 16, 2012 at 6:46 pm

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:
  
  May 16, 2012 at 6:54 pm
  
  Cool proof!
  
  I really wish there were a “preview comment” button too. But wordpress.com does not support it. =(
Pingback: Nature by Numbers | The Math Less Traveled
Pingback: Fibonacci multiples, solution 1 | The Math Less Traveled
Pingback: An Interesting Golden Ratio Identity – jonisalonen.com