# Significance of starting the Fibonacci sequence with 0, 1…

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.

-
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
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
Fibonacci sequence. A series is an infinite sum. – Jack M Oct 30 '13 at 23:00

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$.

-
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.

-

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.

-
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