I'm doing a task in a subject were fib 0 is defined to = 1. But that can't be right? Fib 0 is 0?
Program with fib 0 = 1; spits out fib 4 = 5 Program with fib 0 = 0; spits out fib 3 = 3
What is correct?
+4
A:
Based on the definition of the Fibonacci sequence, you can generate a closed form for defining the nth element:
F(n) = ( f^n - (1-f)^n ) / sqrt(5),
where f = (1 + sqrt(5)) / 2 [the golden ratio]
For n = 0 it is clearly 0:
F(0) = (1 - 1) / sqrt(5) = 0.
Zed
2009-09-20 14:40:33
That's an explanation, albeit a roundabout one. It's really the seed that defines it in the first place.
Noldorin
2009-09-20 15:01:35
True, this is inside-out...
Zed
2009-09-20 15:09:44
Anyway, there's certainly no debate on the closed form, so this gives an unquestionable answer to the question =)
Zed
2009-09-20 15:12:16
@Noldorin Of course you could define the seed differently, but then a lot of nice theorems would become false, like this one. BTW, my favorite is gcd(F_m, F_n) = F_gcd(m,n).
starblue
2009-09-20 16:05:38
+5
A:
You're correct. The Fibonacci sequence is defined with seed values F_0 = 0 and F_1 = 1. This is a requirement for the rest of the sequence to be correct.
The only condition under which F_0 = 1 could work is if you defined a "-1 based counting system" (as opposed to the usual conventions of 0-based and 1-based). This would be pretty wacky however, I'm sure you agree.
Noldorin
2009-09-20 14:41:21
With a nice little emphasis on: "Some sources omit the initial 0, instead beginning the sequence with two 1s"
NomeN
2009-09-20 15:41:12
A:
They are both correct. If you specify a sequence G{n} by the recursion G{1} = 3, G{2} = 5, G{n} = G{ n - 1} + G{ n - 2} then most people would agree that is "a Fibonacci sequence". The only difference being a few terms at the front, but the leading terms are mostly irrelevant for any interesting questions about the sequence. The heart of a Fibonacci sequence is the addition rule, and any sequence that uses that rule is a Fibonacci sequence. It is only necessary to specify whether 0 is in the sequence if you want to ask specific questions about a particular index... every thing else is just a translation on the index and is pretty much irrelevant. That is, if the problem is 'find a closed form solution for the Nth value in the sequence', then solving it for G will solve the problem for F with just a trivial shift of the solution. The hard part of the problem is the same for both sequences.
William Pursell
2009-09-20 17:01:03