## Monday Math Madness #7

It's time for Monday Math Madness #7. I love infinite series and I found today's infinite series problem on the web. This is one of the most interesting of these kinds of problems I have run into. It's challenging but not brutally difficult, so give it a try. I won't reveal the source until the contest ends because the answer is posted with the problem.

Thanks to the sponsors for this contest, I have one $25 gift certificate left for the Art of Problem Solving. I also have a couple of Rubik's Revolutions, courtesy of Techno Source. Depending on how many correct solutions I get I may give away two prizes.

Here's the problem:

What is the sum of this infinite series?

The subscripted F terms refer to the familiar Fibonacci series where F

_{0}=1, F_{1}=1, and F_{n}=F_{n-2}+F_{n-1}for n > 1.

Here are the rules for the contest:

1. Email your answers with solutions to mondaymathmadness at gmail dot com.

2. Only one entry per person.

3. Each person may only win one prize per 12 month period.

3. Answer must be explained. You must show your work! Wild About Math! and Blinkdagger will be the final judges on whether an answer was properly explained or not.

4. The deadline to submit answers is Tuesday, June 3, 2008 12:01AM, Pacific Time. (That’s Tuesday morning, not Tuesday night.)

5. The winner will be chosen randomly from all timely well-explained and correct submissions, using a random number generator.

6. The winner will be announced Friday, June 6, 2008.

7. The winner (or winners) will receive a $25 gift certificate, graciously donated by the Art of Problem Solving. I may give other prizes if there are many entries.

8. Comments for this post should only be used to clarify the problem. Please do not discuss ANY potential solutions.

9. I will post names and website/blog links for people submitting timely correct well-explained solutions UNLESS I get too many entries, in which case I'll post a subset of these.

ingdasMay 26th, 2008 - 10:41

Could it be that there is an error in the contest?

normalle F(0)=0 in the Fibonacci sequence. F(1) and F(2)are both one.

MgcclMay 26th, 2008 - 12:08

Usually… F_0 = 0

SolMay 26th, 2008 - 13:18

Ingdas and Mgcci. When writing the Fibonacci series, it’s arbitrary whether f[0] = 0 or f[0] = 1. I’ve seen it both ways. My experience is that the series starts with 1, 1. Some people start the series with 0, 1. Also, it’s arbitrary whether you index terms starting with the 0th term or with the 1st term.

No change is needed for this contest.

SolMay 26th, 2008 - 13:53

p.s. Three people have already submitted correct answers given the current wording of the problem.

Joshua ZuckerMay 26th, 2008 - 16:53

I was recently at the Julia Robinson Mathematics Festival, where noted combinatorialist Jennifer Quinn used the f(0) = 1 definition because she wanted f(n) to denote the number of tilings with squares and 1×2 rectangles of a 1xn strip.

Meanwhile Donald Knuth pointed out that some favorite Fibonacci identities, like F(n) dividing F(n*k) for any k, only work with the f(0) = 0 definition.

So there’s two noted mathematicians for you who each have pretty strong preferences for their definition of f(0).

I think Dr. Quinn’s compromise suggestion is good: use F(n) for the F(0) = 0 version, and use f(n) for the f(0) = 1 version, to avoid confusion.

SanMay 27th, 2008 - 09:03

Do we have to prove that the series is convergent?

SolMay 27th, 2008 - 11:02

San,

Take is as a given for this problem that the series converges.

johnJune 1st, 2008 - 17:04

i think it does matter which one chooses F_0 to be. if it’s chosen to be 1, then the above sum has first term 1. if it’s chosen to be 0 then the first term is 0. thus we might see two possible answers.

consider using 1/10 rather than 3/5 in the original problem. i get a sum of 10/89 which can’t be right if the first term is 1.

i can’t put my finger on it, but there is a really weird problem with this problem…

johnJune 2nd, 2008 - 10:21

ive really enjoyed playing with this problem. i’ve (finally) come to the conclusion that unless one uses a fraction, n/m, with the property that

sqrt(2)-1

johnJune 2nd, 2008 - 10:23

hmm…my last note didn’t seem to post. oh well

efriqueJune 2nd, 2008 - 16:33

Ah, Dammit. I don’t think I noticed this had F(0)=1 when I submitted. Unlike, say wikipedia or a dozen other sites I could point to.

I can understand starting the series indexed from 0 when the first term is 0 (since you haven’t got anything to count yet), but NOT when starting it from 1. When you count your children, is the first one #0??

Frankly, it makes /no sense/ that I can see to say the first term is 1 AND count it from zero. Consequently much more fuss should have been made of doing it in an odd way.

johnJune 2nd, 2008 - 16:47

efrique,

indexing from zero and not having your first term zero is pretty common. for example,

sum (n=0 to infinity) (1/2)^n has first term 1. i do think there is a real bit of weirdness with mmm7’s problem though…

George BellJune 3rd, 2008 - 11:28

I agree with Knuth! One more reason to define f(0)=0 is if you want to extend the Fibonacci series to negative integers. You can then define f(-i)=(-1)^{i+1}f(i). If you start out with f(0)=1 this identity would be less symmetric.

But why define f(-1) at all? It makes certain identities simpler, like powers of the golden ratio, etc.

But for the purposes of this problem it seems to me the problem designers can define the sequence however they like!

johnJune 3rd, 2008 - 17:11

i really like the solution provided. i’ve produced a solution, though, which gives an answer of 15, and i’m pretty sure my solution is right…i’ve been wrong before though my solution uses a closed form for the fibonacci sequence, relying on the golden ratio. using that closed form, i was able to directly compute the sum. i also managed to find a general formula for similar sums. this general form, though suggested to me some possible convergence problems for the series…but i would need to look harder at it.

ingdasJune 5th, 2008 - 08:45

john, i think you took f(0)=0 and then you get your answer of 15.

johnJune 5th, 2008 - 09:48

ingdas,

no, that wasn’t the problem (and it wouldn’t matter to the sum in the end if one set up their sum properly). in computing the direct sum i made a small error in my resulting geometric series. once i found the error, i got the 25. i then generalized the result for fractions of the form n/m (like 3/5) for this series and got m^2/(m^2-mn-n^2) as the closed form. this form is good for fractions with 0

johnJune 5th, 2008 - 09:49

0 less than n/m less than (sqrt(5)-1)/2