Isn't There A Formula For This?

Note that the Fibonacci numbers follow the identity $\sum_{k=1}^n F_k = F_{n+2} - 1,$ which can be proven by a simple induction on $n$ .

Setting $n=35$ means we need to calculate $\sum_{k=1}^{35} F_k = F_{37} - 1 = 24157817 - 1 = \boxed{24157816}$ (disclosure: I computed $F_{37}$ by Binet's formula)

Using this method, we can reduce the complexity of computing the sum of the first $n$ Fibonacci numbers down from $O(n)$ to $O(\log{n})$ by using fast exponentiation (where the floating point errors in Binet's formula can be avoided by using fast exponentiation of matrices over the integers)

A solution using c++. Mathematical solutions are also welcome :D

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include<iostream>
using namespace std;

int main()

{
    int a=1,b=1,i=1,c,s=2;  //a=b=1 are the initial terms which do not follow the fibonacci sequence, so s=a+b=1+1=2 from the beginning
    for(i=1;i<=35-2;i++) //since a=b=1 are the initial terms, loop should run for n-2 times as it is valid for n>2 only
                {
                    c=a+b;
                    a=b;
                    b=c;
                    s=s+c;
                }
    cout<<s;
    return 0;
}