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.