# Closed form for the sum of even fibonacci numbers?

I recently took a look a project euler, and I am trying to think of a smart way to do number 2. I looked at the sequence, and I saw that the question is basically asking for $$\sum_{i=1}^n F_{3i}$$

For whatever n is gives me the nth even under a million. So, I did some fiddling around with this, and I got this to be equivalent to

$$\sum_{i=0}^{n-1} F_{3i-1}(3^{n-i}-1)$$

I was wondering, is there even a closed form for something like this? Or am I wasting my time? I couldn't find a closed form online anywhere.

• Find the Binet formula for the Fibonaccis, and you'll see this can be done using geometric series. Mar 7, 2013 at 0:05
• What do you mean with "a smart way to do number $2$"?. I hope you don't mean that number $2$... Mar 7, 2013 at 1:07

$$F_k=\frac{\left(1+\sqrt{5}\right)^k}{2^k\sqrt{5}}-\frac{\left(1-\sqrt{5}\right)^k}{2^k\sqrt{5}}$$ $$\sum_{k=1}^nF_{3k}=\sum_{k=1}^n\frac{\left(1+\sqrt{5}\right)^{3k}}{2^{3k}\sqrt{5}}-\sum_{k=1}^n\frac{\left(1-\sqrt{5}\right)^{3k}}{2^{3k}\sqrt{5}}$$ $$=\frac{1}{\sqrt5}\sum_{k=1}^n\left(\frac{1+\sqrt{5}}{2}\right)^{3k}-\frac{1}{\sqrt5}\sum_{k=1}^n\left(\frac{1-\sqrt{5}}{2}\right)^{3k}$$ $$\text{ but we have , } x^3+x^6+x^9...x^{3n}=x^3\frac{x^{3n}-1}{x^3-1}$$ $$\text{ so then, }$$ $$=\frac{1}{\sqrt5}\sum_{k=1}^n\left(\frac{1+\sqrt{5}}{2}\right)^{3k}-\frac{1}{\sqrt5}\sum_{k=1}^n\left(\frac{1-\sqrt{5}}{2}\right)^{3k}$$ $$=\frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt{5}}{2}\right)^3\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{3n}-1}{\left(\frac{1+\sqrt{5}}{2}\right)^3-1}-\left(\frac{1-\sqrt{5}}{2}\right)^3\frac{\left(\frac{1-\sqrt{5}}{2}\right)^{3n}-1}{\left(\frac{1-\sqrt{5}}{2}\right)^3-1}\right)=\frac{F_{3n+2}-1}{2}$$

$$=\sum_{k=1}^{n}F_{3k}$$

• Note that if $\alpha=\frac{1\pm \sqrt{5}}{2}$ then $\alpha^3 - 1 = 2\alpha$, so you can simplify this a bit. Mar 7, 2013 at 1:02
• +1. But this answer woul be easier to read with "\left(...\right)" rather than default parentheses sizes. Mar 7, 2013 at 1:06
• @Ethan you do realise this can actually be simplified to $\sum\limits_{k=1}^{n}{F_{3k}}=\frac{F_{3n+2}-1}{2}$? (which incidentally can be computed in $O(log(n))$ time) Mar 7, 2013 at 2:43
• Thanks, @Ivan, I missed that formula, even though it obviously falls out of my matrix formula. Mar 7, 2013 at 3:00

This answer does not give a closed form, but does give an approach to computing this sum.

The general closed form is still not always useful for computation, because you need to be able to compute some real values to great precision.

Also note that I start at $i=0$. This doesn't affect anything since $F_0=0$.

There is a closed form for $F_n = a_1\alpha_1^n + a_2\alpha_2^n$ for some real numbers $a_1,\alpha_1,a_2,\alpha_2$. Then:

\begin{align}G_n = \sum_{i=0}^n F_{3i} &= a_1\frac{\alpha_i^{3n+3} -1}{\alpha_1-1}+a_2\frac{\alpha_2^{3n+3} -1}{\alpha_2-1}\\ &=b_1\alpha_1^{3n} + b_2\alpha_2^{3n} + b_3\cdot 1^n \end{align}

for some $b_1,b_2,b_3$.

Now you need to know a bit about this sort of recursive linear relationship, but if you look at the polynomial $(x-\alpha_1^3)(x-\alpha_2^3)(x-1) = (x^2-4x-1)(x-1) = x^3-5x^2+3x+1$, this yields a recurrence relationship:

$$G_{n+3} = 5G_{n+2} -3G_{n+1} - G_{n}$$

That gives you a recursive way to compute your sum, $G_n$ in general.

Another approach is to use the matrix formula:

