6
$\begingroup$

I'm trying to code a simple algorithm that prints out the $n^{th}$ Fibonacci number. However, my program requires the initial seed values $F_0 = 0$ and $F_1 = 1$, when I'm hopeful I can figure something out to not require initial seed values.

Where does $F_0$ and $F_1$ come from anyway? Recursively, $F_n = F_{n-1} + F_{n-2}$, for all $n > 1$, but is there a mathematical approach to infer $F_0$ and $F_1$? Basically, how would I approach the values $F_0$ and $F_1$ without knowing them beforehand?

edit; I wanted to add since there seems to be confusion: I'm only concerned with the below sequence.

$$0, 1, 1, 2, 3, 5, 8, ...$$

I'm curious to how the $0, 1$ is defined, because every other term can be derived recursively, but the first two cannot (or can they?).

$\endgroup$
5
  • 2
    $\begingroup$ They're arbitrarily defined to be $0$ and $1$. Well, maybe not arbitrarily, it might lead to pleasing mathematical properties, but you certainly can't prove or deduce that they should be $0$ and $1$. You are of course free to imagine Fibonacci sequences with different starting values. $\endgroup$
    – Jack M
    Feb 17, 2014 at 1:16
  • $\begingroup$ They are the seeds, or initial values, for the recurrence relation. In a programmatic sense, they would be called base cases for the recurrence relation. $\endgroup$
    – Daryl
    Feb 17, 2014 at 1:17
  • $\begingroup$ The recurrence itself does not provide any information about the initial two values -- they are part of the definition of the sequence. Different pair of initial values would yield different sequence even when the recurrence itself was the same. $\endgroup$
    – Peter Košinár
    Feb 17, 2014 at 1:17
  • 1
    $\begingroup$ If you change the initial conditions and still call the sequence Fibonacci, you might get sued by Lucas. :) $\endgroup$
    – ir7
    Feb 17, 2014 at 1:23
  • 1
    $\begingroup$ I vote not to close this question. The other one is about picking the starting index of the fixed sequence (the one that contains $2$ and $3$ in it); this is about whether the initial terms can be picked arbitrarily. And indeed, the answers are different. (If closed, I vote to merge answers to the two questions.) $\endgroup$
    – ShreevatsaR
    Feb 17, 2014 at 4:42

5 Answers 5

Reset to default
7
$\begingroup$

The initial values $F_0 = 0$ and $F_1 = 1$ are part of the definition of the Fibonacci sequence. They can't be derived, because e.g. you could just as well pick any two numbers and apply the same recursion relation to get a different sequence. They're just the simplest numbers to start with, in a sense.

In general, any recursive definition which specifies a member of a sequence in terms of the previous $n$ members will require you to put in the first $n$ values by hand. They can be chosen arbitrarily and then you use the formula to produce further values. If you know that you want to produce a sequence with certain properties, then perhaps you can "derive" the $n$ seeds you need to come up with such a sequence (although there is not guaranteed to be any more efficient way to do so than guessing and checking), but without some constraint on the sequence you expect to end up with, nothing specifies the seeds.

$\endgroup$
6
$\begingroup$

One compelling reason for the standard definition of the fibonacci sequence is that it reveals their interesting divisibility properties, namely that they form a strong divisibility sequence, i.e.

$$\rm\ gcd(f_m,f_n)\ =\ f_{\:gcd(m,n)}$$

hence $\rm\ m\ |\ n\ \Rightarrow\ f_m\ |\ f_n\ $ etc. Analogous results hold for the more general class of Lucas-Lehmer sequences, which prove convenient when studying elementary number theory of quadratic fields, e.g. generalizations of Fermat's little theorem, Euler's $\phi$ totient function, etc. If one changed the indexing then many of these results would be greatly obfuscated.

That said, it should be emphasized that such definitions are merely conventions that prove useful in the context at hand. In other contexts - where such divisibility properties play no role - another indexing might prove more convenient.

$\endgroup$
1
  • $\begingroup$ On the last bit: the number of compositions of $n$ into $1$s and $2$s is $F_{n+1}$ under the usual indexing; this may be one context in which it makes sense to define the indices differently. Another is the number of binary strings with no consecutive $1$s, which is $F_{n+2}$. $\endgroup$
    – ShreevatsaR
    Feb 17, 2014 at 4:44
4
$\begingroup$

There is an entire family of Fibonacci-like sequences. A cool result by Wythoff is that for integral valued Fibonacci sequences, if you "center" them properly, you can use them to make a 1 to 1 correspondence with the rationals. However, the classic Fibonacci sequence is defined that way.

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

$\endgroup$
4
  • $\begingroup$ I think you mean a $1$ to $1$ correspondence with the positive integers, no? $\endgroup$
    – Jack M
    Feb 17, 2014 at 1:33
  • $\begingroup$ I meant rationals. If you look at Wythoff's array, you can literally just place it on top of the rationals if you write them with $\frac{0}{1}$ in the corner, forming rows of fractions with a fixed denominator and every integer above each denominator. The nth row has numbers of the form $\frac{k}{n}$. The hard part for being a 1 to 1 correspondence is making sure you don't include both $\frac{1}{2}$ and $\frac{2}{4}$. There is a 1 to 1 correspondence between the Fibonacci sequences and the positive integers as well. I believe also a result of Wythoff, and this may be what you thought I meant. $\endgroup$
    – mlg4080
    Feb 17, 2014 at 1:38
  • $\begingroup$ You can do that with any table, though, and if you just superimpose the two tables, you will count both $1/2$ and $2/4$. I think the more fundamental fact here is that the table contains every integer without any duplicates - the bijection with $\mathbb Q$ is just down to the fact that the table is countably infinite, as far as I can see. $\endgroup$
    – Jack M
    Feb 17, 2014 at 1:41
  • $\begingroup$ By writing your table for $\mathbb{Q}$ in a semi-clever way, aka only including the fraction $\frac{n}{k}$ if gcd$(n,k) = 1$ it makes this a 1 to 1 correspondence. Yes, it also creates a 1 to 1 correspondence with the positive integers, and each positive integer appears exactly once in Wythoff's array. However, the array-form it naturally appears in, suggests it as a nice bijection with the equivalent looking array for $\mathbb{Q}$. Yes, everyone already knows that the cardinality of $\mathbb{Z^+}$ equals the cardinality of $\mathbb{Q}$. This is just another neat, way to see that. $\endgroup$
    – mlg4080
    Feb 17, 2014 at 1:45
4
$\begingroup$

If you want to "derive" the initial conditions in some sense you could do so in the idealized biological sense of rabbit pair populations like "in the book Liber Abaci (1202) by Leonardo of Pisa, known as Fibonacci."

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

$\endgroup$
2
$\begingroup$

Technically it shouldn't matter which nonzero numbers you start with. The cool thing about Fibonacci number is the limit should go to the golden ratio.

Consider the definition of Golden Ratio - Smaller is to bigger piece, as bigger is to the whole.

As Fibonacci numbers get bigger and bigger, they get to this ratio. Intuitively speaking the original numbers matter less and less, and successive a, b, a+b patterns will go to:

a is to b, as b is to a+b.

Which gets closer and closer to the golden ratio.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .