fibonacci series what Iam is missing ?

[Steven D'Aprano]

On Tue, 24 Mar 2015 11:59 am, Chris Angelico wrote:


> I've never thought of the mathematical definition as being inherently
> recursive; but as inherently sequential. Sure, you can define counting
> numbers based on sets (0 is the cardinality of the empty set, 1 is the
> cardinality of the set containing the empty set, et-set-era), but most
> people will define them by counting. The Fibonacci sequence is
> logically defined by starting somewhere and then adding to the
> sequence. Yes, you can define it recursively too, but it's just as
> easy to define it as a progression.

But what are you adding? You're not adding a constant or simple expression
each time, but a previous term of the series. That's recursion. The
mathematical term is that it is a recurrence relation, and is usually
written:

F[n] = F[n-1] + F[n-2]

where F[x] means F subscript x. In English: the nth Fibonacci number is
equal to the sum of the previous two Fibonacci numbers (with the first and
second given by 0 and 1 respectively). That's inherently recursive: the
definition is given in terms of itself.

http://en.wikipedia.org/wiki/Fibonacci_number

There is at least one closed-form (non-recursive) formula for Fibonacci
numbers, Binet's Formula:

F[n] = (φ**n - ψ**n)/sqrt(5)

where:

  φ is the Golden Ratio (1+sqrt(5))/2

  ψ = 1-φ

but that's not how the Fibonacci numbers are defined, or why they are
interesting. The Fibonacci numbers are just a special case for a more
mathematically interesting family of recurrence relations, the Lucas
sequences.

(Aside: due to floating point rounding, Binet's Formula will give inaccurate
results for large enough values of n. With n=77 it is off by 1.)

The important thing here is that all these associated sequences -- Fibonacci
numbers, Pell numbers, Leonardo numbers, Perrin numbers and others -- are
defined as recurrences, i.e. recursively. But that doesn't necessarily make
recursion the best way to implement it.



-- 
Steven