README.md

Overview:

This repository contains programs to calculate the sum of the even fibonacci numbers in the first n terms of the series. It is done in two ways: iterative version and O(1) version. Please look below on how to run the programs and the logic behind them.

Running the program:

1. Go the directory containing the makefile and run the command 'make'.
2. Run ./fibonacci to run the iterative version
3. Run ./fibonacci_advanced to run the O(1) version

Calculate the sum of the even fibonacci numbers in the first n terms of the series:

Observe that every third fibonacci number is even. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 ,…

So try to write Fn in terms of Fn-3 and Fn-6
Fn = Fn-1 + Fn-2
= Fn-2 + Fn-3 + Fn-3 + Fn-4
= Fn-2 + 2Fn-3 + Fn-4
= Fn-3 + Fn-4 + 2Fn-3 + Fn-4
= 3Fn-3 + 2Fn-4
= 4Fn-3 + Fn-6

Calculate the appropriate number of even numbers and use the above formula to sum them up.

Calculate the sum of the even fibonacci numbers in the first n terms of the series in O(1):

Again using the fact that every third number is even, the sum of even fibonacci numbers can be written as sum of
((phi)³ⁱ - (psi)³ⁱ)/5^1/2
where 'i' is the number of even fibonacci numbers for which we want to find the sum.
phi is (1+5^1/2)/2 and psi = phi^-1
Solving the above gives (1 / sqrt(5)) * ( phi³ * ((1 - phi^3k) / (1 - phi³)) - psi³ * ((1 - psi^3k) / (1 - psi³)))
where k is floor(n/3)