Does the order of the Fibonacci sequence's initial values matter?

Question

I am reading about generating functions in this reputable engineering textbook and the author uses the Fibonacci sequence as an example:

The Fibonacci sequence is defined by the initial conditions $a_0=0$, $a_{-1}=1$, and the recursion relation $a_n=a_{n-1}+a_{n-2}$ for $n>0$.

Using this definition, I am able to work through the author's example to get the correct generating function: $$G(x)=\frac{1}{1-x-x^2}$$

However, everywhere I read online states the initial conditions of the Fibonacci sequence as (0,1) and not (1,0). So I tried that instead, but I get a different result:

$$G(x)=\frac{1+x}{1-x-x^2}$$

This generating function seems to produce the Fibonacci sequence, but starting from the second number instead of the first $(1,2,3,5,8,13,...)$. Where did I go wrong? I would have thought that the sequence should be identical in both cases.

Many thanks for any help!

My calculations:

The author starts with a general expression for a generating function for a sequence $\{a_n\}$: $$G(x)=\sum_{n=0}^{\infty}a_nx^n$$

He then looks at the special case where $\{a_n\}$ is a linear recurrence of range $r$: $$a_n=\sum_{i=1}^rc_ia_{n-i}$$

and proves that this leads to: $$G(x)=\frac{g(x)}{f(x)}=\frac{\sum_{i=1}^rc_ix^i\left(a_{-i}x^{-i}+\cdots+a_{-1}x^{-1}\right)}{1-\sum_{i=1}^rc_ix^i}$$

So, for the Fibonacci sequence, I guess we have $r=2$ and $c_1=c_2=1$. So we get:

$$g(x)=a_{-1}+a_{-2}+a_{-1}x$$

Now I'm a bit confused because the subscripts don't seem to match up. In all the author's discussion, the "initial conditions" have strictly negative subscripts ($a_{-i}$ for $i=1,2,\dots,r$). But just for the Fibonacci example, we have initial conditions $a_0=0$ and $a_{-1}=1$. So I assume these are just off by 1. Therefore, substituting $a_{-1}=0$ and $a_{-2}=1$ gives the author's result above and using $a_{-2}=0$ and $a_{-1}=1$ gives my result above.

Answer 1

In the particular case of the Fibonacci number sequence OEIS A000045 (or series) there is some difference of opinion as amply evidenced by the Wikipedia article and OEIS entry. The most common convention is that $\,F_0=0\,$ and $\,F_1=1\,$ and this choice has much in its favor. This choice implies that its generating function is $$ \sum_{n=0}^\infty F_n\,x^n = \frac{x}{1-x-x^2}. $$ Notice the $\,x\,$ in the numerator. For this and a few other reasons, some prefer the choice $\,F_0=F_1=1\,$ instead, which implies that the generating function is now $$ \sum_{n=0}^\infty F_n\,x^n = \frac{1}{1-x-x^2}. $$ Both choices are valid and useful in some cases and not as useful in other cases. Thus, it is a good idea to be clear on which choice is being used in any given context since the choice will usually matter.

The situation with negative index Fibonacci sequence elements is that the recurrence relation for the sequence can be used to uniquely extend the sequence in the negative index direction. For the common convention this implies that $$ F_{-n} = (-1)^{n-1}F_n \quad\text{ for all integer }n. $$ The result for the other convention it is that $$ F_{-n} = (-1)^n F_{n-2} \quad\text{ for all integer }n. $$

What if we choose arbitrary starting values with the same recurrence relation? That is, if we choose $\,F_0=a\,$ and $\,F_1=b,\,$ what do we get? The recurrence relation is linear and this implies that the sequence of numbers we get is a linear combination of the two initial value choice sequences. The generating function now is $$ (a) \!+\! (b)x \!+\! (a+b)x^2 \!+\! (a+2b)x^3 \!+\! \cdots \!=\! \frac{a\!+\!(b\!-\!a)x}{1-x-x^2}. $$

Note that initial values of Fibonacci and related sequences can be given for any two consecutive index values--not just for $\,a_0\,$ and $\,a_1\,$ since the recursion going forward and backward can reach any other integer index value. Again, this is just a matter of convenience and convention. In the case you cite, specifying $\,a_{-1}\,$ and $\,a_0\,$ is fine. The initial values $\,a_{-1}=1,\,a_0=0\,$ gives the same sequence as $\,a_0=0,\,a_1=1.$ This special case may be misleading though. The initial values $\,a_{-1}=u,\,a_0=v\,$ gives the same sequence as $\,a_0=v,\,a_1=u+v\,$ and $\,u+v\,$ is equal to $\,u\,$ if and only if $\,v=0.$

---

Note that the Wikipedia article Generalizations of Fibonacci numbers mentions some of the issues such as extension to negative integers. It mentions a vector space of number sequences:

Since the set of sequences satisfying the relation $\,S(n)=S(n-1)+S(n-2)\,$ is closed under termwise addition and under termwise multiplication by a constant, it can be viewed as a vector space. Any such sequence is uniquely determined by a choice of two elements, so the vector space is two-dimensional. If we abbreviate such a sequence as $\,(S(0),S(1)),\,$ the Fibonacci sequence $\,F(n)=(0,1)\,$ and the shifted Fibonacci sequence $\,F(n-1)=(1,0)\,$ are seen to form a canonical basis for this space, yielding the identity: $$ S(n)=S(0)F(n-1)+S(1)F(n) $$ for all such sequences $\,S$.

