MMM7 Solutions

Interestingly, this week’s Monday Math Madness (7) question can be answered with a direct application of generating functions, which I recently used to derive the Fibonacci numbers a few weeks ago! (See here for Part I and here for Part II.)

Let me be clear. You don’t actually have to make a generating function out of this, like I do below. I recognize that it adds one more “layer of complication” that isn’t really needed. I did it because it helps me keep my terms straight. Plus I wanted to connect it to the Fibonacci posts that I did easily. You can easily do it without.

The short answer:

Create a function $g(x)$ by letting each of the terms in the sum being a coefficient. Eventually, we want to find $g(1)$ .

Let’s begin the extended answer!

$g(x)=(\frac{3}{5})^0F_0+(\frac{3}{5})^1F_1x^1+(\frac{3}{5})^2F_2x^2+...$
$\frac{3}{5}xg(x)=(\frac{3}{5})^1F_0x^1+(\frac{3}{5})^2F_1x^2+(\frac{3}{5})^3F_2x^3+...$

Note that $g(1)$ is exactly the sum we want to find! Add the two together and combine like terms to get:

$g(x)+\frac{3}{5}xg(x)=(\frac{3}{5})^0F_0+(\frac{3}{5})^1(F_0+F_1)x^1+(\frac{3}{5})^2(F_1+F_2)x^2+...$

Remembering the Fibonacci recurrence relation (e.g. $F_1+F_2=F_3$ and such), and using it to simplify the coefficients above, we get:

$g(x)+\frac{3}{5}xg(x)=(\frac{3}{5})^0F_0+(\frac{3}{5})^1F_2x^1+(\frac{3}{5})^2F_3x^2+...$

We want to get “ $g(x)$ ” on the right hand side (RHS), and we see that multiplying the RHS by $\frac{3}{5}x$ will help. Because at least then we’ll have the same number for the exponents and the Fibonacci number!

$\frac{3}{5}xg(x)+(\frac{3}{5})^2x^2g(x)=(\frac{3}{5})^1F_0x^1+(\frac{3}{5})^2F_2x^2+(\frac{3}{5})^3F_3x^3+...$

Noting that $F_0=F_1$ , we see that the RHS is really $g(x)-F_0$ . (It has all the terms in $g(x)$ except for $F_0$ .)

Finally, we get $\frac{3}{5}xg(x)+(\frac{3}{5})^2x^2g(x)=g(x)-F_0$ .

Rearranging this equation, we get $g(x)=\frac{-F_0}{\frac{3}{5}x+(\frac{3}{5})^2x^2-1}$

Now for the easiest part… plugging 1 in for x, we get $g(1)=25$ . Since $g(1)$ was the infinite sum we were trying to find, we are done!

There are two things to note.

Because our method of solution wasn’t really dependent on the 3/5 at all, we can solve the problem for any other fraction (well… technically… it has to be within the radius of convergence…).
It might seem unintuitive that the original infinite sum will converge. Because you’d think that either the $(3/5)^n$ would decay at a different rate than $F_n$ increases. But it turns out that they both grow exponentially! (You can see that by looking at my previous post on the Fibonacci numbers and how to come up with a general equation for the nth term!). And so having one decay exponentially fast and the other grow exponentially fast end up “cancelingl” each other out. Which is a wishy-washy explanation as to why we can get such a beautiful convergence!

10 comments

i really like your solution. i solved the series on funmathblog as well, but arrived at a different answer than you. using a closed form for the fibonnaci series (involving the golden ratio), i directly computed the series and arrived at 15 as the answer. i’ve checked both my work, and yours, for convergence. my solution generates two geometric series, bit of which converge. your power series (relying on the closed form for fibonacci) certainly converges with x=1 (by the way, it isn’t the fraction that needs to be in the radius of convergence…the value of x needs to be in it. however the chosen fraction does influence the radius). i can’t see why our solutions result in different answers when both seem so right…weird…

How weird! I think I’ll probably try entering some numbers in Excel and see if they approach one or the other. Then we’ll know where to look.

Thanks for the heads up. I definitely won’t show this to my schools MathClub yet… Oh, wait, sad, there aren’t any more.

The year is just coming to a screeching halt! Sigh.

Sam.

Hi John,

I did enter some numbers in Excel and I’m getting a sum (after 401 terms) of 24.999827.

Sam.

hi john,
I directly computed the sum too,using the golden ratio and i arrived at the common answer of 25. I did gotten the answer of 15 before but it was a careless mistake on my part that the polarity of the signs for one of the golden ratio terms was wrong. hmm could you have made that too? Cheers

thanks for the updates. seems i made a mistake after-all. UnA, i used (phi^n – (1-phi)^n)/sqrt(5) with phi = (1+sqrt(5))/2 for my fibonacci closed form. i don’t recall seeing that the closed form required using the “negative” golden ratio,
(1-sqrt(5))/2 (although that is inseed 1-phi). i must have read things wrongly. anyway, thanks for clearing things up!

hooray…i found my mistake. i was summing the closed form from zero, which gave an incorrect first term in my resulting geometric series. it feels good to figure this one out. good fun!

Ahhhhhh. Makes sense. There was a whole discussion about that in the comment section in the Wild About Math post for the problem.

People say that it is more traditional to write F_0=0 and F_1=1, instead of F_0=1 and F_1=1.

I think that I’ve seen it both ways. But if forced to make a choice, I would come down on the F_0=0 and F_1=1 side.

i tend to disagree with you on that. i prefer F_0=0. but that wasn’t the problem i had. when i was using the direct approach i had to sum two (convergent of course) geometric series. using the usual closed form for the fibonacci numbers resulted in those series having zero for their first terms…which i didn’t catch until your solution. i re-indexed the geometric series, and got the 25. then i found a general solution for fractions of the form n/m. the result is m^2/(m^2-mn-n^2), and holds for 0<(n/m)<(sqrt(5)-1)/2. fun stuff! thanks again for posting your solution!

ahem…in my last i meant to say i prefer F_0=1. oops.

hi john,
oh i see! makes sense. i love when problems have different ways of working them.
sam.

Continuous Everywhere but Differentiable Nowhere

I have no idea why I picked this blog name, but there's no turning back now

MMM7 Solutions

10 comments

Leave a Reply Cancel reply

Share this:

Like this:

Related

10 comments

Leave a Reply Cancel reply