Preamble:
This post is about an alternative way of formulating Fibonacci series especially useful for summing even valued terms. The next paragraphs in this preamble may be of little importance for majority of you and thus might want to skip and jump to next section directly...
September 2016 has not been that great to me and my beloved city Bangalore (the city i live and love to live with)and in general to the state i belong to. More so the last weekend of this month to me greeted me to an unusually chilly Saturday morning. Unusual; because i dont remember in the last few years about onset of cold this early and i have been saying this to myself for 100th time since the start of September. The continuous indifference of people towards lake and ecological conservation has seemed to rage enough the mother nature for she seemed to unleash the fury by sending in an untimely cold onset and further determined to demonstrate that weatherman was plain wrong this time about his forecast on due rains. Then as if; to add salt on the wound; the jury's verdict on the long standing river water sharing row with our neighboring state caused flare-up upsetting the already parched civilians of our state. I feel sad to be in the situation where the basic needs of drinking water had to be requested by one and all for securing the same. Naturally the city simmered and as i could see the worry writ large on everyone's face; reading just one common feeling that Did we just loose our rights to basic needs?
Well this was happening from since 2 weeks; the cab ride back home from office on that Friday(previous day); was filled up with all kinds of discussions mainly around the current water issues faced by public at large.Stranger are the ways the mind works; i was feeling; when all of a sudden a momentary flash swept my mind frame with a curious problem on summing even-valued fibonacci terms . This was a problem that some one described to me over a call during lunch that day. But then I wasnt sure to pursue thinking on that while the entire mass in the cab was gravitating towards the center of the raging debate on water dispute. Though my head showed little curiosity at the fibonacci problem for a short-while; my heart came pounding to push me into the center of gravity of the issues that cab was engrossed with. So after a while; finally; head gave in to the heart and thus junked this fibonacci problem into my memory backyard throughout the journey and infact for a good part of the ensuing night.
The general mood was further weather-beaten with early onset of chill in and had me coiling up lazily, cozily wrapped within softrug that iam used to through the friday night till the weehours of saturday . While the sub-concious kept on nagging about the discussions related to the treatment meted out to us through wee-hours; i was desparately looking for my daily booting sequence to arrive (its how one of my colleague nicely sums it). Of-course; You wont second guess this! with a native Bangalorean!. Would You?!!. It better be the coffee made from decanted decauction created straight out of freshly ground coffee beans (more specifically to me; coffee beans from chikamagalur).
Lo!, Just then some events unfolded at home when i had to force myself up from bed to attend to some immediate houshold chore. (Its plain simple; my kids had'nt yet moved the cleaned up utensils from backyard to kitchen and my wife was getting late for school ; this further delayed the food preparation etc... the rest you can fill up the blanks). As primary fail-over entity in these situations i was forced to get it done while kids and thier mother are to leave for school without the brunch. Coupled with the absence of coffee and the fireworks just witnessed, i am standing in the backyard; that cold morning; staring half asleep at a pile of utensils!. Oh Boy! It didnt help at all!!. My cranium ached and longed for something different to tide over this and there it was!. Instead of inspring to get to tkitchen to make myself the cofee, it actually bounced back; of all the things from its backyard; the problem on how to sum up even valued terms of fibonacci series. What a timing! and situation!.
Fired up a bit over on that i tried mentally imagining the terms of the series hoping to make my coffee less situation a bit better. No sooner the terms started enumerating i started delving into realms of the series by asking myself: what could be so special about fibonacci? Ofcourse we all know that every term is sum of last two terms. A plain for-loop with all even value detected and have blind sum of the same. So, what is special about even values to be asked in an interview? why did they not ask odd numbers??.So quickly finishing the agreed chore came back to my laptop and started tapping out first ten fibonacci terms to gaze at it for some time on why some one is interested in even valued terms!.
Sorry to bother with my preamble..and without much ado will jump for the crux.
Fibonacci series generation
The Fibonacci series as we all know; is constructed with every term made from summation of its previous 2 terms in the series(thats obvious stated again isnt it). So typically we could express it as follows:
Given :
- N as the whole number space
- Z as the integer space
- Z+ and Z- as the positive and negative integer space.
- i as the index of the term in the series
- F(i) as the ith fibonacci term
For all i in N (N is whole number space)
F(i) = i where i in [0,1]
F(i) = F(i-2) + F(i-1) where i in [2, INF)
If we tabulate for first 10 numbers the table looks as follows:
| i | F(i) | Std form |
|---|---|---|
| 0 | 0 | Assumed base value |
| 1 | 1 | Assumed base value |
| 2 | 1 | F(0)+F(1) |
| 3 | 2 | F(1)+F(2) |
| 4 | 3 | F(2)+F(3) |
| 5 | 5 | F(3)+F(4) |
| 6 | 8 | F(4)+F(5) |
| 7 | 13 | F(5)+F(6) |
| 8 | 21 | F(6)+F(7) |
| 9 | 34 | F(7)+F(8) |
| 10 | 55 | F(8)+F(9) |
Now, let us extrapolate the series a bit into the negative indexes.
As we know any ith term can be expressed as the sum of two preceding terms i.e F(i) = F(i-2)+F(i-1) and hence by inference we could also say in the series contiuuum; that an ith term F(i) is also the difference of two succeeding terms i.e F(i) = F(i+2) - F(i+1).
Therefore if the above table can be rewritten with this other form as well;the values in the negative scale (i.e negative indexes) presents us an interesting sign-alternating form of the positive term series as shown below.
| i | F(i) | Std form | My form |
|---|---|---|---|
| -4 | -5 | F(-6)+F(-5) | F(-2)-F(-3) |
| -3 | +2 | F(-5)+F(-4) | F(-1)-F(-2) |
| -2 | -1 | F(-4)+F(-3) | F(0)-F(-1) |
| -1 | +1 | F(-3)+F(-2) | F(1)-F(0) |
| 0 | 0 | F(-2)+F(-1) | F(2)-F(1) |
| 1 | 1 | F(-1)+F(0) | F(3)-F(2) |
| 2 | 1 | F(0)+F(1) | F(4)-F(3) |
| 3 | 2 | F(1)+F(2) | F(5)-F(4) |
| 4 | 3 | F(1)+F(2) | F(6)-F(5) |
| 5 | 5 | F(2)+F(3) | F(7)-F(6) |
| 6 | 8 | F(3)+F(4) | F(8)-F(7) |
| 7 | 13 | F(4)+F(5) | F(9)-F(8) |
| 8 | 21 | F(5)+F(6) | F(10)-F(9) |
| 9 | 34 | F(6)+F(7) | F(11)-F(10) |
| 10 | 55 | F(7)+F(8) | F(12)-F(11) |
A casual inspection of this series presents that the even valued term and odd valued terms are not haphazard and every even valued term is surrounded by an odd term on both its sides. Though not particularly fascinating to a mathematically trained eye; this fundamental nature in this particular series lends a fresh/different perspective to an ordinary programmer like me
Continuing back on our trail of deductions; you can say that
Given i belong to {Z}, the ordinate F(i) in this coordinate plane can be defined now as:
F(i-2) + F(i-1) = F(i) = F(i+2) - F(i+1). --------------- (1)
F(-i) = (-1)i+1 F(i) for all i belong to {Z+} --------------- (2)
Now for the interesting observation; Consider the even term alone.
If you observe carefully; the even valued term repeats every 3rd term and curiously enough each such even valued term bears a enigmatic relation with two previous even valued terms. So for instance, the 9th term has an interesting relation with 6th and 3rd terms. Let us explore this a bit
For eg:
F(12) =144 = 4 * 34 + 8 = 4 * F(9) + F(6)
F(9) = 34 = 4 * 8 + 2 = 4 * F(6) + F(3)
F(6) = 8 = 4 * 2 + 0 = 4 * F(3) + F(0).
Hmm....
Try further down when indexes become -ve. So for eg:
F(3) = 2 = 4 * 0 + 2 = 4 * F(0) + F(-3) = 4 * F(0) + F(3) [ By rule (2) F(-3) = (-1)3+1F(3)]
F(0) = 0 = 4 * 2 +(- 8) = 4 * F(-3) + F(-6) = 4 * F(3) - F(6) [ By rule (2) F(-6) = (-1)6+1F(6)]
F(-3) = 2 = 4 * (-8) +(34)=4 * F(-6) + F(-9) = 4 * -F(6) + F(9) [ By rule (2) F(-9) = (-1)9+1F(9)]
F(-6) = -8 = 4 * F(-9) + F(-12) = 4 * F(9) - F(12) = 4 * 34 - 144 [ By rule (2) F(-12) = (-1)12+1F(12)]
This was the first glimmer of smile on that day that something i had not noticed for a long was staring at me!! smilingly
What further interested me is this very same beautiful relation exists with odd valued terms as well!!
So
F(7) = 13 = 4 * 3 + 1 = 4 * F(4) + F(1).
F(8) = 21 = 4 * 5 + 1 = 4 * F(5) + F(2).
F(10) = 55 = 4 * 13 + 3= 4 * F(7) + F(4).
Again with negative indexes;
F(5) = 5 = 4 * 1 + 1 = 4 * F(2) + F(-1)
F(2) = 1 = 4 * 1 + (-3)= 4 *F(-1) + F(-4) = 4 *F(1) - F(4)
So I figure that regardless of whether a term's value is even or odd the Fibonacci series exhibits a relationship such that every ith term can also now be formulated from the (i-3)rd and (i-6)th terms in the following manner as explained and defined below in the proof:
Mathematical proof
OK..just thought to satiate the mathematical rigor by proof in addition to getting satisfied with spreadsheet way of proving..
F(i-1) = F(i-3) + F(i-2) ----------------(3) by simple application of (1)
F(i-2) = F(i-4) + F(i-3) ----------------(4) by simple application of (1)
F(i+2) = F(i-2) + F(i-1) + F(i+1) ---- (5) by re-arranging terms in (1)
F(i) = F(i-4) + F(i-3) + [F(i-1)] ----(6) by inference using (5) for F(i)
F(i-1) = F(i-5) + F(i-4) + F(i-2) ------(7) by inference using (5) for F(i-1)
F(i-2) = F(i-6) + F(i-5) + F(i-3) ------(8) by inference using (5) for F(i-2)
F(i) = F(i-4) + F(i-3) + [F(i-3) + F(i-2)] ------ (9) substituting F(i-1) by (3)
So
F(i) = F(i-4) + 2 * F(i-3) + [F(i-2)]
F(i) = F(i-4) + 2 * F(i-3) + [F(i-6) + F(i-5) + F(i-3)] ---(10) by substituting F(i-2) with (8)
F(i) = 3 * F(i-3) + F(i-6) + [F(i-5) + F(i-4)]
Again since [F(i-5) + F(i-4)] = F(i-3) by simple application of (1)
therefore
F(i) = 3 * F(i-3) + F(i-6) + [F(i-3)]
F(i) = 4*F(i-3) + F(i-6)
Solution to the even-term summation
Now it dawns on the importance of why folks were interested in the even valued terms.
A simple loop that jumps at interval of 3 can reduce the looping by 2/3rd the original number of iterations. Meaning; with first 2 seed even valued terms which is 0 and 2; i can now generate a continuos set of even valued terms directly by applying the formula FEven(i) = 4*FEven(i-1) + FEven(i-2).
Ofcourse please be advised the code below is a simple indicative pseudo code to only highlite the fact that a different formulation exists to generate every 3rd term of the series and thus can reduce potentially on the complexity of computation.
int fibonacciConstantValues[] = {0, 2};
private int fibonacciEven(int i){
if(i less than 2) return fibonacciConstantValues[i];
else return 4 * fibonacciEven(i-1) + fibonacciEven(i-2)
}
/** Sum to N even valued terms. **/
int sum=0;
for (int i=0; i less than N; i++) { sum += fibonacciEven(i); }
Or even if you just need to build a complete fibonacci series then however this may not have edge on computational speed over the traditional form but is mentioned for the sake of completeness:
int fibonacciConstantValues[] = {0, 1, 1, 2, 3, 5};
private int fibonacci(int i){
if(i less than 6) return fibonacciConstantValues[i];
else return 4 * fibonacci(i-3) + fibonacci(i-6);
}
Summary
In summary an interesting insight opened up within myself about this great series and that insight ;i had not heard anywhere (in my college or elsewhere). This information could be possibly lying in a mathematical journals ; however i feel it could have been atleast worthy enough a mention in some programming texts. Anyways its not always I would get up to a cold morning in september witnessing my better half yelling at kids but indirectly making me do an uninteresting house chore and then most of all thinking of a different avatar of Fibonacci series. I sign off saying that it was well worth of a weekend enough to carry it as a nostalgia into my future. Thanks for reading through my thoughts this far
