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].
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];
}
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;
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,
So it can be re written as this by some LHS RHS shifts.
Also this holds true,
, So Similarly we can write these equations going this way
ans so till N-> 0
If we add up all the equations we will get this result
Now I think YOu observe that what we are trying to demystify.
S[N] IS SUM OF N TERMS OF FIBONACCI
AND WE HAVE A CONCRETE EXPRESSION FOR IT NOW,
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)
Good one