Question regarding the First Few Terms of a Fibonacci-like Recurrence.

Question

My friend handed me an interesting problem involving Fibonacci numbers and i was interested in trying to generalize it, and see what known results are around after that. But before I do that, i had a question about such generalizations.

I know the Fibonacci numbers satisfy the recurrence relation

$$F(n)=F(n-1)+F(n-2); F(0)=0, F(1)=1$$

I was taught that the first two terms are 0 and 1. Then we apply the reccurence to capture the sequence. So I was looking up generalized versions and noted that Wikipedia and Wolfram have write ups involving "Tribonacci" numbers. And they involve similar recurrence relations involving the sums of previous 3 terms;

$$T(n)=T(n-1)+T(n-2)+T(n-3)$$

Here is the wikipedia site and here is mathworld wolfram site. The wikipedia site lists then $T(0)=0, T(1)=0,$ and $T(2)=1$ while wolfram gives $T(0)=0, T(1)=1, T(2)=1$. It should be noted that these initial conditions actually generate the same sequence, but with a shifted index.

Here's my question. Why wouldn't you consider the first 3 whole numbers instead of choosing arbitrary $0$'s and $1$'? I know they aren't arbitrary necessarily, but to me it seems natural to define Tribonacci numbers, and thus higher-order Fibonacci analogs (order m?) as follows.

$$A(n)=\sum_{k=1}^m{A(n-k)}; A(k)=k, 0\le k\le m-1$$

Thus, the sequence of Tribonacci changes from what is seen on wikipedia and wolfram to

$$0,1,2,3,6,11,20,37,...$$

Then the order 4 fibonacci numbers would be

$$0,1,2,3,6,12,21,39, ...$$

Then the order 5 fibonacci numbers would be

$$0,1,2,3,4,10,19,36,70, ...$$

Answer 1

There is no deep fundamental reason besides convention. As you note, the common definitions of the $n$th order Fibonacci-like numbers are equivalent to the initial condition with the first $n-1$ being $0$ and the $n$th number being $1$. There's a certain nice-ness to this, I suppose.

A pragmatic reason might be in trying to study the sequence, in that certain initial conditions make the sequence nicer. When studying sequences defined by linear recurrences we usually use linear algebraic methods: we write $\mathbf x_n=\mathbf {Ax}_{n-1}$ then $\mathbf x_n=\mathbf{A}^n\mathbf{x}_0$. It's not hard to see that this gives nicer expressions when $\mathbf x_0=(0,0,0,\dots,1)^T$ instead of $(0,1,2,3,\dots,n)^T$.

Answer 2

I think you explain it in your question that while Wikipedia and Wolfram disagree on the root, they don't have to ignore the recurrence relation for these terms.

The fact that the roots of the 2-nacci (Fibonacci) sequence are the first two elements of the Natural numbers is not sufficient evidence to override the pattern of the N-nacci recurrence relation.

In your suggestion, you change the behavior of the $N$-nacci recurrence relation itself.