Day: June 3, 2008

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.

  1. 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…).
  2. 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!