Abstract
Recently, Bednarz introduced a new two-parameter generalization of the Fibonacci sequence, which is called the \((k,p)\)-Fibonacci sequence and denoted by \((F_{k,p}(n))_{n\geq0}\). In this paper, we study the geometry of roots of the characteristic polynomial of this sequence.
Similar content being viewed by others
1 Introduction
The Fibonacci sequence \((F_{n})_{n}\) is one of the most famous sequences in mathematics. This sequence is defined by the binary recurrence \(F_{n+2}=F_{n+1}+F_{n}\) for \(n\geq 0\) with initial values \(F_{0}=0\) and \(F_{1}=1\). So, its first ten nonzero terms are 1, 1, 2, 3, 5, 8, 13, 21, 34, and 55. A well-known nonrecursive formula for the nth Fibonacci number is called the Binet formula:
where \(\alpha :=(1+\sqrt{5})/2\) and \(\beta :=(1-\sqrt{5})/2\). The Fibonacci numbers have been the main object of many books (see, e.g., [1–5] and some references therein). Many generalizations of this sequence have appeared in the literature. Probably, the most known generalization is the k-generalized Fibonacci sequence \((F^{(k)}_{n})_{n\geq -(k-2)}\) (also known as the k-bonacci, the k-fold Fibonacci, or kth-order Fibonacci) defined by
with initial values \(F^{(k)}_{-j}=0\) (for \(j = 0,1,\ldots , k-2\)) and \(F^{(k)}_{1}=1\). Their recent wide and intensive study was started in 1960 by Miles [6]. In 1971, Miller [7] proved some basic facts on the geometry of the roots of their characteristic polynomial
which was a foundation for a systematic search for a “Binet-like” formula for \((F^{(k)}_{n})_{n}\) (see, e.g., [8–10]). The k-generalized Fibonacci sequence was further generalized; see [11–15].
Another generalization, applied in a new coding method, and defined by the recurrence
with \(F_{p}(j)=1\) for \(j = 1,\ldots , p+1\), was introduced by Stakhov [16] and is called as Fibonacci p-numbers. Stakhov and Rozin [17, 18] studied some properties of the roots of their characteristic equation
and Kılıç [13] proved that all roots are simple and provided a “Binet-like” formula for \((F_{p}(n))_{n}\). This sequence was gradually generalized in [19–22].
In 2008, Włoch [23] studied the total number of k-independent sets in some graphs, which led her to the sequence \((P(n,k))_{n\geq 0}\) called the generalized Pell numbers. For \(k\geq 2\), these numbers are defined by the recurrent relation
with initial values \(P(i,k)=2k-2\) for \(3 \leq i\leq k\), \(P(k+1,k)=2k+1\), and
Recently, Trojovský [24] dealt with the behavior (in the algebraic and analytic sense) of the roots of the characteristic polynomial \(p_{k}(x)=x^{k}-x^{k-1}-x-1\) of the sequence \((P(n,k))_{n\geq 0}\).
Very recently, Bednarz [25] introduced a new type of generalization of Fibonacci numbers (depending on two integer parameters \(p\geq 2\) and \(k\geq 3\)), called the \((k,p)\)-Fibonacci numbers, by the following recurrence:
with initial values \(F_{k,p}(0)=0\) and \(F_{k,p}(j)=p^{j-1}\), \(j = 1,2,\ldots , k-1\). The characteristic polynomial of this sequence is
In 2020, Bednarz and Włoch [26] studied interesting interpretations of these numbers in undirected simple graphs and found some interesting identities.
In this paper, we are interested in studying the geometry of roots of the characteristic polynomial of this sequence \((F_{k,p}(n))_{n\geq 0}\). Our main result is the following:
Theorem 1
For integers \(p\geq 2\) and \(k\geq 3\), the polynomial \(f_{k,p}(x)\) has the following properties:
-
(i)
\(f_{k,p}(x)\) has a dominant root, say \(\alpha _{k,p}\) (which is its only positive root), and
$$ p < \alpha _{k,p} < p+ \frac{2}{p^{k-3}} $$for all \(k\geq 2\). In particular, \(\lim_{k\to \infty }\alpha _{k,p}=p\) and \(\lim_{p\to \infty }\alpha _{k,p}=\infty \);
-
(ii)
\(f_{k,p}(x)\) has one negative root for any \(p\geq 2\) and even \(k\geq 3\);
-
(iii)
\(f_{k,p}(x)\) has two negative roots when k is odd:
- (\(\mathrm{iii} _{a}\)):
-
\(p=3\) and \(k\geq 7\),
- (\(\mathrm{iii} _{b}\)):
-
\(p\in \{4,5,6\}\) and \(k\geq 5\),
- (\(\mathrm{iii} _{c}\)):
-
\(p\geq 7\) and \(k\geq 3\);
-
(iv)
all roots of \(f_{k,p}(x)\) are simple.
As in all previous generalizations of Fibonacci numbers, this theorem is the basis for finding a Binet-like formula for direct calculation of terms of the sequence \(F_{k,p}(n)\), but since the roots of its characteristic polynomial do not have a simple form, the existence of a certain simple formula is unlikely. We will show, however, a particular case, in which we know a little more about the roots.
Remark 1
If \(k\equiv 5\pmod{6}\), then \(x^{2}-x+1\) divides \(f_{k,p}(x)\), that is, \(f_{k,p}(\omega ^{j})=0\) for \(\omega =(1+\sqrt{-3})/2\) and \(j\in \{1,2\}\). Indeed, since \(\omega ^{3}=-1\), \(\omega ^{4}=-\omega \), \(\omega ^{5}=-\omega ^{2}\), and \(\omega ^{6}=1\), we have (for \(k=6t+5\), where t is a nonnegative integer)
The same argument can be used to deduce that \(f_{k,p}(\omega ^{2})=0\). Furthermore, a short calculation shows the factorization
Example 1
Using Remark 1 (and Cardano’s formula), we can find the exact form for all roots of the characteristic polynomial
in the following form:
where
With respect to Theorem 1, we know that the polynomial \(x^{3}-(p-1) x^{2}-p x - 1\) (the second factor in (2)) has one positive real root \(\alpha _{3}\) and two roots \(\alpha _{4/5}\), which are complex conjugate for \(p=1,2,3\), and for \(p\geq 4\), they are negative real roots.
2 Auxiliary results
In this section, we present two results, which will be essential ingredients in the proof of our results. For clarity, we introduce some notations. As usual, \([a, b]\) denotes the set \(\{a, a + 1,\ldots , b\}\) for integers \(a < b\). Also, \(B[0,1]\) is the closed unit ball (i.e., all complex numbers z such that \(|z|\leq 1\)), and \(\mathcal{R}_{g}\) is 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 completeness, we 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}\geq 0\). Set
Then, there exists a nonnegative 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 2
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 nonnegative integer.
A fundamental result in the theory of recurrence sequences is the following:
Lemma 2
Let \((u_{n})\) be a linear recurrence sequence whose characteristic polynomial \(\psi (x)\) splits as
where the \(\alpha _{j}\) are distinct complex numbers. Then there exist uniquely determined nonzero polynomials \(g_{1},\ldots ,g_{\ell }\in \mathbb{Q}(\{\alpha _{j}\}_{j=1}^{\ell })[x]\), with \(\deg g_{j}\leq m_{j}-1\) (\(m_{j}\) is the multiplicity of \(\alpha _{j}\) as zero of \(\psi (x)\)) for \(j\in [1, \ell ]\), such that
The proof of this result can be found in [27, Theorem C.1].
Another useful and very important result is due to Eneström and Kakeya [28, 29].
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\leq a_{0}\leq a_{1}\leq \cdots \leq a_{n}\), then all zeros of \(f(x)\) lie in \(B[0,1]\).
Our last tool is the following:
Lemma 4
Let \(f:\mathbb{C}\to \mathbb{C}\) be the Möbius transformation
where a, b, c, d are real numbers with \(ad-bc\neq 0\). Then \(f^{-1}(\mathbb{R})\subseteq \mathbb{R}\), that is, if \(f(z)\) is a real number, then so is z.
Proof
Suppose that ω is a complex number such that \(f(\omega )\in \mathbb{R}\). Then \(f(\omega )=\overline{f(\omega )}\) (where, as usual, z̅ denotes the complex conjugate of z). Since \(a,b,c,d\in \mathbb{R}\), we have that \(\overline{f(\omega )}=f(\overline{\omega})\), and so \(f(\omega )=f(\overline{\omega})\) yields
After a straightforward computation, we obtain that \(ad(\overline{\omega}-\omega )=bc(\overline{\omega}-\omega )\). Since \(ad\neq bc\), we have \(\overline{\omega}=\omega \), that is, ω is a real number, as desired. □
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)
First, we use Lemma 1 to deduce that the polynomial \(f_{k,p}(x)=x^{k}-px^{k-1}-(p-1)x-1\) has only a positive root, say \(\alpha _{k,p}\). From now on, by abuse of notation, we will write f for \(f_{k,p}\) and α for \(\alpha _{k,p}\). Since \(\alpha ^{k}=p\alpha ^{k-1}+(p-1)\alpha +1\), we obtain that \(f(x)=(x-\alpha )g(x)\), where
We claim that if z is a root of \(g(x)\), then \(|z|\leq \alpha \). To prove this, it suffices to show that the roots of \(h(x):=g(\alpha x)\) belong to \(B[0,1]\). This holds by applying Lemma 3 to the polynomial
since
where the last inequality is valid because \(p>1\).
Now since α is the only positive root of \(f(x)\) and \(\lim_{x\to \infty }f(x)=+\infty \), we have \(f(x)\geq 0\) for all \(x\geq \alpha \) (also, \(\alpha >p\) since \(f(p)=-p(p-1)-1\)). Our second claim is that if z is a root of \(f(x)\) with \(\nu :=|z|\geq \alpha \), then z is a real number. Indeed, since \(f(\nu )\geq 0\). we have \(\nu ^{k}\geq p\nu ^{k-1}+(p-1)\nu +1\). On the other hand, the triangle inequality yields \(\nu ^{k}\leq p\nu ^{k-1}+(p-1)\nu +1\), and thus
Thus \(|z^{k}+pz^{k-1}+(p-1)z+1|= |z|^{k}+|pz|^{k-1}+|(p-1)z|+1\), implying that 1, \((p-1)z\), \(pz^{k-1}\), and \(z^{k}\) lie in the same ray (this follows from the fact that the equality in the complex triangle inequality \(|\sum_{j=1}^{n}z_{j}|\leq \sum_{j=1}^{n}|z_{j}|\) occurs if and only if all nonzero \(z_{j}\) have the same argument, that is, \(z_{j}=a_{j}\eta \) for some \((a_{j},\eta )\in \mathbb{R}_{>0}\times \mathbb{C}\) with \(j\in [1,n]\)). So, in particular, there exists a real number \(t_{0}\) such that \(z^{k}=1+t_{0}(pz^{k-1}-1)\). Since \(z^{k}=pz^{k-1}+(p-1)z+1\), we obtain that
On the other hand, the vectors \(pz^{k-1}-(p-1)z\) and \(pz^{k-1}-1\) have the same direction, so that
is a real number. Thus
is a real number, and so is \(z^{k-1}\) (by Lemma 4). From the definition of \(t_{0}\) we also deduce that \(z\in \mathbb{R}\).
In conclusion, we proved that if z is a root of \(f(x)\) with \(|z|\geq \alpha \), then z is a real number with \(|z|=\alpha \). So, \(z\in \{-\alpha ,\alpha \}\). Suppose that \(z=-\alpha \). Then since
we arrive at an absurdity as \(\alpha ^{k}=1\) or \(p\alpha ^{k-1}=-1\), which contradicts that fact that \(\alpha >p>1\).
To finish the proof of this item, we must prove that
For that, since \(f(p)<0\), it suffices to show (by the intermediate value theorem) that \(f(p+2/p^{k-3})>0\). Indeed, since \(f(x)=x^{k-1}(x-p)-(p-1)x-1\), we get
where we used the Bernoulli inequality \((1+x)^{n} \geq 1+nx\) for all \((n,x)\in \mathbb{Z}_{\geq 0}\times \mathbb{R}_{>-1}\). The proof is complete.
3.2 Proof of item (ii)
By using Lemma 1 and the equality \(f(-x)=x^{k}+px^{k-1}+(p-1)x-1\) (for k even) \(f(x)\) has exactly one negative root.
3.3 Proof of item (iii)
In this case, \(f(-x)=-x^{k}-px^{k-1}+(p-1)x-1\), and so by Lemma 1 we have either zero or two negative roots. Since \(f(0)=-1\) and \(f(x)\) tends to −∞ (when k is odd) as \(x\to -\infty \), to prove the existence of two negative roots, we only need to find a real number \(r<0\) such that \(f(r)>0\) (again by the intermediate value theorem). Also, let \(f(x)=x^{k-1}(x-p)-(p-1)x-1\).
3.3.1 Proof of item (\(\mathrm{iii} _{a}\))
In this case, we choose \(r=-3/5\), and thus
whenever \(k>-\log 18/\log (3/5)+1=6.65823\ldots \) . Since \(k\geq 7\), the proof is complete.
3.3.2 Proof of item (\(\mathrm{iii} _{b}\))
In this case, for \(r=-1/2\), we get
Therefore
for \(k\geq 5\) and \(p\in \{4,5,6\}\).
3.3.3 Proof of item (\(\mathrm{iii} _{c}\))
In this case, also for \(r=-1/2\), we get
for \(k\geq 3\) and \(p\geq 7\).
3.4 Proof of item (iv)
Note that \(f''(x)=k(k-1)x^{k-2}-p(k-1)(k-2)x^{k-3}\). So, \(f''(x)=0\) if and only if \(x=0\) or \(x=p(k-2)/k\). However, none of these values is a root of \(f(x)\), since \(f(0)=-1\) and its only positive root \(\alpha >p\), whereas \(p(k-2)/k\in (0,p)\). Summarizing, a possible repeated root must have multiplicity 2.
Now we claim that all real roots of \(f(x)\) are simple. The only positive root α must be simple because of Lemma 1. For the negative roots, we first see that in the case of an even k, \(f'(x)\) has no negative roots. Since \(f'(-x)=-kx^{k-1}-p(k-1)x^{k-1}-(p-1)\) (and Lemma 1), when k is odd, we have two roots, which are distinct by the previous items, and so both must be simple (again by Lemma 1).
In conclusion, a possible double root must be a nonreal number. Note that \(f(x)=0\) and \(f'(x)=0\) imply
respectively. By combining the previous relations, we arrive at the following quadratic equation:
Since the roots are not real numbers, its discriminant must be negative. However, the discriminant is
This contradiction completes our proof.
4 Conclusions
In this paper, we are interested in the behavior of the so-called \((k,p)\)-Fibonacci numbers, which are a kth-order two-parameter recurrence defined by \(F_{k,p}(n) = p F_{k,p}(n-1) + (p-1) F_{k,p}(n-k+1) + F_{k,p}(n-k)\) with initial values \(F_{k,p}(0)=0\) and \(F_{k,p}(j)=p^{j-1}\) (for \(j\in [1,k-1]\)). It is well known that the study of the (arithmetic and asymptotic) behavior of a sequence is closely related to the knowledge of the analytic and algebraic properties of roots of its characteristic polynomial (a kind of “Binet-like formula”). In our case, this polynomial is \(f_{k,p}(x)=x^{k}-px^{k-1}-(p-1)x-1\). Therefore, in this work, we provided a complete study of the roots of \(f_{k,p}(x)\). For example, in our main result, we proved (among other things) the existence of a dominant root \(\alpha _{k,p}\in (p,p+2)\) (together with some more accurate lower and upper bounds) for \(k\geq 3\) and \(p\geq 2\). Moreover, these bounds allow us to deduce that \((\alpha _{k,p})\) converges to p as \(k\to \infty \) (while it is unbounded in p).
Availability of data and materials
Data sharing is not applicable to this paper as no datasets were generated or analyzed during the current study.
References
Koshy, T.: Fibonacci and Lucas Numbers with Applications. Wiley, New York (2001)
Posamentier, A.S., Lehmann, I.: The (Fabulous) Fibonacci Numbers. Prometheus Books, Amherst (2007)
Vorobiev, N.N.: Fibonacci Numbers. Birkhäuser, Basel (2003)
Hoggat, V.E.: Fibonacci and Lucas Numbers. Houghton Mifflin, California (1969)
Ribenboim, P.: My Numbers, My Friends: Popular Lectures on Number Theory. Springer, Berlin (2000)
Miles, E.P.: Generalized Fibonacci numbers and associated matrices. Am. Math. Mon. 67, 745–752 (1960)
Miller, M.D.: On generalized Fibonacci numbers. Am. Math. Mon. 78, 1108–1109 (1971)
Spickerman, W.R., Joyner, R.N.: Binet’s formula for the recursive sequence of order k. Fibonacci Q. 22, 327–331 (1984)
Wolfram, D.A.: Solving generalized Fibonacci recurrences. Fibonacci Q. 36, 129–145 (1998)
Dresden, G.P.B., Du, Z.: A simplified Binet formula for k-generalized Fibonacci numbers. J. Integer Seq. 17, 14–47 (2014)
Dickinson, D.: On sums involving binomial coefficients. Am. Math. Mon. 57, 82–86 (1950)
Gabai, H.: Generalized Fibonacci k-sequences. Fibonacci Q. 8, 31–38 (1970)
Kılıç, E.: The generalized order-k Fibonacci–Pell sequence by matrix methods. J. Comput. Appl. Math. 209, 133–145 (2007)
Marques, D., Trojovský, P.: On characteristic polynomial of higher order generalized Jacobsthal numbers. Adv. Differ. Equ. 2019, 392 (2019)
Alfuraidan, M.R., Joudah, I.N.: On a new formula for Fibonacci’s family m-step numbers and some applications. Mathematics 7, 805 (2019)
Stakhov, A.: The golden section in the measurement theory. Comput. Math. Appl. 17, 613–638 (1989)
Stakhov, A., Rozin, B.: The golden algebraic equations. Chaos Solitons Fractals 27, 1415–1421 (2006)
Stakhov, A., Rozin, B.: Theory of Binet formulas for Fibonacci and Lucas p-numbers. Chaos Solitons Fractals 27, 1162–1177 (2006)
Kocer, E.G., Tuglu, N., Stakhov, A.P.: On the m-extension of the Fibonacci and Lucas p-numbers. Chaos Solitons Fractals 40, 1890–1906 (2009)
Włoch, I., Bednarz, U., Bród, D., Wołowiec-Musiał, M., Włoch, A.: On a new type of distance Fibonacci numbers. Discrete Appl. Math. 161, 2695–2701 (2013)
Falcon, S.: Generalized \((k, r)\)-Fibonacci numbers. Gen. Math. Notes 25, 148–158 (2014)
da Silva, R., Souza de Oliveira, K., Cunha da Graca Neto, A.: On a four-parameter generalization of some special sequences. Discrete Appl. Math. 243, 154–171 (2018)
Włoch, I.: On generalized Pell numbers and their graph representations. Comment. Math. 48, 169–175 (2008)
Trojovský, P.: On the characteristic polynomial of the generalized k-distance Tribonacci sequences. Mathematics 8, 1387 (2020)
Bednarz, N.: On \((k, p)\)-Fibonacci numbers. Submitted
Bednarz, N., Włoch, I.: Some interpretations of the \((k, p)\)-Fibonacci numbers. Comment. Math. Univ. Carol. (2020) To appear
Shorey, T.N., Tijdeman, R.: Exponential Diophantine Equations. Cambridge Tracts in Mathematics, vol. 87. Cambridge University Press, Cambridge (1986)
Eneström, G.: Remarque sur un théorème relatif aux racines de l’équation \(a_{n}x^{n} + a_{n-1}x^{n-1} + \cdots+a_{1}x + a_{0} = 0\) où tous les coefficientes a sont réels et positifs. Tohoku Math. J. (1) 18, 34–36 (1920)
Kakeya, S.: On the limits of the roots of an algebraic equation with positive coefficients. Tohoku Math. J. (1) 2, 140–142 (1912)
Acknowledgements
The authors thank the anonymous referees for their significant comments and suggestions to improve the quality of paper.
Funding
The author was supported by Project of Excelence PrF UHK No. 2213/2020, University of Hradec Kralove, Czech Republic.
Author information
Authors and Affiliations
Contributions
The author read and approved the final manuscript.
Corresponding author
Ethics declarations
Competing interests
The author declares that they have no competing interests.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Trojovský, P. On the characteristic polynomial of \((k,p)\)-Fibonacci sequence. Adv Differ Equ 2021, 28 (2021). https://doi.org/10.1186/s13662-020-03186-8
Received:
Accepted:
Published:
DOI: https://doi.org/10.1186/s13662-020-03186-8