- #51

Buzz Bloom

Gold Member

- 2,325

- 402

Hi QQ:Although I think that you can find it easily on the net, in any case, the explicit solution to the Fibonacci recurrence is Fn=1√5(1+√52)n−1√5(1−√52)nF_n = \frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2})^n - \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})^n known asBinet'sformula.

I get that the "solution" of the Fibonacci number recursive definition is the closed form formula that calculated the value of the nth number in the series. What I do not get is the relationship of this "solution" to algorithms and the time it takes to perform a calculation using an algorithm. hat I am guessing is there are more than one definition for what it means to solve a recursion expression. One meaning is the closed form that represents the nth term of the recursive sequence, and another meaning has something to do with algorithms and time to perform calculations. If I get the time, I will try to read the 30 page article you cited, and perhaps then I will understand this second meaning.

Regards,

Buzz