Source-linked AI summary
A simplified Binet formula for k-generalized Fibonacci numbers
Gregory P. Dresden
TL;DR
The paper asks whether k-generalized Fibonacci numbers can be generated by a simple Binet-style expression and whether its first term suffices to recover the sequence. The paper represents the sequence using roots of its characteristic polynomial and considers a rounded expression based on the unique positive root. For all n ≥ 2−k, the nearest integer to the first-term expression gives the nth k-generalized Fibonacci number.
Problem
The paper asks whether k-generalized Fibonacci numbers can be generated by a simple Binet-style expression and whether its first term suffices to recover the sequence.
Source: §1 · p. 3Method
The paper represents the sequence using roots of its characteristic polynomial and considers a rounded expression based on the unique positive root.
Source: §1 · p. 3Results
For all n ≥ 2−k, the nearest integer to the first-term expression gives the nth k-generalized Fibonacci number.
Source: §1 · p. 3Takeaways & Limitations
For this family, the rounded dominant-root expression generates the sequence across the theorem’s stated index range.
Source: §1 · pp. 2–3When two roots have absolute value greater than 1, it is impossible to express G_n in terms of just one of these two numbers.
Source: §1 · p. 3
Abstract
from arXiv · showhide
We present a particularly nice Binet-style formula that can be used to produce the k-generalized Fibonacci numbers (that is, the Tribonaccis, Tetranaccis, etc). Furthermore, we show that in fact one needs only take the integer closest to the first term of this Binet-style formula to generate the desired sequence. These results were also found (independently) at about the same time by Zhaohui Du of Singapore, China. We are working on a joint paper.
1 Introduction
The paper presents a Binet-style representation of k-generalized Fibonacci numbers and shows that a rounded dominant-root expression generates the sequence. It also notes that this simplification does not extend to every recurrence sequence.
1 Introduction
- The k = 3 and k = 4 sequences are called Tribonaccis and Tetranaccis; these numbers also appear in probability theory and certain sorting algorithms [6].Source: §1 · p. 1
- Theorem 1 represents each k-generalized Fibonacci term using the roots of x^k − x^{k−1} − ··· − 1 = 0.The authors call this a new presentation rather than a new result; for k = 2, it reduces to their standard-Fibonacci Binet variant.Source: §1 · p. 2
- For sufficiently large n, the other roots’ contributions become negligible, leaving a dominant-root expression for the sequence.The characteristic polynomial has one root with absolute value greater than 1; the others lie strictly inside the unit circle.Source: §1 · p. 2
- Theorem 2 gives a nearest-integer formula for k-generalized Fibonacci numbers for all n ≥ 2−k, using the unique positive root α.The stated root is that of x^k − x^{k−1} − ··· − 1 = 0.Source: §1 · p. 3
- For k = 6, the rounding error is not monotone decreasing, so the theorem is not trivial from an error-decrease argument.The passage points to a chart illustrating the error.Source: §1 · p. 3
- The one-root simplification is not universal: for the recurrence Gn = 2Gn−1 + 4Gn−2, two roots have absolute value greater than 1, precluding an expression through just one.The paper also gives a scaled Fibonacci example whose Binet formula applies only for n ≥ 5.Source: §1 · p. 3
2 Previous Results
The section situates the paper’s formulas among earlier generalized-Fibonacci work, noting prior Tribonacci results and a connection to Wolfram’s arbitrary-starting-condition formula. It also reviews known properties of the polynomials whose roots appear in these formulas.
2 Previous Results
- Spickerman had previously found the paper’s Theorem 2 for the Tribonacci numbers.The cited formula uses the roots of x^3−x^2−x−1=0.Source: §2 · p. 3
- Spickerman and Joyner’s formula uses the roots of x^k−x^(k−1)−···−1, and the paper observes that its first term alone suffices for n≥0.The authors say this was already done by Spickerman for k=3.Source: §2 · p. 4
- The paper’s Theorem 1 formula is equivalent to the Spickerman-Joyner formula and is therefore a special case of Wolfram’s extension to arbitrary starting conditions.Wolfram’s extension allows starting conditions other than 0, 0, …, 0, 1.Source: §2 · p. 4
- The polynomials x^k−x^(k−1)−···−1 have one zero outside the unit circle, and for k≥3 their zeros cannot be constructed by ruler and compass.For 5≤k≤11, the zeros are not expressible in radicals; whether that holds more generally remains open.Source: §2 · p. 4
3 Preliminary Lemmas
The preliminary lemmas bound the positive root used in the formulas and characterize the recurrence satisfied by the approximation error. They also develop properties of the auxiliary function m(k).
3 Preliminary Lemmas
- For k≥6, the positive root α lies between 2−1/3k and 2.The authors present a simpler proof of this bound than appealing to Wolfram’s earlier result [13].Source: §3 · p. 5
- The auxiliary function m(k) is continuous and decreasing on the interval considered in Lemma 4.The supplied lemma passages also establish a comparison between x and m(k)(x) on that interval.Source: §3 · p. 5
- The error E_n in the Binet approximation satisfies the same recurrence as the k-generalized Fibonacci numbers for n≥2.E_n is defined as the error in the approximation of Theorem 2.Source: §3 · p. 6
4 Proof of Theorem 1
The proof identifies the roots of the characteristic polynomial and uses their defining equation to transform the Spickerman–Joyner formula. The transformation establishes its equivalence to equation (2) of Theorem 1.
4 Proof of Theorem 1
- The roots α_i of x^k − x^(k−1) − · · · − 1 = 0 provide the basis for comparing the two formulas.The proof then uses a relation obtained from this root equation to transform the formula.Source: §4 · p. 6
- Multiplying the root equation by α_i − 1 yields a relation used to transform the Spickerman–Joyner formula.The passage gives the multiplication step and introduces its use in the transformation.Source: §4 · p. 6
- The resulting transformation establishes that formulas (11) and (12) are equivalent.The proof states this as the desired equivalence.Source: §4 · p. 6
5 Proof of Theorem 2
The proof bounds the error E_n by 1/2: it handles initial indices and rules out later errors reaching that threshold. The contradiction uses the recurrence for E_n and the fact that the error eventually tends to zero.
5 Proof of Theorem 2
- The proof handles initial indices by bounding |E_n| below 1/2 for n = 0 and n = −1, −2, …, 2 − k, and separately establishes |E_1| < 1/2.For the negative indices, it uses the bound at n = 0 together with α^−1 < 1.Source: §5 · p. 7
- For n ≥ 2, E_n = E_(n−1) + E_(n−2) + · · · + E_(n−k), the recurrence used in the contradiction argument.Assuming a first error of magnitude at least 1/2 leads to |E_(n0+1)| > |E_n0| and then successive growth, contrary to the error eventually tending to zero.Source: §5 · p. 7
- |E_n| < 1/2 for all n ≥ 2 − k, as the proof establishes for n ≥ 2 and then extends to the initial indices.For n ≥ 2, an error reaching 1/2 would force successive errors to grow, contradicting eventual decay; the proof also treats earlier indices and E_1.Source: §5 · p. 7