Answer 2

The recursion $a_n=a_{n-1}+a_{n-2}$ is "encoded" in the denominator of the generating function: $1-x-x^2$. The numerator is determined by the values of $a_0$ and $a_1$. In particular, $$ \overbrace{\left(1-x-x^2\right)\vphantom{\sum^\infty}}^\text{denominator}\overbrace{\sum_{n=0}^\infty a_kx^k}^{\substack{\text{generating}\\\text{function}}}=\overbrace{a_0+(a_1-a_0)\,x\vphantom{\sum^\infty}}^\text{numerator}+\sum_{n=2}^\infty\overbrace{(a_n-a_{n-1}-a_{n-2})\vphantom{\sum^\infty}}^0\,x^n $$ Thus, the generating function is $$ \frac{a_0+(a_1-a_0)x}{1-x-x^2} $$

---

I prefer the definition of the Fibonacci Numbers that starts with $F_0=0$ and $F_1=1$, whose generating function is $$ \frac{x}{1-x-x^2} $$ because, among other things, we have $$ n\mid m\implies F_n\mid F_m $$ Furthermore, $$ F_{-n}=(-1)^{n-1}F_n $$ Lucas Numbers also obey the same recursion as Fibonacci Numbers, and their generating function is $$ \frac{2-x}{1-x-x^2} $$

Answer 3

There is already a nice description of generating functions in Somos answer. I will focus here on the question you had about the author's general formula.

$$G(x)=\frac{g(x)}{f(x)}=\frac{\sum_{i=1}^rc_ix^i\left(a_{-i}x^{-i}+\cdots+a_{-1}x^{-1}\right)}{1-\sum_{i=1}^rc_ix^i}$$

You are right in saying, 'for the Fibonacci sequence, I guess we have $r=2$ and $c_1=c_2=1$.' You are also correct in observing that you weren't given $a_{-2}$ and the formula requires it.

Also, technically, since the recursion given in the exercise only holds for $n > 0$, $a_{-2}$ is indeterminate in the exercise. So this is 'bad' notation on the author's part if you are expected to use this general theorem, in my opinion.

So, to alleviate this I propose you consider an extension to the recursion, where the recursion holds for $n\geq 0$, (as it must whenever the theorem you have stated and it's associated formula should apply). In such a case, although you aren't given $a_{-2}$ you can find its value from the recursion itself since:

$$a_{0} = a_{-1} + a_{-2}$$

So $a_{-2} = a_{0} - a_{-1} = -1$. Plugging it all in:

$$ G(x) = \frac{x(x^{-1}) + x^{2}(-x^{-2}+ x^{-1})}{1-x-x^{2}} = \frac{x}{1-x-x^{2}} $$

So, it yields the expected generating function for the case where $a_{0}=0$ and $a_{1} = 1$.

So, I understand the confusion you had. However to answer the question as to what happened, when you shift the indices for the initial condition, it will result in shifting the indices throughout the sequence which emerges from the recursion and this will change the generating function.

Answer 4

Although one does not always make this explicit, giving a sequence of numbers really amounts to giving a set of (index,value) pairs; for instance an infinite sequence of real numbers is really a function $\Bbb N\to\Bbb R$, whose graph is an infinite set of such pairs. The generating series for a set $S$ of such pairs $(i,a_i)$ is $\sum_{(i,a_i)\in S}a_iX^i$, so for a series of numbers corresponding to $f:\Bbb N\to\Bbb R$ this is $\sum_{i=0}^\infty f(i)X^i$.

Let me first put aside the easy answer to the question in your title: of course order of initial terms matters, and permuting them in general gives an entirely different sequence. But that is not what your question was really about, which seems to be more about whether a shift in indexing produces a different generating series. Here too the answer is yes: a pure shift in indexing amounts for the generating series in multiplication by a power of $X$. If the shift is accompanied by addition or removal of nonzero values in the sequence, then this amounts to addition of terms to the generating series.

Note that normally a generating series is a formal power series in $X$, with no negative powers of $X$ at all. In this sense there is no generating series at all for a sequence with a nonzero value at some negative index, as your book apparently wants to do by starting at $a_{-1}=1$. If you insist on including that, the generating series would have a term $X^{-1}$, and thereby become a Laurent series rather than a formal power series. But usually those who entertain the idea of Fibonacci numbers at negative indices want them for all negative integer indices, but for such bi-infinite sequences the idea of generating series simply does not work: there is no appropriate algebraic framework. Think of it: if there were such a thing as $S=\sum_{i\in\Bbb Z}a_iX^i$ for a sequence $(a_i)_{i\in\Bbb Z}$ satisfying $a_{i+2}=a_i+a_{i+1}$ everywhere, then one would want to express this by saying $S(1-X-X^2)=0$, but $S=0/(1-X-X^2)$ in no way describes a generating series for the Fibonacci numbers (for one thing that expression gives no information about any "initial terms" that were used, for another it just simplifies to $0$ in any reasonable algebraic setting).