The second problem is:
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Lets again start with a python script solving this:
Analytically, I have not gotten far.
First thing I notice is that is only even if , else it is odd.
Think in binary or follow my proof if you do not believe me:
First step, is always even:
Basis:
Assumption:
Holds to , therefore is even
Induction:
is always even, is even and the sum of even numbers is even as well. Ergo is always even!
But we still have to proof that are the ONLY even numbers!
Lets take a look at which should be always odd:
Basis:
Assumption:
Holds to , therefore is odd
Induction:
A sum of a odd and an even number is always odd hence is odd
What is left? !
Basis:
Assumption:
Holds to , therefore is odd
Induction:
And again, odd + even = odd!
So the only even numbers in the Fibonacci sequence are the ones
with !
But that’s it, no idea how to battle this problem further.
Update
Well, after some thinking, I guess I found an analytic solution.
Lets have look which Fibonacci numbers are in the sum of all even Fibonacci numbers:
(remember, every third is even)
But these could also be written like this:
This means that
and therefore we can also write it as:
We now only need to know what the sum of all Fibonacci numbers to some n is:
Wherefore, the solution is: