## 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.

Assistant 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: 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:

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. =(