MMM #35 Fibonacci fun - we have winners!
July 4th, 2009
I’m giving away three prizes this time. Yes, I did say I would give four prizes but when I reviewed the first two submissions one of them was not correct. Henno Brandsma, editor for the Topology Q+A Board, sent the first correct solution, and that was the only correct solution submitted before I gave a small hint. I’m giving a prize to .mau. since he has sent in many solutions to MMMs and has never been selected by random.org. And, I’m giving a prize to Olivier, who was selected by random.org.
Here was the problem:
Let F(0)=1, F(1)=1, and F(n)=F(n-2)+F(n-1). This is the familiar Fibonacci series.
Simplify F(0)xF(1) + F(1)xF(2) + F(2)xF(3) + F(3)xF(4) + … + F(n-1)xF(n) + F(n)xF(n+1)
Show your work.
I got 14 submissions. Most of you sent induction proofs. Since induction doesn’t give any insight as to how a solution was derived I can only guess that folks found patterns for sums as n increases then used induction to verify the patterns they saw.
Chao Xu submitted a nice induction proof at the Math Solutions Blog. The solution was password protected to not help others before the submission deadline. I’ve asked Chao to unprotect it.
Duram had an interesting different-looking but equivalent answer:
S(n+1)=( f(n+2)^2 - f(n) x f(n+1) -1 ) /2
Note how this answer eliminates the need to consider odd and even cases. And, yes, the index is off by 1 in this formula but the insight is excellent.
Jacques Descartes had a clever simplification of the odd/even thing:
S(n)=F(n+1)^2-.5+.5(-1)^n
Do you see how odd/even is handled?
Matthias Malandain proved these two formulas:
S(2n) = (F(2n+1))^2
S(2n-1) = F(2n-1) x F(2n+1)
Another way to approach the problem was by looking at the pictures I posted. While my way does not provide a proof it gives one an intuitive sense of why the answer is what it is.
I’m delighted to see the variety in solving this problem.
Stay tuned Monday for the next MMM, right here at Wild About Math!
If you enjoyed this post, make sure you subscribe to my RSS feed!
