14
$\begingroup$

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.

$\endgroup$
6
  • 18
    $\begingroup$ Using negative subscripts in an introduction to generating functions is just confusing and evil. $\endgroup$
    – orlp
    Feb 21, 2021 at 15:30
  • 6
    $\begingroup$ Everyone define it as starting $F_0=0$ and $F_1=1$ with $F_{n+2}=F_{n+1}+F_n$ for all $n\in\mathbb{Z}$, so this has the effect of making $F_{-1}=1$ too. There is no difference in your textbook's Fibonacci sequence and the rest of the world's. But definitely using negative subscripts in an introduction is evil. $\endgroup$ Feb 21, 2021 at 15:47
  • 2
    $\begingroup$ @user10354138 I think that's it. If we work backwards into negative Fibonacci numbers, we get: $…,−8,5,−3,2,−1,1,0,1,1,2,3,5,8,…$. If we start with initial condition (1,0), then the sequence proceeds with $1,1,2,3...$ and if we start with (0,1), then the sequence proceeds with $1,2,3,5,...$. If I understand correctly, the usual convention (0,1) counts one of the initial values as the first value in the sequence. But in this textbook, the sequence starts after the initial values. $\endgroup$
    – Harry
    Feb 21, 2021 at 16:08
  • 3
    $\begingroup$ The modern index convention makes the Binet formula simplest (not to mention a whole slew of other formulae). A simple way of remembering this convention is that $F_5=5$ and $F_{12}=12^2$. $\endgroup$
    – PM 2Ring
    Feb 21, 2021 at 22:52
  • 1
    $\begingroup$ @orlp confusing and evil tinkering like that often is based on some less noticed property. In this case it surely provides some additional insight for those willing to dig :) $\endgroup$
    – Džuris
    Feb 22, 2021 at 7:30

4 Answers 4

15
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ I had noticed the version with the $x$ in the numerator while googling. I think I see now what the difference is. When you say both choices are valid, is it not the case that many other choices (perhaps infinitely many) would also be valid (albeit probably less convenient)? For example, if I say $F_0=5$ and $F_1=8$ then I get $g(x)=13+8x$ and we just start from a different place. (Although unless I knew I was looking for the Fibonacci numbers, I'm not sure how I would justify choosing 5 and 8). $\endgroup$
    – Harry
    Feb 21, 2021 at 19:33
  • $\begingroup$ @Harry According to mathworld, $F_1=F_2=1$ is a convention. The formulas both in mathworld and wikipedia have to be modified unnecessarily (although it is just a shift) , if we use the other assignment. I see no reason to do that , even if some combinatorical formula might become more "elegant" with the other assignment. $\endgroup$
    – Peter
    Feb 21, 2021 at 20:10
  • $\begingroup$ @Peter That's interesting. According to wikipedia, the other convention was used in "some older books". I'm not sure what qualifies as old, but this book was written in 1967, which makes it rather ancient in an electronic engineering context. I'm not sure if I understand the whole debate. If you told me the first two values were $F_{77}=21$ and $F_{78}=34$, then I could probably live with that. So I'll just make sure I update my own notes to follow the accepted convention. $\endgroup$
    – Harry
    Feb 21, 2021 at 20:40
  • $\begingroup$ "Both choices are valid and useful in some cases and not as useful in other cases." I disagree, and believe that $F_0=0$ is the natural choice. (One huge reason: this choice enables the implication "if $m$ divides $n$ then $F_m$ divides $F_n$".) But I invite an alternate view: can you describe a situation in which $F_1=1$ is more convenient? $\endgroup$ Feb 22, 2021 at 7:44
  • 2
    $\begingroup$ @GregMartin One example where $F_0=F_1=1$ is "nicer" is the combinatorial definition of $F_n$ as the number of ways to tile a $1\times n$ rectangle using squares and dominos. $\endgroup$
    – Carmeister
    Feb 22, 2021 at 15:23
6
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ I would consider the divisibility property a canonical property of the Fibonacci numbers and one of the most important reasons for the particular definition. $\endgroup$ Feb 21, 2021 at 23:44
  • $\begingroup$ That $\implies$ is even an $\iff$; even better, $\gcd(F_n, F_m) = F_{\gcd(n, m)}$! $\endgroup$ Feb 22, 2021 at 18:05
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ @openproblem I don't understand what you want to say, or how it relates to my answer. Yes sequence satisfying a same linear recurrence form a vector space. No, there is no such thing as a "trivial" solution (except if you mean the zero solution, which I think you do not); every solution to a degree $d$ recurrence needs $d$ values to be completely determined. No, multiplying with the polynomial you call "annihilator" does not lose information, since $K[[X]]$ is an integral domain. But my point is: neither $K[[X]]$ nor $K((X))$ nor other nice rings properly represent bi-infinite sequences. $\endgroup$ Mar 1, 2021 at 13:08
  • $\begingroup$ @openproblem I think you missed my main point. A formal Laurent series in $K((X))$ may have some negative powers of $X$, but only finitely many. This property is essential for being able to define a multiplication: without it coefficients of a product would be given by infinite sums that may fail to converge. This multiplication makes $K((X))$ into an integral domain (even a field), so multiplying by $(1-X-X^2)$ does not annihilate any nonzero formal Laurent series. So an expression like $X^{-4}/(1-X-X^2)$ describes a FLS and a Fibonacci-like sequence with a few terms at negative indices. $\endgroup$ Mar 3, 2021 at 20:14
  • $\begingroup$ ... However, a FLS cannot represent any bi-infinite sequence. If one imagines an algebraic structure that can represent bi-infinite sequences, then not only it cannot be an integral domain, it cannot be a ring at all. This makes it impossible to use an expression like $E/(1-X-X^2)$ to describe a Fibonacci-like bi-infinite series (without multiplication certainly division is meaningless), and the only candidate for the expression $E$ would be $0$. Whence "no appropriate structure" exists; some module over $K[X]$ could model bi-infinite sequences, but does not allow expressions for them. $\endgroup$ Mar 3, 2021 at 20:23
  • $\begingroup$ I think everything you have said in the comments here clarifies your answer a great deal, and so I will delete my comments to clean up the section since they don't serve much purpose anymore but to clutter this section, which I think is frowned upon and they suggest to move the comments to chat after a certain amount. Some of these clarifications that you put here will strengthen your answer if you work them into it, or leave them as comments as time allows. Thank you for your patience and explanations. $\endgroup$ Mar 4, 2021 at 1:19

This site is temporarily in read-only mode and not accepting new answers.

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