DEV Community

Kartik Bhatia for eduAlgo

Posted on

Sum of N Fibonacci Numbers

If you read the title and you have that feeling for algorithms you already know the way to Sum Up Fibonacci Numbers. But let's see it the other way round , Let's do it today in a more Mathy way ( ofcourse the optimal ).

(If you don't Know Fibonacci Numbers)
Fibonacci numbers is a series of numbers created in such a way that the current term in the series is the sum of previous two terms, ofcourse the first two Terms in Fibonacci are 0,1-> and then it continues this way after 0,1,-> 1,2,3,5 or you can generalize this as ...

F[0]=0
F[1]=1
F[i]= F[i-1]+F[i-2].
Enter fullscreen mode Exit fullscreen mode

Now when you think about some algo to to Sum Up N fibonacci Numbers, what you can attempt is Find ALL Fibonacci up till N numbers, and now how to do this , as you saw the pattern here that i th fibonacci is sum of (i-1)th and (i-2) th Fibonacci,so let's throw some light on it You can begin with your F[0]=0 and F[1]=1 and Find All Fibonacci Up Till Nth Fibonacci, this is just some easy Dynammic Programming stuff where we have the results for the previous two fibonacci and we create our next out of it.
Here is a pesudu-code for it as well

int F[N];
F[0]=0;
F[1]=1;
for(int i=2;i<N;i++)
{
      F[i]=F[i-1]+F[i-2];
}
Enter fullscreen mode Exit fullscreen mode

And Once you have All Fibonacci up till Nth Fibonacci we will be planning to sum them up and this again is a simple while loop

int sum=0;
for(int i=0;i<N;i++)
{
      sum=sum+F[i];
}
return sum;
Enter fullscreen mode Exit fullscreen mode

Now think about Time Complexity We have two loops which are going up till N , So Asymptotically this completely Boils down to O(N).
Can We do it Better ?
Yes Now comes some beautiful Math along with it , Previously we were depending upon All the N terms to Sum Up N terms of Fibonacci , This time It ain't needed Let's derive a formulae for it.

As this is the recurrence for Fibonacci,
Alt Text
So it can be re written as this by some LHS RHS shifts.
Alt Text
Also this holds true,
Alt Text
, So Similarly we can write these equations going this way
Alt Text
Alt Text
Alt Text
ans so till N-> 0
Alt Text
If we add up all the equations we will get this result

Alt Text
Now I think YOu observe that what we are trying to demystify.
S[N] IS SUM OF N TERMS OF FIBONACCI
Alt Text
AND WE HAVE A CONCRETE EXPRESSION FOR IT NOW,
Alt Text

We No Longer Need N elements of Fibonacci to Sum N terms of Fibonacci , ALl we need now is N+2 th term of Fibonnaci to sum up till N.

How to Do it ? Optimally ?

Hint-> Use Some Linear Algebra to find any Fibonacci Term in O(LOG(N))

Top comments (1)

Collapse
 
abhijit2505 profile image
Abhijit Tripathy

Good one