# Generalized Fibonacci sequences

Why Fibonacci sequence start at $0$, Tribonacci sequence with $0,0$, Tetranacci with $0,0,0$, etc. [ref OEIS] Has any good reasons for that?

These sequences arise in generalization of Pascal Triangle as diagonal sums and there they start at $1$.

Pascal triangle:

$$\begin{array}{} \color{red}1& \color{blue}0& \color{green}0& \color{cyan}0&\dots\\ \color{blue}1& \color{green}1& \color{cyan}0& \color{magenta}0&\dots\\ \color{green}1& \color{cyan}2& \color{magenta}1& 0&\dots\\ \color{cyan}1& \color{magenta}3& 3& \color{red}1&\dots\\ \vdots&\vdots&\vdots&\vdots&\ddots \end{array}$$

diagonal sum gives $\color{red}1,\color{blue}1,\color{green}2,\color{cyan}3,\color{magenta}5,8,\color{red}{13}\dots$ Fibonacci sequence

First generalization:

$$\begin{array}{r} \color{red}1& \color{blue}0& \color{green}0& \color{cyan}0& \color{magenta}0& 0&\color{red}0&\dots\\ \color{blue}1& \color{green}1& \color{cyan}1& \color{magenta}0& 0& \color{red}0&\color{blue}0&\dots\\ \color{green}1& \color{cyan}2& \color{magenta}3& 2& \color{red}1& \color{blue}0&\color{green}0&\dots\\ \color{cyan}1& \color{magenta}3& 6& \color{red}7& \color{blue}6& \color{green}3&\color{cyan}1&\dots\\ \color{magenta}1&4&\color{red}{10}&\color{blue}{16}&\color{green}{19}&\color{cyan}{16}&\color{magenta}{10}&\dots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{array}$$

gives sequence of diagonal sum $\color{red}1,\color{blue}1,\color{green}2,\color{cyan}4,\color{magenta}7,\dots$, Tribonacci sequence, etc.

-
Sorry, I'm slow: how are you computing your diagonal sums? –  Guess who it is. Dec 18 '11 at 1:29
Also, if you look here, I'd say it's pretty convenient to have the generalized Fibonacci numbers take on positive values for positive index. –  Guess who it is. Dec 18 '11 at 1:33
Thanks @Robert! I found this in the meantime. –  Guess who it is. Dec 18 '11 at 1:37
@J.M.: I added some color to make it more obvious. –  Brian M. Scott Dec 18 '11 at 2:19
@Peter: If $a(r,c)$ is the entry in row $r$, column $c$, $$a(r+1,c)=a(r,c)+a(r,c-1)+a(r,c-2)\;.$$ There’s an error in the table, which I’ve now fixed. –  Brian M. Scott Dec 18 '11 at 10:04

The essential definition of a $k$-nacci sequence is that the earliest positive term is $1$ and all subsequent terms are the sum of the previous $k$ terms.

So to find the second earliest positive term (which is also $1$) you need at least $k-1$ zeros at the beginning of the sequence to do the sum. In your tables there are at least $k-1$ columns of implicit zeroes to the left of the columns you show.

Since the Fibonacci sequence conventionally starts with $F(1)=1$ and $F(0)=0$, it is a plausible but not necessary convention to start the $k$-nacci sequence with the initial leading zero also at a zero index, and this is what the OEIS has done.

You could do something different, but then you would need to translate between your indices and those used by others. That is the effect of conventions.

-

While it looks natural to start Fibonacci at $f_1=1$, the Fibonacci actually goes both ways. Indeed

$$f_{n+1}=f_n+f_{n-1} \,,$$ implies

$$f_{n-1}= f_{n+1}-f_n \,.$$

Thus you can calculate $f_0$ and $f_{-n}$.

Given a recurrence which goes in both directions, any "start" point is somewhat artificial.

I find the start $f_0=0$ useful when I work with the matrices

$$F:=\left( \begin{array}{rr} 1 & 1\\ 1 & 0 \end{array}\right)=\left(\begin{array}{rr} f_2 & f_1\\ f_1 & f_0 \end{array}\right) \,.$$

Note that without starting with $f_0=0$, the standard formula

$$F^n= \left(\begin{array}{rr} f_{n+1} & f_n\\ f_n & f_{n-1} \end{array}\right)$$

would not work for $n=1$. This would make some consequences weaker, since you'd need always the eliminate the case when the parameter(s) are 1. But this would be a not needed elimination.

It is somehow similar to the following situation: You have a function $f$ in the complex plane, and you can prove it is entire, but you only need the fact that it is Analytical in some region $R$. What do you do? Do you prove that it is Analytic in the region you need for the applications you are interested, or prove it is entire?

Who knows, at some point in the future you might need that the function it is entire. You also might need to work with $f_0$, and I explained above why $f_n$ can be extended in an unique way below 0. Same can be said about the other sequences.

-

As for "Why Fibonacci sequence start at $0$?" one compelling reason is that this indexing is the natural one that reveals their interesting divisibility properties, namely that they form a strong divisibility sequence, i.e.

$$\rm\ gcd(f_m,f_n)\ =\ f_{\:gcd(m,n)}$$

hence $\rm\ m\ |\ n\ \Rightarrow\ f_m\ |\ f_n\$ etc. Analogous results hold for the more general class of Lucas-Lehmer sequences, which prove convenient when studying elementary number theory of quadratic fields, e.g. generalizations of Fermat's little theorem, Euler's $\phi$ totient function, etc. If one changed the indexing then many of these results would be greatly obfuscated.

That said, it should be emphasized that such definitions are merely conventions that prove useful in the context at hand. In other contexts - where such divisibility properties play no role - another indexing might prove more convenient.

-
Can you be more specific about Lucas-Lehmer sequences as a general notion? The only somewhat authoritative mention I can find is in OEIS, but is is only one sequence, even though its title enigmatically uses the indefinite article. As far as I know the only thing really called after Lucas and Lehmer is the primality test (in which the above sequence occurs, and no other). Possibly you meant Lucas sequences? –  Marc van Leeuwen Dec 18 '11 at 8:02
@Marc D.H. Lehmer developed an extended theory of Lucas sequences in his PhD thesis, which was published in Annals of Math., 1930 Due to such, many authors refer to the general class as Lucas-Lehmer sequences, e.g. see Ribenboim's The New Book of Prime Number Records, 1996. –  Bill Dubuque Dec 18 '11 at 15:07

Once you have also an expression, which allows interpolating to noninteger n (thus putting the sequence into a greater framework), then this might provide an argument to select a specific n as beginning of the sequence. For the Fibonacci-numbers I think the Binet-formula is
$$\small fib(n) = {((1+\sqrt 5 )^n - (1-\sqrt 5)^n) \over 2^n \sqrt 5 }$$ and then $\small fib(0) = 0$. Surely one can insert an arbitrary offset for n into the defining expression, but the given definition may be taken as the most natural.

-