Closed form for the sum of even fibonacci numbers?

Question

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.

Answer 1

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$.

This answer requires somewhat sophisticated knowledge about linear recurrences.

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}$.

Answer 2

$$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}$$

Answer 3

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.

Answer 4

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)$$

Answer 5

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$.