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

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