# Sum of Fibonacci-Numbers

Is there a closed formula for the sum of the first $n$ even (or odd) Fibonacci numbers, like there is one for the $n$th number (Moivre-Binet)?

-
– A.E Sep 5 '13 at 21:16
Do you mean the even Fibonacci numbers, or do you mean the Fibonacci numbers with even indices? – Brian M. Scott Sep 5 '13 at 21:22
Add the Binet formulae for the odds or evens by summing the geometric progressions which arise. Write out the first few terms to see what is going on. – Mark Bennet Sep 5 '13 at 21:22
@BrianM.Scott the even numbers. But the sum of numbers with even indices would be interesting too. – user127.0.0.1 Sep 5 '13 at 21:23
Further to @BrianM.Scott's comment - note that every third Fibonacci number is even, so that gives a GP too. The odd numbers can be summed as two GPs (or as the sum of all the numbers less the sum of the even ones). – Mark Bennet Sep 5 '13 at 21:24

Note that $F_n$ is even iff $n\equiv 0\pmod 3$ because the Fibonacci recursion modulo $2$ gives the sequence $0,1,1,0,1,1,\ldots$

So we want to find a closed expression for $$s_n=\sum_{k=0}^n F_{3k}.$$ We find the recursion (why?) $$s_{n+1} = 4s_n+s_{n-1}+2$$ and from this $$s_n =a(2+\sqrt 5)^n+b(2-\sqrt 5)^n -\frac12$$ where $a,b$ can be determined from the cases $n=0$ and $n=1$, for example.

-
Note that because $F_{3k}=F_{3k-1}+F_{3k-2}$ it is particularly easy to sum the odd numbers once the sum of the evens is known. – Mark Bennet Sep 5 '13 at 21:56

Let $\varphi=\frac12\left(1+\sqrt5\right)$ and $\widehat\varphi=\frac12\left(1-\sqrt5\right)$, so that $F_n=\frac1{\sqrt5}\left(\varphi^n-\widehat\varphi^n\right)$. Then

$$\varphi^3=\left(\frac{1+\sqrt5}2\right)^3=2+\sqrt5\qquad\text{and}\qquad\widehat\varphi^3=\left(\frac{1-\sqrt5}2\right)^3=2-\sqrt5\;,$$

so the sum of the first $n$ even Fibonacci numbers is

\begin{align*} \sum_{k=0}^{n-1}F_{3k}&=\frac1{\sqrt5}\sum_{k=0}^{n-1}\left(\varphi^{3k}-\widehat\varphi^{3k}\right)\\\\ &=\frac1{\sqrt5}\left(\sum_{k=0}^{n-1}\varphi^{3k}-\sum_{k=0}^{n-1}\widehat\varphi^{3k}\right)\\\\ &=\frac1{\sqrt5}\left(\frac{\varphi^{3n}-1}{\varphi^3-1}-\frac{\widehat\varphi^{3n}-1}{\widehat\varphi^3-1}\right)\\\\ &=\frac{(2+\sqrt5)^n-1}{5+\sqrt5}-\frac{1-(2-\sqrt5)^n}{5-\sqrt5}\\\\ &=\frac{(2+\sqrt5)^n}{5+\sqrt5}+\frac{(2-\sqrt5)^n}{5-\sqrt5}-\left(\frac1{5+\sqrt5}+\frac1{5-\sqrt5}\right)\\\\ &=\frac{(2+\sqrt5)^n}{5+\sqrt5}+\frac{(2-\sqrt5)^n}{5-\sqrt5}-\frac12\;. \end{align*}

Moreover, $2-\sqrt5\approx-0.23607$, and $5-\sqrt5\approx2.76393$, so even for $n=1$ the middle term is only about $-0.08541$, and it decreases rapidly as $n$ increases. Thus, you want the integer nearest

$$\frac{(2+\sqrt5)^n}{5+\sqrt5}-\frac12\;,$$

which is

$$\left\lfloor\frac{(2+\sqrt5)^n}{5+\sqrt5}\right\rfloor\;.$$

-