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.

Solution 1:

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

Solution 2:

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

Solution 3:

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