Heard of the Fresh Fibonacci Soup?

No need Yesterday’s soup and day before yesterday’s soup to make Fibonacci Soup.

The Fibonacci numbers are the numbers in the following integer sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation,

Fn = Fn-1 + Fn-2

with seed values,

F0 = 0 and F1 = 1.

To get the nth Fibonacci number we need to find the (n-1)th and (n-2)th Fibonacci number.

Why we need to calculate the (n-1)th and (n-2)th Fibonacci number to find nth Fibonacci number ? is there anyway to find the nth Fibonacci number directly ?

Yes, you can find with the help of computational mathematics.

Solving linear homogeneous Recurrence relations with constant coefficient

The Fibonacci sequence satisfies part of the hypothesis of the distinct-roots theorem since the Fibonacci relation is a second-order linear homogeneous recurrence relation with constant coefficients

Characteristic equation,

have distinct roots? By the quadratic formula, the roots are,

It follows from the distinct-roots theorem that the Fibonacci sequence is given by the explicit formula

where C and D are the numbers whose values are determined by the fact that

F0 = 0 and F1 = 1

By using above seed values we can find C and D.

This explicit method is fast and inexpensive computationally To get the nth Fibonacci number without find the (n-1)th and (n-2)th Fibonacci number.