# Prove that the sum of the first $n$ even terms of the Fibonacci sequence is given by $(F_{3n} + F_{3n + 3} - 2) / 4$ not using induction?

each even term in the Fibonacci sequence has a position index which is a multiple of 3, therefore the even term is $F_{3n}$:

$F_{3 (0)} = 0$

$F_{3 (1)} = 2$

$F_{3 (2)} = 8$

$F_{3 (3)} = 34$

$F_{3 (4)} = 144$

...

How can I prove and reconstruct the formula which states that the sum of the first $n$ even terms (2, 8, 34, ...) of the Fibonacci sequence is given by $(F_{3n} + F_{3n + 3} - 2)/4$ not using induction?

For example, given:

$U_{n} = F_{3n}$

$S_{n} = U_{0} + U_{1} + U_{2} + U_{3} + ... + U_{n}$

How to derive the formula $S_n = (U_{n} + U_{n + 1} - 2) / 4 = \frac{(F_{3n} + F_{3n + 3} - 2)}{4}$?

• Have you tried finding a recursive formula for this sequence similar to the one defining the Fibonacci numbers? – Nate May 4 '15 at 18:55
• @Nate Should we say that using that recurrence relation is also using induction? I think the only possible way to avoid induction is to use the close form formula. – Salomo May 4 '15 at 18:57

It is relatively easy to show that , for $n \geqslant 1$, $4F_{3n} = F_{3(n+1)}-F_{3(n-1)}$(Hint: Use the definition of the Fibonacci numbers). Using this identity, we can now show that $$\sum_{k=1}^n F_{3k} = \frac{(F_{3n} + F_{3n + 3} - 2)}{4}$$

by summing up $4F_{3k}$, where k goes from $1$ to $n$.

\begin{align} 4 \sum_{k=1}^n F_{3k} &= \sum_{k=1}^n 4F_{3k}= \sum_{k=1}^n F_{3(k+1)}-F_{3(k-1)} \\ &= \sum_{k=1}^n F_{3(k+1)} - \sum_{k=1}^n F_{3(k-1)} \\&= \sum_{k=2}^{n+1} F_{3k} - \sum_{k=0}^{n-1} F_{3k} \\ &= F_{3n} + F_{3n + 3} + \sum_{k=2}^{n-1} F_{3k} - \sum_{k=2}^{n-1} F_{3k} -2 \\ &= F_{3n} + F_{3n + 3} - 2 \end{align}

Dividing everything by $4$ , we reach the desired equality.

• Sorry for the late response, thanks for the passages! – user3019105 May 7 '15 at 8:23

What is being asked is to find the sum \begin{align} \sum_{r=0}^{n} F_{3r}. \end{align} This is obtained in the following way. \begin{align} \sqrt{5} \, S_{n} &= \sum_{r=0}^{n} \left( \alpha^{3r} - \beta^{3r} \right) \\ &= \frac{1 - \alpha^{3n+3}}{1-\alpha^{3}} - \frac{1-\beta^{3n+3}}{1-\beta^{3}} \\ &= - \frac{1}{2\alpha} + \frac{\alpha^{3n+2}}{2} + \frac{1}{2 \beta} - \frac{\beta^{3n+2}}{2} \\ &= \frac{\sqrt{5}}{2} \left( F_{3n+2} -1 \right). \end{align} From this it can be stated that \begin{align} \sum_{r=0}^{n} F_{3r} = \frac{F_{3n+2} - 1}{2}. \end{align}

The formulas used in this evaluation are: \begin{align} F_{n} = \frac{\alpha^{n} - \beta^{n}}{\alpha - \beta} \end{align} which is Binet's formula and \begin{align} \sum_{r=0}^{n} x^{r} = \frac{1 - x^{n+1}}{1-x}. \end{align} Other components used: \begin{align} 1 - \alpha^{3} &= 1 - \alpha(1 + \alpha) = 1 - \alpha - (1 + \alpha) = - 2 \alpha \\ 1 - \beta^{3} &= - 2 \beta \\ \alpha \beta &= -1 \end{align}

• I didn't fully understand all the passages, could you give me some links or explain more thorough the passages you took? I know that $(α^{3r}−β^{3})$ comes from the Binet's formula, where $α = (1 + \sqrt{5})/2$ and $β = -1/α$. In the following passages you are using some properties of the geometric series, aren't you? – user3019105 May 4 '15 at 19:29
• @user3019105 The components used have been added. Note that $\alpha^{2} = 1 + \alpha$ and the same applies to $\beta$. – Leucippus May 4 '15 at 19:54
• Thanks for the elucidation, your formula is really really nice! – user3019105 May 7 '15 at 21:05