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 by letting each of the terms in the sum being a coefficient. Eventually, we want to find .
Let’s begin the extended answer!
Note that is exactly the sum we want to find! Add the two together and combine like terms to get:
Remembering the Fibonacci recurrence relation (e.g. and such), and using it to simplify the coefficients above, we get:
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 would decay at a different rate than 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!