Golden Power Series!

Last updated on 3 min read Math Lecture

As you probably know, I wear my heart on my sleeve:

Well, I took the golden opportunity (ha!) to bring the golden ratio \Phi = \frac{1+\sqrt{5}}{2}into Calc 2 this week, using it (and its little pal \Psi = \frac{1-\sqrt{5}}{2}) to find a closed formula for the n-th term of the Fibonacci sequence.

The ubiquitous Fibonacci sequence! It’s something you may have encountered out in the wild. You know, it goes a little like this:

F_0 = 1, \, \, F_1 = 1, \, \, F_n = F_{n-1} + F_{n-2},

so F_2 = 2, \, \, F_3 = 3, \, \, F_4 = 5, \, \, F_5 = 8, \, \, F_6 = 13, \, \, F_7 = 21 \, \, \ldots.

And let’s say for some reason, you need to cook up F_{108}. I hope you have some time on your hands if you’re planning to add all the way up to that. Instead, wouldn’t it be nice if we had a simple formula that we could use — i.e., a formula that was not recursive — to figure out the n-th Fibonacci number?

Luckily, such a formula exists, and there are lots of ways to find it. In this post, we’ll find it using power series. Read on, brave blogosphere traveler.

First thing we’re going to do is build a power series:

\begin{matrix} F(x) &= \displaystyle{\sum_{n=0}^\infty F_n \cdot x^n} \hfill \\ &= 1 + 1\cdot x + 2 \cdot x^2 + 3 \cdot x^3 + 5 \cdot x^4 + 8 \cdot x^5 + 13 \cdot x^6 + 21 \cdot x^7 + \cdots \end{matrix}

Remember that $F_n = F_{n-1} + F_{n-2}$ as long as $n \geq 2$. This means that we can rewrite our power series:

\begin{matrix} F(x) &= \displaystyle{\sum_{n=0}^\infty F_n \cdot x^n} \hfill \\ &= 1 + 1\cdot x + \displaystyle{\sum_{n = 2}^\infty \left(F_{n-1} + F_{n-2}\right)\cdot x^n} \hfill \\ &= 1 + 1\cdot x + \displaystyle{\sum_{n = 2}^\infty \left(F_{n-1}\cdot x^n + F_{n-2}\cdot x^n\right)} \hfill \\ &= 1 + 1\cdot x + \displaystyle{\sum_{n = 2}^\infty \left(F_{n-1}\cdot x^n\right) + \sum_{n = 2}^\infty \left(F_{n-2}\cdot x^n\right)} \hfill\end{matrix}

So far so good? We’re not done yet, though. We can do a little reindexing. In particular, note that by tweaking the index na little bit, we have equalities:

\begin{matrix}\hfill \displaystyle{\sum_{\mathbf{n = 2}}^\infty \left(F_{\mathbf{n-1}}\cdot x^\mathbf{n}\right)} &= \hfill \displaystyle{\sum_{\mathbf{n = 1}}^\infty \left(F_{\mathbf{n}}\cdot x^{\mathbf{n+1}}\right)}\hfill &= x \cdot (F(x) - 1) \hfill \\ \hfill \displaystyle{\sum_{\mathbf{n = 2}}^\infty \left(F_{\mathbf{n-2}}\cdot x^\mathbf{n}\right)} &= \hfill \displaystyle{\sum_{\mathbf{n = 0}}^\infty \left(F_{\mathbf{n}}\cdot x^{\mathbf{n+2}}\right)} \hfill &= x^2 \cdot F(x) \hfill \end{matrix}

You might want to grab a coffee and some scratch paper to make sure you believe all those equalities up there. No worries; the rest of the post will be here when you’re ready.

Okay — agree with me? Good! Remember that we have figured out

F(x) = 1 + 1\cdot x + \displaystyle{\sum_{n = 2}^\infty \left(F_{n-1}\cdot x^n\right) + \sum_{n = 2}^\infty \left(F_{n-2}\cdot x^n\right)}

so substituting our work from above, we obtain

\begin{matrix} F(x) &= 1 + 1\cdot x + x\cdot(F(x) - 1) + x^2 \cdot F(x) \hfill \\ &= 1 + x\cdot F(x) + x^2 \cdot F(x)\end{matrix}

so finally, if we solve all of that for F(x), we get the marvelous rational function

F(x) = \displaystyle{ \frac{-1}{x^2+x-1}.}

All right, kids. Now the question becomes: (a) do you remember Partial Fraction Decomposition from earlier in the semester? and (b) do you remember the quadratic formula? We’re going to need both of those things. Let me google that for you… Partial Fraction Decomposition and Quadratic Formula.

Now that you’ve had a chance to review, you can double check that x^2+x-1 = (x+\Phi)(x+\Psi)where \Phi = \frac{1+\sqrt{5}}{2}, the Golden Ratio, and \Psi = \frac{1 - \sqrt{5}}{2}, which we’ll call the Aluminum Ratio for the purposes of this post. Maybe it’ll catch on?

And this means that

\displaystyle{\frac{-1}{x^2 + x - 1} = \frac{A}{x+\Phi} + \frac{B}{x+\Psi}.}

I’ll let you check my math here, but I’d wager a cat that A = \frac{-1}{\sqrt{5}}\Phi \, , \, latex B = \frac{1}{\sqrt{5}}\Psi.

First, let’s work with \frac{A}{x+\Phi}.

\begin{matrix} \displaystyle{\frac{A}{x+\Phi} } &= \displaystyle{\frac{-1}{\sqrt 5} \frac{\Phi}{x+\Phi} } \hfill \\ &= \displaystyle{\frac{-1}{\sqrt 5} \frac{1}{1+\frac{x}{\Phi}} } \hfill \\ &= \displaystyle{\frac{-1}{\sqrt 5} \sum_{n=0}^\infty \left(\frac{x}{\Phi}\right)^n} \hfill \\ &= \displaystyle{\frac{-1}{\sqrt 5} \sum_{n = 0}^\infty x^n \frac{1}{\Phi^n}} \hfill \\ &= \displaystyle{\frac{1}{\sqrt 5} \sum_{n = 0}^\infty x^n \Psi^n.}\hfill \end{matrix}

That last equality comes from the fact that

\Phi\Psi = -1so

\frac{1}{\Phi} = -\Psi

and vice versa. Similarly,

\displaystyle{ \frac{B}{x+\Psi} = \frac{-1}{\sqrt 5} \sum_{n = 0}^\infty x^n \Phi^n}.

This means that \displaystyle{ F(x) = \frac{1}{\sqrt 5} \sum_{n = 0}^\infty \left(\Phi^n - \Psi^n\right) x^n}. Remember that the coefficient of $x^n$ in $F(x)$ is actually $F_n$, and therefore — drumroll, please! —

\displaystyle{\begin{LARGE}F_n = \frac{1}{\sqrt 5} \left( \Phi^n - \Psi^n\right)\end{LARGE}.}

And so to calculate F_{108}, you can just plug \frac{1}{\sqrt 5} \left( \left(\frac{1+\sqrt 5}{2}\right)^{108} - \left(\frac{1-\sqrt{5}}{2}\right)^{108}\right)into your favorite calculator. For instance, wolfram alpha calculates that this Fibonacci number is merely…

\begin{huge}16,641,027,750,620,563,662,096.\end{huge}