On the Characteristic Polynomial of the Generalized k-Distance Tribonacci Sequences

Abstract

In 2008, I. Włoch introduced a new generalization of Pell numbers. She used special initial conditions so that this sequence describes the total number of special families of subsets of the set of n integers. In this paper, we prove some results about the roots of the characteristic polynomial of this sequence, but we will consider general initial conditions. Since there are currently several types of generalizations of the Pell sequence, it is very difficult for anyone to realize what type of sequence an author really means. Thus, we will call this sequence the generalized k-distance Tribonacci sequence ${(T_n^{(k)})}_{n\ge 0}$.

1. Introduction

The Fibonacci numbers ${(F_n)}_n$ was first described in connection with computing the number of descendants of a pair of rabbits in the book Liber Abaci in 1202 (see [1], pp. 404–405). This sequence is probably one of the best known recurrent sequences and it is defined by the second order recurrence (firstly used by Albert Girard in 1634, see [2], p. 393)

$$F_n=F_{n-1}+F_{n-2},\mathrm{for}n\ge 2,$$

(1)

with initial values $F_0=0$ and $F_1=1$. The Fibonacci numbers have the a closed form expression for the computation (without appealing to its recurrence) of the nth Fibonacci number. It is called Binet’s formula in honor of Jacques Binet, which discovered this formula in 1843 (see [2] or [3], p. 394),

$$F_n={\displaystyle \frac{{\alpha }^n-{\beta }^n}{\sqrt{5}}},$$

where $\alpha :=(1+\sqrt{5})/2$ and $\beta :=(1-\sqrt{5})/2$ are the roots of the characteristic equation $x^2-x-1=0$. The Fibonacci numbers have been the main object of many books and papers (see for example [4,5,6,7,8,9] and some references therein). Many generalizations of the Fibonacci sequence have appeared in the literature. Probably the most well-known generalization are the k-generalized Fibonacci sequence ${(F_n^{(k)})}_{n\ge -(k-2)}$ (also known as the k-bonacci, the k-fold Fibonacci or k-th order Fibonacci), satisfying

$$F_n^{(k)}=F_{n-1}^{(k)}+F_{n-2}^{(k)}+\cdots +F_{n-k}^{(k)},$$

with initial values $F_{-j}^{(k)}=0$ (for $j=0,1,2,\cdots k-2$) and $F_1^{(k)}=1$. For instance, for $k=2$, we have the usual Fibonacci numbers ${(F_n^{(2)})}_n$ and for $k=3$, ${(F_n^{(3)})}_n$ we get the Tribonacci numbers (see Feinberg’s introductory paper [10] and Spickerman’s paper [11] with properties of roots of its characteristic equation). Miles [12] seems to be the introductory paper of this generalization. In 1971, Miller [13] proved some basic facts on the geometry of the roots of their characteristic equation $x^k-x^{k-1}-x^{k-2}-\cdots -x-1=0$, what was the bases for gradually finding the “Binet-like” formula for the sequence ${(F_n^{(k)})}_n$ (see [14,15,16]) and for some properties of this sequence, see, for instance [17,18,19,20,21,22,23,24,25,26,27,28,29].

In 2008, Włoch [30] studied the total number of k-independent sets in some special simple, undirected graphs. She showed that this number is equal to the terms of the sequence ${(T_n^{(k)})}_{n\ge 0}$, where these numbers are defined for an integer $k\ge 2$ by

$$T_n^{(k)}=T_{n-1}^{(k)}+T_{n-k+1}^{(k)}+T_{n-k}^{(k)},\mathrm{for}n\ge k+3,$$

(2)

with initial values

