Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with $1$ and $2$, the first $10$ terms will be: $$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$$
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
The Fibonacci sequence starts with $1, 2$. Every new term is the sum of the previous two:
$$1,\; 2,\; 3,\; 5,\; 8,\; 13,\; 21,\; 34,\; 55,\; 89,\; 144,\; \dots$$We need the sum of all even-valued terms that do not exceed $4{,}000{,}000$.
1. Where Are the Even Terms?
Look at the sequence modulo 2:
$$\underbrace{1}_{\text{odd}},\; \underbrace{0}_{\text{even}},\; \underbrace{1}_{\text{odd}},\; \underbrace{1}_{\text{odd}},\; \underbrace{0}_{\text{even}},\; \underbrace{1}_{\text{odd}},\; \underbrace{1}_{\text{odd}},\; \underbrace{0}_{\text{even}},\; \dots$$The pattern is odd, even, odd and repeats every 3 terms. Therefore the even terms sit exactly at indices:
$$2,\; 5,\; 8,\; 11,\; \dots \;=\; 3k-1 \quad\text{for }k=1,2,3,\dots$$So the even terms are precisely $a_{3k-1}$.
2. Deriving the Telescoping Identity
By the standard Fibonacci definition:
$$a_{3k+1} = a_{3k} + a_{3k-1} \tag{1}$$And because $a_{3k} = a_{3k-1} + a_{3k-2}$, we can rearrange to get:
$$a_{3k-2} = a_{3k} - a_{3k-1} \tag{2}$$Subtracting equation $(2)$ from equation $(1)$:
$$a_{3k+1} - a_{3k-2} = (a_{3k} + a_{3k-1}) - (a_{3k} - a_{3k-1}) = 2a_{3k-1}$$Dividing both sides by $2$ gives the telescoping identity:
$$\boxed{a_{3k-1} = \frac{1}{2}\left(a_{3k+1} - a_{3k-2}\right)}$$Quick check for $k=2$:
- LHS: $a_{5} = 8$
- RHS: $\frac{1}{2}(a_{7} - a_{4}) = \frac{1}{2}(21 - 5) = 8$ ✓
3. Summing via Telescoping
Let $S_n$ be the sum of the first $n$ even Fibonacci terms:
$$S_n = \sum_{k=1}^{n} a_{3k-1}$$Substitute the identity:
$$S_n = \sum_{k=1}^{n} \frac{1}{2}\left(a_{3k+1} - a_{3k-2}\right) = \frac{1}{2}\sum_{k=1}^{n}\left(a_{3k+1} - a_{3k-2}\right)$$Write out the terms inside the sum:
| $k$ | Term: $a_{3k+1} - a_{3k-2}$ |
|---|---|
| 1 | $a_{4} - a_{1}$ |
| 2 | $a_{7} - a_{4}$ |
| 3 | $a_{10} - a_{7}$ |
| $\vdots$ | $\vdots$ |
| $n$ | $a_{3n+1} - a_{3n-2}$ |
Everything in the middle cancels (telescopes!). We are left with only the last positive term and the first negative term:
$$\sum_{k=1}^{n}\left(a_{3k+1} - a_{3k-2}\right) = a_{3n+1} - a_{1} = a_{3n+1} - 1$$Therefore:
$$\boxed{S_n = \frac{1}{2}\left(a_{3n+1} - 1\right)}$$This is a closed-form expression. Instead of adding up terms one by one, we only need to find the single Fibonacci number $a_{3n+1}$.
4. Applying to the $4{,}000{,}000$ Limit
List the even terms until they exceed $4{,}000{,}000$:
| $k$ | Index $3k-1$ | Value $a_{3k-1}$ |
|---|---|---|
| 1 | 2 | 2 |
| 2 | 5 | 8 |
| 3 | 8 | 34 |
| 4 | 11 | 144 |
| 5 | 14 | 610 |
| 6 | 17 | 2,584 |
| 7 | 20 | 10,946 |
| 8 | 23 | 46,368 |
| 9 | 26 | 196,418 |
| 10 | 29 | 832,040 |
| 11 | 32 | 3,524,578 |
| 12 | 35 | 14,930,352 (exceeds limit) |
So $n = 11$ even terms qualify. The next index we need is:
$$3n+1 = 3(11)+1 = 34$$From the Fibonacci sequence, $a_{34} = 9{,}227{,}465$.
Plug into the closed form:
$$S_{11} = \frac{1}{2}\left(9{,}227{,}465 - 1\right) = \frac{9{,}227{,}464}{2} = \boxed{4{,}613{,}732}$$5. Why This Is Powerful
| Method | Work Required |
|---|---|
| Brute-force | Iterate every Fibonacci term, check if even, add if $\leq 4{,}000{,}000$ |
| Telescoping | Find one identity, count $n=11$, look up $a_{34}$, compute $\frac{a_{34}-1}{2}$ |
The telescoping method turns a summation problem into a single subtraction and division, all because the even terms were cleverly rewritten as differences of other Fibonacci terms that collapse when summed.