I was looking at some of the Project Euler problems the other day and I found some pretty neat solutions using generating functions and Mathematica. For example:
“By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.”
My solution in Mathematica was:
Normal[Series[2/(1 - 4 x - x^2), {x, 0, 10}]] /. x -> 1
To understand why this works, first realize that the Fibonacci numbers go in an odd, odd, even pattern (this is easily proven). Second, if f(n) is the nth Fibonacci number, then f(n) = 4 f(n-3) + f(n-6). This is not as easy to prove, but it is still not so hard. And lastly, we just have to find a polynomial whose coefficient of x^n is f(n). This is the interesting part.
Let p(x) = 2 + 8 x + 34 x^2 + … + g(n) x^n + … where g(n) is the nth even Fibonacci number.
4x p(x) = 8 x + 32 x^2 + … + 4 g(n) x^(n+1) + …
p(x) - 4 x p(x) = 2 + x^2 (2 + 8 x + … + g(n) x^n + …) (prove this with the recursion above)
p(x) - 4 x p(x) = 2 + x^2 p(x)
p(x) = 2/(1 - 4 x - x^2)
So p(x) expanded into a power series will have coefficients of all the even Fibonacci numbers. So in comes the power of Mathematica. The Series function gives a power series of p(x) approximated to however many terms (a little inspection will tell you that more than 10 will exceed 4 million) plus an error term (which the function Normal gets ride of). Then all you have to do is plug in 1 for x and it will return the sum of the first 10 terms of the power series approximation for p(x). Problem solved!
