Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

DISCLAIMER: I do not deal with in-depth mathematics on a daily basis as some of you may, so please pardon my ignorance or lack of coherence on this topic.

QUESTION: What is the significance of starting the Fibonacci sequence with $0,1$ ?

For instance, if I picked any two random integers, say 2 and 7, to start a sequence would I actually be creating some multiple or derivation of the Fibonacci sequence?

Is there a general mathematical explanation for the relationship between any sequence represented by $a[0] = x, a[1] = y, a[n] = a[n-1] + a[n-2]$ and the Fibonacci sequence?

Or, back to my example sequence, is there a general mathematical relationship between:

$2,7,9,16,25,41,66,107,173,280...$

and

$0,1,1,2,3,5,8,13,21,34...$

Perhaps the Golden Ratio explains it somehow? Any help would be appreciated.

share|improve this question
    
I think it's just because 0 and 1 are the 2 lowest numbers that you can start from. –  Cruncher Oct 30 '13 at 20:16
1  
As in Brian Scott's answer, note that any sequence with that additive property is a "linear combination" of the Fibonacci numbers and the Lucas numbers. That is, if you make such a sequence and call it $\mbox{frogpelt}_n,$ then there will be constants $A,B$ such that $\mbox{frogpelt}_n = A F_n + B L_n.$ –  Will Jagy Oct 30 '13 at 20:29
2  
Fibonacci sequence. A series is an infinite sum. –  Jack M Oct 30 '13 at 23:00

3 Answers 3

up vote 11 down vote accepted

Yes, such sequences are closely related, and the relationship does involve the golden ratio.

Let $\varphi=\frac12(1+\sqrt5)$ and $\widehat\varphi=\frac12(1-\sqrt5)$; $\varphi$ is of course the golden ratio, and $\widehat\varphi$ is its negative reciprocal. Let $a_0$ and $a_1$ be arbitrary, and define a Fibonacci-like sequence by the recurrence $a_n=a_{n-1}+a_{n-2}$ for $n\ge 2$. Then there are constants $\alpha$ and $\beta$ such that

$$a_n=\alpha\varphi^n+\beta\widehat\varphi^n\tag{1}$$

for each $n\ge 0$. Indeed, you can find them by substituting $n=0$ and $n=1$ into $(1)$ and solving the system

$$\left\{\begin{align*} a_0&=\alpha+\beta\\ a_1&=\alpha\varphi+\beta\widehat\varphi \end{align*}\right.$$

for $\alpha$ and $\beta$. In the case of the Fibonacci numbers themselves, $\alpha=\frac1{\sqrt5}$ and $\beta=-\frac1{\sqrt5}$; in the case of the Lucas numbers $L_n$, for which the initial values are $L_0=2$ and $L_1=1$, $\alpha=\beta=1$.

share|improve this answer
    
Thank you very much, good sir! –  frogpelt Oct 30 '13 at 20:28
    
@frogpelt: You’re very welcome. –  Brian M. Scott Oct 30 '13 at 20:29

Let's call a sequence "fibonacci-like" if it satisfies the recurrence $$s_{n+2} = s_n + s_{n+1}$$ for all $n$. It's easy to see (or to show) that if $\{s_i\}$ and $\{t_i\}$ are two fibonacci-like sequences, then so is $\{s_i+t_i\}$, and so is $\{cs_i\}$ where $c$ is any constant. So the collection of fibonacci-like sequences forms a vector space. The dimension of the vector space is 2, since specifying two elements of the sequence (say $s_0$ and $s_1$) are enough to determine it completely.

So let's abbreviate such a sequence as $[s_0, s_1]$. The standard Fibonacci sequence $0,1,1,2,3,\ldots$ is written as $[0,1]$ in this notation. The Lucas sequence $\mathcal L_i = 1,3,4,7,11,\ldots$ is written $[1,3]$.

Since the space of all fibonacci-like sequences is a two-dimensional vector space, any two elements will form a basis for it, unless one is a multiple of the other. For example, a simple and standard basis for this vector space is the two vectors $[0,1]$ and $[1,0]$. The former is simply the standard Fibonacci sequence. The latter is the sequence $1,0,1,1,2,3,5,\ldots$, which is just the standard Fibonacci sequence shifted right by one position; its $i$th element is $f_{i-1}$, the $(i-1)$th Fibonacci number.

Now consider the general fibonacci-like sequence $[p,q]$:

$$[p,q] = p[1,0] + q[0,1]$$

So the $i$th element of the sequence $[p,q]$ is exactly $$pf_{i-1} + qf_i.$$ For example, the Lucas sequence has $$\mathcal L_i = f_{i-1} + 3f_i.$$ Simiarly your example sequence is $[2,7]$ and is therefore related to the Fibonacci sequence by $$[2,7] = 2[1,0] + 7[0,1] = 2f_{i-1} + 7f_i.$$

Any two sequences form a basis of the space as long as they are not multiples of one another. For example, any fibonacci-like sequence can be expressed in the form $s_i = af_i + b\mathcal L_i$ for some constants $a$ and $b$. For your $[2,7]$ sequence, we want $[2,7] = a[0,1] + b[1,3] = [b,a+3b]$. So $b=2$ and $a=1$, and we get $[2,7] = f_i + 2\mathcal L_i$.

Now consider the Fibonacci sequence, but shifted left by $k$ places, whose $i$th element is $f_{i+k}$ for each $i$. Then the first two terms of the fibonacci-like sequence $\{f_{i+k}\}$ are $f_k$ and $f_{k+1}$, we get $$\{f_{i+k}\} = [f_k, f_{k+1}] = f_k[1,0] + f_{k+1}[0,1] = f_kf_{i-1} + f_{k+1}f_i$$ and we have just proved the sum-of-indices formula for fibonacci numbers. Take $i=k$ in this and we get $$f_{2k} = f_kf_{k-1} + f_{k+1}f_k $$ which is useful for calculating extremely large Fibonacci numbers quickly.

share|improve this answer

For any sequence $a_0, a_1, a_2, a_3, \dots$ that satisfies the Fibonacci recurrence, we have $$a_n=(a_1-a_0)f_n+a_0f_{n+1},$$ where $f_0,f_1, f_2, \dots$ is the Fibonacci sequence.

To prove this, let $b_n=(a_1-a_0) f_n+a_0f_{n+1}$. Note that $b_0=a_0$ and $b_1=a_1$. The two sequences $(a_n)$ and $(b_n)$ "begin" in the same way, and satisfy the same recurrence, so they are the same.

share|improve this answer
    
I think this is slightly off. If $n=1$, you get $b_1=a_1+a_0$. –  Mike Oct 30 '13 at 21:18
    
@Mike: Thanks, cleaned up. –  André Nicolas Oct 30 '13 at 21:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.