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

.

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

If evenly divides , then evenly divides .

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

For example, evenly divides , and sure enough, evenly divides . evenly divides , and sure enough, evenly divides (in particular, ).

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.

I wonder…

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?

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.

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

and then using induction.

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? ;-)

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.

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.

For , . (Proof by induction left as an exercise for the reader.)

Now assume that for , which can be proven for the base cases of 1 and 2 with and by expanding .

Then and so , with .

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

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