The Fibonacci sequence begins $F_1,F_2 = 1$ with the recurrence relation $F_n = F_{n-1} + F_{n-2}$. Alternatively, we may say $F_0 = 0$ and $F_1 = 1$ with the same recurrence relation, and obtain the same sequence.
I am trying to observe certain patterns in 'generalized' Fibonacci numbers (recurrence relations of higher order) where intial terms are similar. However, I am torn between:
- Choosing various $k$ and focusing on the sequence $F_1,F_2,F_3 \dots$ where $F_1,F_2 \dots F_k = 1$ with the recurrence relation $F_n = \sum F_{n-i}$ where $i$ runs from $1$ to $k-1$.
- Choosing various $k$ and focusing on the sequence $F_1,F_2,F_3 \dots$ where $F_1 = 1$ and $F_0,F_{-1} \dots F_{-k+1} = 0$ with the same recurrence relation.
In the case of $k=1$, either method will produce the Fibonacci numbers. In general, however, two difference sequences are produced.
My question: is there any reason I should prefer to study classes of recurrence relations produced by one of the above methods over the other? Specifically, do either of the above methods produces classes of sequences which share more properties with the Fibonacci numbers than the other? The term 'Fibonacci-like' is tossed around frequently in literature, but does not have a concrete definition–is there a preference in literature for one of the above methods of generating Fibonacci-like sequences over the other?
Best Answer
I've been reading some papers recently on higher-order Fibonacci Numbers (aka "n-bonacci"), and I found to be common practice to define them by the recurrence $$ F_{\,n} ^{\left( m \right)} = \sum\limits_{k = 1}^m {F_{\,n - k} ^{\left( m \right)} } $$ so that there is common agreement on that $m=2$ be the standard Fibonacci,
and assigning as initial values the $m$-tuple $$ \left( {\underbrace {0,0, \cdots ,0}_{m - 1\;{\rm zeros}},1} \right) $$
The only difference I found is that the $m$-tuple
- by some sources (e.g 1) is made to start at the index $0$ $$ F_{\,0} ^{\left( m \right)} = F_{\,1} ^{\left( m \right)} = \cdots = F_{\,m - 2} ^{\left( m \right)} = 0,\quad F_{\,m - 1} ^{\left( m \right)} = 1 $$ - others (e.g. 2) prefer to fix the one at $n=1$ and so put $$ F_{\, - m + 2} ^{\left( m \right)} = F_{ - m + 3} ^{\left( m \right)} = \cdots = F_{\,0} ^{\left( m \right)} = 0,\quad F_{\,1} ^{\left( m \right)} = 1 $$ The difference is just a shift in the lower index.
I personally prefer the second setting since it provides a simpler extension of the o.g.f. $$ \eqalign{ & G\left( {z,2} \right) = {z \over {1 - z - z^{\,2} }} = {z \over {1 - z\left( {1 + z} \right)}} = {z \over {1 - z{{1 - z^{\,2} } \over {1 - z}}}}\quad \Rightarrow \cr & \Rightarrow \quad G\left( {z,m} \right) = {z \over {1 - z\left( {1 + z + \cdots + z^{\,m - 1} } \right)}} = {z \over {1 - z{{1 - z^{\,m} } \over {1 - z}}}} \cr} $$