$$\left(\begin{matrix}1 & 1\\1&0\end{matrix}\right)^n = \left(\begin{matrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{matrix}\right)$$

If $A=\left(\begin{matrix}1 & 1\\1&0\end{matrix}\right)$, then the series $\sum_{i=0}^n A^{3i}$ has, in the off diagonal, the sum that you want.

But you get the normal sum of a geomtric series:

$$\sum_{i=0}^n A^{3i} = (A^{3n+3}-I)(A^3-I)^{-1}$$

Now, $A$ satisfies an equation, $A^2 - A - I = 0$, and therefore $A^3-I=2A$. Also $A^{-1} = A-I$, so you want to compute: $$\frac{1}{2}(A^{3n+3} - I)(A-I)$$

Now, it might not seem much easier to compute $A^{3n+3}$, but you can do that with only $O(\log(3n+3))$ multiplications by using the method of exponentiation by squaring.

once you've computed this matrix, take the value off the diagonal.

Ivan Loh below noted that we can do better in a comment in the other answer, and it applies here, too. We know $A^{3n+3}$, so we can write this all as:

\begin{align}(A^{3n+3}-I)(A-I) &= \frac 1 2 \left(\begin{matrix}F_{3n+4}-1&F_{3n+3}\\F_{3n+3}&F_{3n+2}-1\end{matrix}\right)\left(\begin{matrix}0 & 1\\ 1 & -1\end{matrix}\right)\\ &=\frac{1}{2}\left(\begin{matrix}*&*\\F_{3n+2}-1&*\end{matrix}\right) \end{align}

(We don't care about the other entries.)

So the sum we are looking for is $\frac{F_{3n+2}-1}{2}$.

• The above is far more complex computationally than just calculating the answer using the definition of the Fibonacci numbers in the obvious way. Mar 7, 2013 at 0:54
• Do you mean "harder" computationally (in terms of time computing,) or harder to understand? I think $O(\log n)$ is pretty good in the matrix approach. (It's probably a bit more than that, but certainly better than $O(n)$, which the bull-headed approach would give you.) @RobArthan Mar 7, 2013 at 0:56
• I just meant complex in the informal sense and was reading "smart" in the question as appropriate for a Project Euler problem, i.e. finding the answer to a specific problem efficiently. The problem in question is about quite small numbers, so a fairly "smart" solution is the naive one. Mar 7, 2013 at 1:11
• A lot of the PE problems have answers like this. For example, some of the earlier problems have answers that are $O(1)$ where the bull-headed answer is $O(n)$. It depends on what your goal is when solving PE problems - if you just want to code an answer, then of course, the linear approach is often faster. If you want a learning experience, a lot of PE problems give you room to explore. This poster in particular clearly wanted to explore. @RobArthan Mar 7, 2013 at 1:20
• This is great! this is exactly what I was looking for! I would have never thought about doing this with matrices. Mar 7, 2013 at 18:27

Using $$F_{3k}=F_{3k-1}+F_{3k-2} = \frac12\left(F_{3k}+F_{3k-1}+F_{3k-2}\right)$$, since this is Fibonacci,

and $$\sum\limits_{k=1}^{n}F_{k}=F_{n+2}-1$$, which has an easy proof by induction,

you have $$\sum\limits_{k=1}^{n}F_{3k} = \frac{1}{2}\sum\limits_{k=1}^{n}(F_{3k}+F_{3k-1}+F_{3k-2})=\frac{1}{2}\sum\limits_{k=1}^{3n}F_{k} = \frac12\left(F_{3n+2}-1\right)$$

For variety, if $\varphi$ is the golden ratio, then

$$\varphi^n = F_{n-1} + F_n \varphi$$

(where $F_0 = 0$ and $F_1 = 1$... and $F_{-1} = 1$) The same equation holds for $\bar{\varphi}$, the other root of $x^2 = x+1$. (not the complex conjugate)

Therefore

$$\sum_{i=0}^n \varphi^{3i} = (\cdots) + \left(\sum_{i=0}^n F_{3i} \right) \varphi$$

We can get rid of the unwanted term by by subtracting off its conjugate:

$$\sum_{i=0}^n \varphi^{3i} - \bar{\varphi}^{3i} = \left(\sum_{i=0}^n F_{3i} \right) (\varphi - \bar{\varphi})$$

And then you can do whatever you like from there. This is, of course, similar to the other answers; I just like how it's organized.

• It's also similar to my matrix answer, since $A^n = F_{n-1}I+F_nA$ - essentially, since $A$ has $\phi$ and $\bar\phi$ as eigenvalues, it stands in for both of them simultaneously. Mar 7, 2013 at 19:25

Here is how I would do it in terms of even Fibonacci numbers alone.

We first render

$$F_{3n+3}=F_{3n+2}+F_{3n+1}=2F_{3n+1}+F_{3n}$$

$$=3F_{3n+2}+2F_{3n-1}=3F_{3n}+F_{3n-1}+F_{3n-1}=4F_{3n}+F_{3n-1}-F_{3n-2}$$

$$\color{blue}{F_{3n+3}=4F_{3n}+F_{3n-3}}$$

which defines a recursion for the even Fibonacci numbers alone.

We sum this for subscripts $$3×1+3$$ through $$3n+6$$ on the left. Only the last $$n$$ terms of $$S_{+1}$$ and $$S_{n+2}$$ are included in this sum, so some initial values must he subtracted off:

$$S_{n+2}-2-8=4(S_{n+1}-2)+S_n$$

$$S_{n+2}=4S_{n+1}+S_n+2$$

and the incrementations

$$S_{n+1}=S_n+F_{3n+3}$$

$$S_{n+2}=S_n+F_{3n+3}+F_{3n+6}$$

And then

$$S_n+F_{3n+3}+F_{3n+6}=4S_n+4F_{3n+3}+S_n+2$$

Upon solving

$$\color{blue}{S_n=(F_{3n+6}-3F_{3n+3}-2)/4}$$

Thus the sum of the first several even Finonacci numbers is rendered in terms of the next two higher even Fibonacci numbers; for instance $$n=2$$ gives $$2+8=(144-(3×34)-2)/4=10$$.