Fibonacci series recursion error

[Steven D'Aprano]

On Mon, 02 May 2011 10:53:52 +0100, Hans Georg Schaathun wrote:

> On 02 May 2011 08:56:57 GMT, Steven D'Aprano
>   <steve+comp.lang.python at pearwood.info> wrote:
> :  I see your smiley, but there are a number of similar series as
> Fibonacci, :  with the same recurrence but different starting values, or
> similar but :  slightly different recurrences. E.g. Lucas, primefree,
> Pell, Padovan and :  Perrin numbers.
> 
> Well, Fibonacci isn't one unique sequence.  Any sequence satisfying f(n)
> = f(n-1) + f(n-2) is /a/ Fibonacci sequence.  Regardless of starting
> values.  At least according to some authors.

According to the references I have, there is one and only one Fibonacci 
sequence, the usual one invented by Fibonacci to talk about rabbits. 
(Actually, we should talk about Fibonacci *numbers*, rather than 
sequence.)

Wolfram Mathworld is typical, defining *the* Fibonacci numbers as those 
with starting conditions f(1)=1, f(2)=1 (or f(0)=0 if you prefer).

http://mathworld.wolfram.com/FibonacciNumber.html

The Collins Dictionary of Mathematics agrees with Mathworld.

The Lucas numbers (related to, but not the same as, the Lucas sequence) 
obey the same recurrence as the Fibonacci numbers, but with a different 
set of starting values. So there is certainly precedent in the 
mathematical literature for giving different names to the same recurrence 
with different starting values.

In any case, whatever you call them, what I call R(n) is not one, as the 
recurrence is different:

R(n) = R(n-1) + R(n-2) + 1


> Penguin, Dict. of Mathematics prefer 1,1,2,3,5 but they also suggest
> 0,1,1,2,3, ...

This depends on whether you start counting from n=0 or n=1.

Even the sequence you quote, from Anderson: 

1,2,3,5...

is just the usual Fibonacci numbers starting at n=2 instead of 1 or 0. 
(No matter how confusing something is, there's always at least one person 
who will try to make it *more* confusing.)


> In short, don't assume that a person talking about Fibonacci numbers
> assume the same base cases as you do.

As far as I'm concerned, there are only two definitions of Fibonacci 
numbers that have widespread agreement in the mathematical community:

0,1,1,2,3 ... (starting from n=0)
1,1,2,3,5 ... (starting from n=1)

Any other definition is rather, shall we say, idiosyncratic.



-- 
Steven