Ah nice to see maths, I came up with the same thing however with a different approach of using generator functions.

Let us forget about fibonacci and think of the even fibonacci as a new series. (I probably think there would be a mathematical way of deducing it, but I just used brute force to find it out)

So the recurrence relation for this series would be

F_{n}= 4F_{n-1} + F_{n-2}.
To find out the Sum of n elements in this series (let's call this S_{n}), we can rewrite the recurrence relation like this: 4F_{n-1} = F_{n} - F_{n-2}
and we can move all n's by 1: 4F_{n} = F_{n+1} - F_{n-1}

Now we can use the same logic to finder other n's: 4F_{n} = F_{n+1} - F_{n-1} 4F_{n-1} = F_{n} - F_{n-2} 4F_{n-2} = F_{n-1} - F_{n-3} 4F_{n-3} = F_{n-2} - F_{n-3} ... ... 4F_{4} = F_{5} - F_{3} 4F_{3} = F_{4} - F_{2} 4F_{2} = F_{3} - F_{1} 4F_{1} = 4F_{1}

For folks not familiar with this technique, we are simply doing to cancel out similar terms when we add all equations. (Note all items in pair are canceled out since x - x = 0).

If you notice the left hand side is essentially equivalent to 4S_{n}

Now we can finally write the relation between sum and series as:

S_{n}= ( F_{n+1} + F_{n} - F_{2} + 3F_{1} ) / 4

The point is this avoids the for loop for summing all the values. Go ahead and try substituting values and you will find this sums it up. You will have to use F(1) = 2 and F(2) = 8.

Now that we have removed one for loop, how do we get a direct formula for getting the F_{n}.

This involves a bit more complicated math(for adventurous folks visit austinrochford.com/posts/2013-11-0...).
In short the closed form for this recurrence relation is
And if you compute the roots and follow along the url I posted above, you will end up with this

This gives us a function to compute F_{n} .

Now we can combine our summing and this formula to get a simple O(1) arithmetic function to get the sum. Side note: Running a for loop will take much less brain time :P

## re: Project Euler #2 - Even Fibonacci numbers VIEW POST

VIEW PARENT COMMENT VIEW FULL DISCUSSIONAh nice to see maths, I came up with the same thing however with a different approach of using generator functions.

Let us forget about fibonacci and think of the even fibonacci as a new series. (I probably think there would be a mathematical way of deducing it, but I just used brute force to find it out)

So the recurrence relation for this series would be

F._{n}= 4F_{n-1}+ F_{n-2}To find out the Sum of n elements in this series (let's call this S

_{n}), we can rewrite the recurrence relation like this:4F_{n-1}= F_{n}- F_{n-2}and we can move all n's by 1:

4F_{n}= F_{n+1}- F_{n-1}Now we can use the same logic to finder other n's:

4F_{n}= F_{n+1}- F_{n-1}4F_{n-1}= F_{n}- F_{n-2}4F_{n-2}= F_{n-1}- F_{n-3}4F_{n-3}= F_{n-2}- F_{n-3}......4F_{4}= F_{5}- F_{3}4F_{3}= F_{4}- F_{2}4F_{2}= F_{3}- F_{1}4F_{1}= 4F_{1}For folks not familiar with this technique, we are simply doing to cancel out similar terms when we add all equations. (Note all items in pair are canceled out since

`x - x = 0`

).4F_{n}= F_{n+1}-~~F~~_{n-1}4F_{n-1}= F_{n}-~~F~~_{n-2}4F_{n-2}=~~F~~-_{n-1}~~F~~_{n-3}4F_{n-3}=~~F~~-_{n-2}~~F~~_{n-3}......4F_{4}=~~F~~-_{5}~~F~~_{3}4F_{3}=~~F~~- F_{4}_{2}4F_{2}=~~F~~- F_{3}_{1}4F_{1}= 4F_{1}4F

_{n}+ 4F_{n-1}+ 4F_{n-2}+ ... + 4F_{2}+ 4F_{1}= F_{n+1}+ F_{n}- F_{2}+ 3F_{1}If you notice the left hand side is essentially equivalent to

4S_{n}Now we can finally write the relation between sum and series as:

The point is this avoids the for loop for summing all the values. Go ahead and try substituting values and you will find this sums it up. You will have to use

`F(1) = 2`

and`F(2) = 8`

.Now that we have removed one

`for loop`

, how do we get a direct formula for getting the F_{n}.This involves a bit more complicated math(for adventurous folks visit austinrochford.com/posts/2013-11-0...).

In short the closed form for this recurrence relation is

And if you compute the roots and follow along the url I posted above, you will end up with this

This gives us a function to compute F

_{n}.Now we can combine our summing and this formula to get a simple O(1) arithmetic function to get the sum. Side note: Running a for loop will take much less brain time :P

I applaud your solution, fellow math lover! π