$$T_i^{(k)}=2k-2,\mathrm{for}3\le i\le k,T_{k+1}^{(k)}=2k+1,T_{k+2}^{(k)}=\left\{\begin{array}{cc}12,\hfill & \mathrm{if}k=2;\hfill \\ 2k+7,\hfill & \mathrm{if}k\ge 3.\hfill \end{array}\right.$$

She called these numbers the generalized Pell numbers, but we think that this notation is quite unclear as there are already many types of generalized Pell sequences and as this sequence is defined by “four terms recurrence relation” as the Tribonacci sequence, so we will call this sequence generalized k-distance Tribonacci sequence (the notation “k-distance’’ is very suitable as it was introduced in the same meaning, e.g., in papers [31,32,33]).

In this work, we are interested in the sequence ${(T_n^{(k)})}_{n\ge 0}$ defined by the recurrence Equation (2), but with general initial values $T_i^{(k)}=c_i$, for an integer $i\in [0,k-1]$ (where $c_0,c_1,\dots ,c_{k-1}$ are real numbers, previously chosen). Let $f_k(x)=x^k-x^{k-1}-x-1$ be characteristic polynomial of this sequence. Note that $f_2(x)=x^2-2x-1$ has roots $1\pm \sqrt{2}$ which are the generators of the Pell sequence (by its “Binet-like” formula)

$$P_n={\displaystyle \frac{{(1+\sqrt{2})}^n-{(1-\sqrt{2})}^n}{2\sqrt{2}}}.$$

In fact, $P_n=T_n^{(2)}$ coincide with the Pell sequence (for the choice of $P_0=0$ and $P_1=1$), while, the sequence $T_n^{(3)}$ coincides with the Tribonacci sequence $T_n$.

As the properties of roots of ${(F_n^{(2)})}_n$ turned out important for its deeper study, in this paper, we shall study the behavior (in the algebraic and analytic sense) of the roots of $f_k(x)$. More precisely, our main result is the following:

Theorem 1.

For $k\ge 2$, let $f_k(x)=x^k-x^{k-1}-x-1$ be the characteristic polynomial of $(T_n^{(k)})$. Then the following hold

(i) 

$f_k(x)$ has a dominant root, say ${\alpha }_k$, which is its only positive root, with

$$1<{\alpha }_k\le 1+\sqrt{{\displaystyle \frac{2}{k-1}}},$$

for all $k\ge 2$. In particular, ${\alpha }_k$ tends to $1$ as $k\to \infty$.

(ii) 

$f_k(x)$ has a negative root (which is unique) only when k is even.

(iii) 

All the roots of $f_k(x)$ are simple roots.

(iv) 

${({\alpha }_k)}_k$ is a strictly decreasing sequence.

2. Auxiliary Results

In this section, we shall present two results which will be essential ingredients in the proof of our results. For clarity, we record some notations. As usual, $[a,b]$ denotes the set $\{a,a+1,\dots ,b\}$, for integers $a<b$. Also, $B[0,1]$ denotes the closed unit ball (i.e., all complex numbers z such that $\left|z\right|\le 1$) and ${\mathcal{R}}_g$ is defined as the set of all complex zeros of the polynomial $g(x)$.

The first tool is the famous Descartes’ sign rule which gives an upper bound on the number of positive or negative real roots of a polynomial with real coefficients. For the sake of completeness, we shall state it as a lemma.

Lemma 1

(Descartes’ sign rule). Let $f(x)=a_{n_1}{x}^{n_1}+\cdots +a_{n_k}{x}^{n_k}$ be a polynomial with nonzero real coefficients and such that $n_1>n_2>\cdots >n_k\ge 0$. Set

$$\nu :=\#\{i\in [1,k-1]:a_{n_i}{a}_{n_{i+1}}<0\}.$$

Then, there exists a non-negative integer r such that $\#{\mathcal{R}}_f=\nu -2r$ (multiple roots of the same value are counted separately).

As a corollary, we have that for obtaining information on the number of negative real roots, we must apply the previous rule for $f(-x)$.

Remark 1.

Generally speaking, the previous result says that if the terms of a single-variable polynomial with real coefficients are ordered by descending variable exponent, then the number of positive roots of the polynomial is equal to the number of sign differences between consecutive nonzero coefficients, minus an even non-negative integer.

A fundamental result in the theory of recurrence sequences asserts that:

Lemma 2.

Let $(u_n)$ be a linear recurrence sequence whose characteristic polynomial $\psi (x)$ splits as

$$\psi (x)={(x-{\alpha }_1)}^{m_1}\cdots {(x-{\alpha }_{\ell })}^{m_{\ell }},$$

where the ${\alpha }_j$’s are distinct complex numbers. Then, there exist uniquely determined non-zero polynomials $g_1,\dots ,g_{\ell }\in \mathbb{Q}({\left\{{\alpha }_j\right\}}_{j=1}^{\ell })\left[x\right]$, with $deg{g}_j\le m_j-1$ ($m_j$ is the multiplicity of ${\alpha }_j$ as zero of $\psi (x)$), for $j\in [1,\ell ]$, such that

$$u_n=g_1(n){\alpha }_1^n+g_2(n){\alpha }_2^n+\cdots +g_{\ell }(n){\alpha }_{\ell }^n,foralln.$$

(3)

The proof of this result can be found in [34], Theorem C.1.

Another useful and very important result is due to Eneström and Kakeya [35,36]:

Lemma 3

(Eneström-Kakeya theorem). Let $f(x)=a_0+a_{1}x+\cdots +a_n{x}^n$ be an n-degree polynomial with real coefficients. If $0\le a_0\le a_1\le \cdots \le a_n$, then all zeros of $f(x)$ lie in $B[0,1]$.

Now, we are ready to deal with the proof of the theorem.

3. The Proof of the Main Theorem

3.1. Proof of Item (i)

Proof. 

By Lemma 1, the polynomial $f_k(x)=x^k-x^{k-1}-x-1$ has only a positive root, say ${\alpha }_k$. From now on, by abuse of notation, we shall write f for $f_k$ and $\alpha$ for ${\alpha }_k$. By using that ${\alpha }^k={\alpha }^{k-1}+\alpha +1$, we obtain that $f(x)=(x-\alpha )g(x)$, where

$$g(x)=x^{k-1}+(\alpha -1)x^{k-2}+({\alpha }^2-\alpha )x^{k-3}+\cdots +({\alpha }^{k-2}-{\alpha }^{k-3})x+{\alpha }^{k-1}-{\alpha }^{k-2}-1.$$

We claim that if z is a root of $g(x)$, then $\left|z\right|\le \alpha$. In fact, it suffices to prove that all the roots of $h(x):=g(\alpha x)$ belong to $B[0,1]$. This holds by applying Lemma 3 to the polynomial

$$h(x)={\alpha }^{k-1}{x}^{k-1}+\sum _{j=1}^{k-2}({\alpha }^{k-1}-{\alpha }^{k-2})x^{k-j-1}+{\alpha }^{k-1}-{\alpha }^{k-2}-1,$$

since ${\alpha }^{k-1}>{\alpha }^{k-1}-{\alpha }^{k-2}>{\alpha }^{k-1}-{\alpha }^{k-2}-1={\alpha }^{k-2}(\alpha -1)-1>0$ (this last inequality is valid because ${\alpha }^{k-2}=(\alpha +1)/(\alpha (\alpha -1))$).

Now, since $\alpha$ is the only positive root of $f(x)$ and ${lim}_{x\to \infty }f(x)=+\infty$, then $f(x)\ge 0$, for all $x\ge \alpha$ (also, $\alpha >1$). Our second claim is that if z is root of $f(x)$ with $\rho :=\left|z\right|\ge \alpha$, then z is a real number. Indeed, since $f(\rho )\ge 0$. then ${\rho }^k\ge {\rho }^{k-1}+\rho +1$. On the other hand, the triangle inequality yields ${\rho }^k\le {\rho }^{k-1}+\rho +1$ and so

$$2{\rho }^k=|z^k+z^{k-1}{+z+1|\le |z|}^k+{\left|z\right|}^{k-1}+\left|z\right|+1={\left|z\right|}^k+{\rho }^{k-1}+\rho +1\le 2{\rho }^k.$$

Thus $|z^k+z^{k-1}+z+1|={\left|z\right|}^k+{\left|z\right|}^{k-1}+\left|z\right|+1$ implying that $1,z,z^{k-1}$ and $z^k$ lie in the same ray. In particular, there are real numbers $t_1$ and $t_2$ such that $1+t_1(z-1)=z^{k-1}$ and $1+t_2(z-1)=z^k$. Thus $(z^k-1)/(z-1)$ and $(z^{k-1}-1)/(z-1)$ are real numbers and by subtracting them, we deduce that so is $z^{k-1}$. Therefore, $z=(z^k-t_2-1)/t_2$ is also a real number, as desired.

In conclusion, if z is a root of $f(x)$ with $\left|z\right|\ge \alpha$, then z is a real number with $\left|z\right|=\alpha$. Thus, $z\in \{-\alpha ,\alpha \}$. However, $f(-\alpha )=0$ leads to the absurdity as $a^k=1$ or ${\alpha }^{k-1}=-1$ (according to k is even or odd, respectively). Therefore, $\alpha$ is the dominant root of $f(x)$.

To finish the proof of this item, we must prove that

$$1<{\alpha }_k\le 1+\sqrt{{\displaystyle \frac{2}{k-1}}}.$$

For that, it is enough to show that $f(1)<0$ and $f(1+\sqrt{2/(k-1)})\ge 0$. In fact, $f(1)=-2$ and, since $f(x)=x^{k-1}(x-1)-(x+1)$, we have

$$\begin{array}{ccc}\hfill f\left(1+\sqrt{{\displaystyle \frac{2}{k-1}}}\right)& =& {\left(1+\sqrt{{\displaystyle \frac{2}{k-1}}}\right)}^{k-1}·\sqrt{{\displaystyle \frac{2}{k-1}}}-\left(2+\sqrt{{\displaystyle \frac{2}{k-1}}}\right)\hfill \\ & \ge & \left(1+(k-1)\sqrt{{\displaystyle \frac{2}{k-1}}}\right)·\sqrt{{\displaystyle \frac{2}{k-1}}}-2-\sqrt{{\displaystyle \frac{2}{k-1}}}\hfill \\ & =& 0,\hfill \end{array}$$

where we used the Bernoulli’s inequality: ${(1+x)}^n\ge 1+nx$ for every integer $n\ge 0$ an every real number $x>-1$ (note that $k-1\ge 1$). □

3.2. Proof of Item (ii)

Proof. 

By using Lemma 1 and the fact that $f(-x)=x^k+x^{k-1}+x-1$ (for k even), then $f(x)$ has exactly one negative root.

For the case in which k is odd, we have that $f(-x)=-x^k-x^{k-1}+x-1$ and so, again by Lemma 1, we infer that the number of negative roots of $f(x)$ is either 0 or 2. Thus, we need to find another approach to conclude that there is no $z<0$ such that $f(z)=0$, when k is odd. To prove this, it suffices to show that $f^{\prime }(x)>0$, for $x<-1$ and $f(x)<0$, for all $x\in (-1,0)$. In fact, $f(x)=x^{k-1}(x-1)-(x+1)<0$, since $x+1\in (0,1)$ while $x^{k-1}(x-1)<0$, for $x<0$ (here we used that $k-1$ is even and so $x^{k-1}>0$). Furthermore, $f^{\prime }(x)=x^{k-2}(kx-k+1)$ is positive, for $x<-1$, since $x^{k-2}<0$ (because $k-2$ is odd), while $kx-k+1<-2k+1<0$ for $x<-1$. This finishes the proof. □

3.3. Proof of Item (iii)

Proof. 

Aiming for a contradiction, suppose that z is a double root of $f(x)$. Then, $f(z)=f^{\prime }(z)=0$. Since $f^{\prime }(x)=k{x}^{k-1}-(k-1)x^{k-2}-1$, then $z^k-z^{k-1}-z-1=0$ and $k{z}^{k-1}-(k-1)z^{k-2}-1=0$. Thus,

$$0=k(z^k-z^{k-1}-z-1)-z(k{z}^{k-1}-(k-1)z^{k-2}-1)=-z^{k-1}-(k-1)z-k$$

and so

$$\begin{array}{ccc}\hfill 0& =& -k(z^{k-1}+(k-1)z+k)+(k{z}^{k-1}-(k-1)z^{k-2}-1)\hfill \\ & =& -(k-1)z^{k-2}-k(k-1)z-(k^2+1).\hfill \end{array}$$

Hence, we obtain

$$\begin{array}{ccc}\hfill 0& =& -z((k-1)z^{k-2}+k(k-1)z+(k^2+1))+(k-1)(z^{k-1}+(k-1)z+k)\hfill \\ & =& -k(k-1)z^2-2kz+k(k-1)\hfill \end{array}$$

yielding that $(k-1)z^2+2z-(k-1)=0$. Therefore, $z\in \{z_{-},z_{+}\}$, where

$$z_{\pm }={\displaystyle \frac{-1\pm \sqrt{{(k-1)}^2+1}}{k-1}}.$$

Since $z_{\pm }$ are both real numbers, then if $z=z_{+}$, we infer that $z_{+}=\alpha$. However, $\alpha >1$ implying that $-1+\sqrt{{(k-1)}^2+1}>k-1$ which leads to the absurd that $k<1$. In the case in which $z=z_{-}$, we use that the negative root of f satisfies $z_{-}\in (-1,0)$ (since k is even and then $f(0)=-1$ and $f(-1)=2$) and after some manipulations, we arrive again at the absurdity of $k<1$. In conclusion, such a root z does not exist and so, all the roots of $f(x)$ are simple roots. □

3.4. Proof of Item (iv)

Proof. 

We now wish to prove that ${\alpha }_k>{\alpha }_{k+1}$. For ease of notation, set $\alpha :={\alpha }_k$ and $\beta :={\alpha }_{k+1}$. Let us define the polynomial ${\psi }_k(x):=f_{k+1}(x)+1=x^{k+1}-x^k-x$. Since ${\psi }_k^{\prime }(x)=((k+1)x-k)x^{k-1}-1>0$ (for $x>1$ and $k\ge 2$), then ${\psi }_k:(1,\infty )\to \mathbb{R}$ is an increasing function. Note that ${\psi }_k(\beta )=1$ and the relation ${\alpha }^k-{\alpha }^{k-1}-1=\alpha$, implies that ${\psi }_k(\alpha )={\alpha }^2$. Since, by item (i), $\alpha ,\beta \in (1,\infty )$, and ${\psi }_k(\alpha )={\alpha }^2>1={\psi }_k(\beta )$, then $\alpha >\beta$. In conclusion, ${\alpha }_k>{\alpha }_{k+1}$ yielding that the sequence ${({\alpha }_k)}_k$ is strictly decreasing. □

4. Applications of Our Results

In this section, we shall show an application of our results for the distribution of the dominant root ${\alpha }_k$ depending on k and the determination of its upper bound (of course this is also an upper bound to the absolute value of all the other roots). For example, by Theorem 1 and Lemma 2, we can write a k-distance Tribonacci sequence in its asymptotic form

$$T_n^{(k)}=c{\alpha }_k^n(1+o(1)),$$

where c is a nonzero constant and $o(1)$ is a function which tends to 0 as $n\to \infty$. Therefore, the growth of ${\alpha }_k$ is a crucial step to gain an understanding about the growth of the sequence ${(T_n^{(k)})}_n$. This behavior and its precision is showed in the

Table 1. The dominant root ${\alpha }_k$ of $f_k(x)=x^k-x^{k-1}-x-1$ and its upper bound $A(k)=1+\sqrt{2/(k-1)}$ for k from 2 to 49.

k	${\mathit{\alpha }}_{\mathit{k}}$	$\mathit{A}(\mathit{k})$	k	${\mathit{\alpha }}_{\mathit{k}}$	$\mathit{A}(\mathit{k})$	k	${\mathit{\alpha }}_{\mathit{k}}$	$\mathit{A}(\mathit{k})$
2	2.414213562	2.414213562	18	1.163910449	1.342997170	34	1.097462321	1.246182982
3	1.839286755	2.000000000	19	1.156780140	1.333333333	35	1.095189446	1.242535625
4	1.618033989	1.816496581	20	1.150313062	1.324442842	36	1.093031609	1.239045722
5	1.497094049	1.707106781	21	1.144417473	1.316227766	37	1.090979976	1.235702260
6	1.419632763	1.632455532	22	1.139018098	1.308606700	38	1.089026607	1.232495277
7	1.365254707	1.577350269	23	1.134052557	1.301511345	39	1.087164353	1.229415734
8	1.324717957	1.534522484	24	1.129468689	1.294883912	40	1.085386751	1.226455407
9	1.293188036	1.500000000	25	1.125222520	1.288675135	41	1.083687949	1.223606798
10	1.267874775	1.471404521	26	1.121276701	1.282842712	42	1.082062631	1.220863052
11	1.247047862	1.447213595	27	1.117599293	1.277350098	43	1.080505957	1.218217890
12	1.229573607	1.426401433	28	1.114162811	1.272165527	44	1.079013511	1.215665546
13	1.214676212	1.408248290	29	1.110943467	1.267261242	45	1.077581254	1.213200716
14	1.201805729	1.392232270	30	1.107920561	1.262612866	46	1.076205487	1.210818511
15	1.190560750	1.377964473	31	1.105075990	1.258198890	47	1.074882811	1.208514414
16	1.180640991	1.365148372	32	1.102393848	1.254000254	48	1.073610101	1.206284249
17	1.171817047	1.353553391	33	1.099860103	1.250000000	49	1.072384476	1.204124145

, Figure 1 and Figure 2.

5. Conclusions

In this paper, we have been interested in the behavior of the so-called k-distance Tribonacci sequence which is a kth order recurrence defined by $T_n^{(k)}=T_{n-1}^{(k)}+T_{n-k+1}^{(k)}+T_{n-k}^{(k)}$. There exist many results in literature which permit transfer the study of the behavior of the sequence to the knowledge of the analytic and algebraic properties of roots of its characteristic polynomial (in a form of a “Binet-like formula”). In our case, this polynomial is $f_k(x)=x^k-x^{k-1}-x-1$. Therefore, in this work, we shall explicit a complete study of the roots of $f_k(x)$. For example, in our main result, we shall prove (among other things) the existence of a dominant root ${\alpha }_k\in (1,2)$ (together with some more accurate lower and upper bounds), for all $k\ge 2$. Moreover, we shall show that ${({\alpha }_k)}_{k\ge 2}$ is a strictly decreasing sequence (which converges to 1 as $k\to \infty$).