A Simplified Binet Formula for k-Generalized Fibonacci Numbers

Gregory P. B. Dresden Department of Mathematics Washington and Lee University Lexington, VA 24450 USA

                   dresdeng@wlu.edu

Zhaohui Du Shanghai China

                 zhao.hui.du@gmail.com

Abstract

In this paper, we present a 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 in order to generate the desired sequence.

1 Introduction

Let k ≥ 2 and define F_{n}^{(k)}, the n^{th} k-generalized Fibonacci number, as follows:

F_{n}^{(k)} = \begin{cases}0, & if n < 1; \\ 1, & if n = 1; \\ F_{n−1}^{(k)} + F_{n−2}^{(k)} + ⋯ + F_{n−k}^{(k)}, & if n > 1 \end{cases}

These numbers are also called generalized Fibonacci numbers of order k, Fibonacci kstep numbers, Fibonacci k-sequences, or k-bonacci numbers. Note that for k = 2, we have F_{n}^{(2)} = F_{n}, our familiar Fibonacci numbers. For k = 3 we have the so-called Tribonaccis (sequence number \underline{A000073} in Sloane’s Encyclopedia of Integer Sequences), followed by the Tetranaccis (\underline{A000078}) for k = 4, and so on. According to Kessler and Schiff [6], these numbers also appear in probability theory and in certain sorting algorithms. We present here a chart of these numbers for the first few values of k:

k name  first few non-zero terms
2 Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, …
3 Tribonacci 1, 1, 2, 4, 7, 13, 24, 44, 81, …
4 Tetranacci 1, 1, 2, 4, 8, 15, 29, 56, 108, …
5 Pentanacci 1, 1, 2, 4, 8, 16, 31, 61, 120, …

We remind the reader of the famous Binet formula (also known as the de Moivre formula) that can be used to calculate F_{n}, the Fibonacci numbers:

F_{n} = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{n} − (\frac{1 − \sqrt{5}}{2})^{n}]

= \frac{α^{n} − β^{n}}{α − β}

for α > β the two roots of x^{2} − x − 1 = 0. For our purposes, it is convenient (and not particularly difficult) to rewrite this formula as follows:

F_{n} = \frac{α − 1}{2 + 3(α − 2)}α^{n−1} + \frac{β − 1}{2 + 3(β − 2)}β^{n−1}  (1)

We leave the details to the reader.

Our first (and very minor) result is the following representation of F_{n}^{(k)}:

Theorem 1. For F_{n}^{(k)} the nth k-generalized Fibonacci number, then

F_{n}^{(k)} = ∑_{i=1}^{k} \frac{α_{i} − 1}{2 + (k + 1)(α_{i} − 2)}α_{i}^{n−1}  (2)

for α_{1}, …, α_{k} the roots of x^{k} − x^{k−1} − ⋯ − 1 = 0.

This is a new presentation, but hardly a new result. There are many other ways of representing these k-generalized Fibonacci numbers, as seen in the articles [2, 3, 4, 5, 7, 8, 9]. Our Eq. (2) of Theorem 1 is perhaps slightly easier to understand, and it also allows us to do some analysis (as seen below). We point out that for k = 2, Eq. (2) reduces to the variant of the Binet formula (for the standard Fibonacci numbers) from Eq. (1).

As shown in three distinct proofs [9, 10, 13], the equation x^{k} − x^{k−1} − ⋯ − 1 = 0 from Theorem 1 has just one root α such that |α| > 1, and the other roots are strictly inside the unit circle. We can conclude that the contribution of the other roots in Eq. 2 will quickly become trivial, and thus:

F_{n}^{(k)} ≈ \frac{α − 1}{2 + (k + 1)(α − 2)}α^{n−1} for n sufficiently large.  (3)

It’s well known that for the Fibonacci sequence F_{n}^{(2)} = F_{n}, the “sufficiently large” n in Eq. (3) is n = 0, as shown here:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ F_{n} & 0 & 1 & 1 & 2 & 3 & 5 & 8 \\ \frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})n & 0.447 & 0.724 & 1.171 & 1.894 & 3.065 & 4.960 & 8.025 \\ |error| & .447 & .277 & .171 & .106 & .065 & .040 & .025 \end{matrix}

It is perhaps surprising to discover that a similar statement holds for all the k-generalized Fibonacci numbers. Let’s first define rnd(x) to be the the value of x rounded to the nearest integer: rnd(x) = ⌊x + \frac{1}{2}⌋. Then, our main result is the following:

Theorem 2. For F_{n}^{(k)} the nth k-generalized Fibonacci number, then

F_{n}^{(k)} = rnd (\frac{α − 1}{2 + (k + 1)(α − 2)}α^{n−1})

for all n ≥ 2 − k and for α the unique positive root of x^{k} − x^{k−1} − ⋯ − 1 = 0.

We point out that this theorem is not as trivial as one might think. Note the error term for the generalized Fibonacci numbers of order k = 6, as seen in the following chart; it is not monotone decreasing in absolute value.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ F_{n}^{(6)} & 0 & 1 & 1 & 2 & 4 & 8 & 16 & 32 \\ \frac{α−1}{2+7(α−2)}α^{5} & 0.263 & 0.522 & 1.035 & 2.053 & 4.072 & 8.078 & 16.023 & 31.782 \\ |error| & .263 & .478 & .035 & .053 & .072 & .078 & .023 & .218 \end{matrix}

We also point out that not every recurrence sequence admits such a simple formula as seen in Theorem 2. Consider, for example, the scaled Fibonacci sequence 10, 10, 20, 30, 50, 80, …, which has Binet formula:

\frac{10}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n} − \frac{10}{\sqrt{5}} (\frac{1 − \sqrt{5}}{2})^{n} .

This can be written as rnd (\frac{10}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^{n}), but only for n ≥ 5. As another example, the sequence 1, 2, 8, 24, 80, … (defined by G_{n} = 2G_{n−1} + 4G_{n−2}) can be written as

G_{n} = \frac{(1 + \sqrt{5})^{n}}{2\sqrt{5}} − \frac{(1 − \sqrt{5})^{n}}{2\sqrt{5}} ,

but because both 1 + \sqrt{5} and 1 − \sqrt{5} have absolute value greater than 1, then it would be impossible to express G_{n} in terms of just one of these two numbers.

2 Previous Results

We point out that for k = 3 (the Tribonacci numbers), our Theorem 2 was found earlier by Spickerman [11]. His formula (modified slightly to match our notation) reads as follows, where α is the real root, and σ and \overline{σ} are the two complex roots, of x^{3} − x^{2} − x − 1 = 0:

F_{n}^{(3)} = rnd (\frac{α^{2}}{(α − σ)(α − \overline{σ})}α^{n−1})  (4)

It is not hard to show that for k = 3, our coefficient \frac{α−1}{2+(k+1)(α−2)} from Theorem 2 is equal to Spickerman’s coefficient \frac{α^{2}}{(α−σ)(α−\overline{σ})}. We leave the details to the reader.

In a subsequent article [12], Spickerman and Joyner developed a more complex version of our Theorem 1 to represent the generalized Fibonacci numbers. Using our notation, and with {α_{i}} the set of roots of x^{k} − x^{k−1} − ⋯ − 1 = 0, their formula reads

F_{n}^{(k)} = ∑_{i=1}^{k} \frac{α_{i}^{k+1} − α_{i}^{k}}{2α_{i}^{k} − (k + 1)}α_{i}^{n−1}  (5)

It is surprising that even after calculating out the appropriate constants in their Eq. (5) for 2 ≤ k ≤ 10, neither Spickerman nor Joyner noted that they could have simply taken the first term in Eq. (5) for all n ≥ 0, as Spickerman did in Eq. (4) for k = 3.

The Spickerman-Joyner Eq. (5) was extended by Wolfram [13] to the case with arbitrary starting conditions (rather than the initial sequence 0, 0, …, 0, 1). In the next section we will show that our Eq. (2) in Theorem 1 is equivalent to the Spickerman-Joyner formula given above (and thus is a special case of Wolfram’s formula).

Finally, we note that the polynomials x^{k} − x^{k−1} − ⋯ − 1 in Theorem 1 have been studied rather extensively. They are irreducible polynomials with just one zero outside the unit circle. That single zero is located between 2(1−2^{−k}) and 2 (as seen in Wolfram’s article [13]; Miles [9] gave earlier and less precise results). It is also known [13, Lemma 3.11] that the polynomials have Galois group S_{k} for k ≤ 11; in particular, their zeros can not be expressed in radicals for 5 ≤ k ≤ 11. Wolfram conjectured that the Galois group is always S_{k}. Cipu and Luca [1] were able to show that the Galois group is not contained in the alternating group A_{k}, and for k ≥ 3 it is not 2-nilpotent. They point out that this means the zeros of the polynomials x^{k} − x^{k−1} − ⋯ − 1 for k ≥ 3 can not be constructed by ruler and compass, but the question of whether they are expressible using radicals remains open for k ≥ 12.

3 Preliminary Lemmas

First, a few statements about the the number α.

Lemma 3. Let α > 1 be the real positive root of x^{k} − x^{k−1} − ⋯ − x − 1 = 0. Then,

2 − \frac{1}{k} < α < 2  (6)

In addition,

2 − \frac{1}{3k} < α < 2  for k ≥ 4.  (7)

Proof. We begin by computing the following chart for k ≤ 5:

\begin{matrix}k & 2 − \frac{1}{k} & 2 − \frac{1}{3k} & α \\ 2 & 1.5 & 1.833 … & 1.618 … \\ 3 & 1.666 … & 1.889 … & 1.839 … \\ 4 & 1.75 & 1.916 … & 1.928 … \\ 5 & 1.8 & 1.933 … & 1.966 … \end{matrix}

It’s clear that 2− \frac{1}{k} < α < 2 for 2 ≤ k ≤ 5 and that 2− \frac{1}{3k} < α < 2 for 4 ≤ k ≤ 5. We now focus on k ≥ 6. At this point, we could finish the proof by appealing to 2(1 − 2^{−k}) < α < 2 as seen in the article [13, Lemma 3.6], but here we present a simpler proof.

Let f(x) = (x − 1)(x^{k} − x^{k−1} − ⋯ − x − 1) = x^{k+1} − 2x^{k} + 1. We know from our earlier discussion that f(x) has one real zero α > 1. Writing f(x) as x^{k}(x − 2) + 1, we have

f (2 − \frac{1}{3k} ) = (2 − \frac{1}{3k} )^{k} (\frac{−1}{3k}) + 1  (8)

For k ≥ 6, it’s easy to show

3k < (\frac{5}{3})^{k} = (2 − \frac{1}{3})^{k} < (2 − \frac{1}{3k} )^{k}

Substituting this inequality into the right-hand side of (8), we can re-write (8) as

f (2 − \frac{1}{3k} ) < (3k) · (\frac{−1}{3k}) + 1 = 0.

Finally, we note that

f(2) = 2^{k+1} − 2 · 2^{k} + 1 = 1 > 0,

so we can conclude that our root α is within the desired bounds of 2 − 1/3k and 2 for k ≥ 6.

We now have a lemma about the coefficients of α^{n−1} in Theorems 1 and 2.

Lemma 4. Let k ≥ 2 be an integer, and let m^{(k)}(x) = \frac{x − 1}{2 + (k + 1)(x − 2)}. Then,

1. m^{(k)}(2 − 1/k) = 1.

2. m^{(k)}(2) = \frac{1}{2}.

3. m^{(k)}(x) is continuous and decreasing on the interval [2 − 1/k, ∞).

4. m^{(k)}(x) > \frac{1}{x} on the interval (2 − 1/k, 2).

Proof. Parts 1 and 2 are immediate. As for 3, note that we can rewrite m^{(k)}(x) as

m^{(k)}(x) = \frac{1}{k + 1} (1 + \frac{1 − \frac{2}{k+1}}{x − (2 − \frac{2}{k+1})})

which is simply a scaled translation of the map y = 1/x. In particular, since this m^{(k)}(x) has a vertical asymptote at x = 2 − \frac{2}{k+1}, then by parts 1 and 2 we can conclude that m^{(k)}(x) is indeed continuous and decreasing on the desired interval.

To show part 4, we first note that in solving \frac{1}{x} = m^{(k)}(x), we obtain a quadratic equation with the two intersection points x = 2 and x = k. It’s easy to show that \frac{1}{x} < m^{(k)}(x) at x = 2 − 1/k, and since both functions \frac{1}{x} and m^{(k)}(x) are continuous on the interval [2 − 1/k, ∞) and intersect only at x = 2 and x = k ≥ 2, we can conclude that \frac{1}{x} < m^{(k)}(x) on the desired interval.

Lemma 5. For a fixed value of k ≥ 2 and for n ≥ 2 − k, define E_{n} to be the error in our Binet approximation of Theorem 2, as follows:

E_{n} = F_{n}^{(k)} − \frac{α − 1}{2 + (k + 1)(α − 2)} · α^{n−1}
= F_{n}^{(k)} − m^{(k)}(α) · α^{n−1},

for α the positive real root of x^{k} − x^{k−1} − ⋯ − x − 1 = 0 and m^{(k)} as defined in Lemma 4. Then, E_{n} satisfies the same recurrence relation as F_{n}^{(k)}:

E_{n} = E_{n−1} + E_{n−2} + ⋯ + E_{n−k} (for n ≥ 2).

Proof. By definition, we know that F_{n}^{(k)} satisfies the recurrence relation:

F_{n}^{(k)} = F_{n−1}^{(k)} + ⋯ + F_{n−k}^{(k)}  (9)

As for the term m^{(k)}(α) · α^{n−1}, note that α is a root of x^{k} − x^{k−1} − ⋯ − 1 = 0, which means that α^{k} = α^{k−1} + ⋯ + 1, which implies

m^{(k)}(α) · α^{n−1} = m^{(k)}(α)α^{n−2} + ⋯ + m^{(k)}(α)α^{n−(k+1)}  (10)

We combine Equations (9) and (10) to obtain the desired result.

4 Proof of Theorem 1

As mentioned above, Spickerman and Joyner [12] proved the following formula for the kgeneralized Fibonacci numbers:

F_{n}^{(k)} = ∑_{i=1}^{k} \frac{α_{i}^{k+1} − α_{i}^{k}}{2α_{i}^{k} − (k + 1)}α_{i}^{n−1}  (11)

Recall that the set {α_{i}} is the set of roots of x^{k} − x^{k−1} − ⋯ − 1 = 0. We now show that this formula is equivalent to our Eq. (2) in Theorem 1:

F_{n}^{(k)} = ∑_{i=1}^{k} \frac{α_{i} − 1}{2 + (k + 1)(α_{i} − 2)}α_{i}^{n−1}  (12)

Since α_{i}^{k} − α_{i}^{k−1} − ⋯ − 1 = 0, we can multiply by α_{i} − 1 to get α_{i}^{k+1} − 2α_{i}^{k} = −1, which implies (α_{i} − 2) = −1 · α_{i}^{−k}. We use this last equation to transform (12) as follows:

\frac{α_{i} − 1}{2 + (k + 1)(α_{i} − 2)} = \frac{α_{i} − 1}{2 + (k + 1)(−α_{i}^{−k})} = \frac{α_{i}^{k+1} − α_{i}^{k}}{2α_{i}^{k} − (k + 1)}

This establishes the equivalence of the two formulas (11) and (12), as desired. □

5 Proof of Theorem 2

Let E_{n} be as defined in Lemma 5. We wish to show that |E_{n}| < \frac{1}{2} for all n ≥ 2 − k. We proceed by first showing that |E_{n}| < \frac{1}{2} for n = 0, then for n = −1, −2, −3, …, 2 − k, then for n = 1, and finally that this implies |E_{n}| < \frac{1}{2} for all n ≥ 2 − k.

To begin, we note that since our initial conditions give us that F_{n}^{(k)} = 0 for n = 0, −1, −2, …, 2 − k, then we need only show |m^{(k)}(α) · α^{n−1}| < 1/2 for those values of n. Starting with n = 0, it’s easy to check by hand that m^{(k)}(α) · α^{−1} < 1/2 for k = 2 and 3, and as for k ≥ 4, we have the following inequality from Lemma 3:

2 − \frac{1}{3k} < α,

which implies

α^{−1} < \frac{3k}{6k − 1}.

Also, by Lemma 4,

m^{(k)}(α) < m^{(k)}(2 − 1/3k) = \frac{3k − 1}{5k − 1},

so thus:

m^{(k)}(α) · α^{−1} < \frac{3k − 1}{5k − 1} · \frac{3k}{6k − 1} < \frac{(3k) · 1}{(5k − 1) · 2} < \frac{1}{2},

as desired. Thus, 0 < |m^{(k)}(α) · α^{−1}| < 1/2 for all k, as desired.

Since α^{−1} < 1, we can conclude that for n = −1, −2, …, 2 − k, then |E_{n}| = m^{(k)}(α) · α^{n−1} < 1/2.

Turning our attention now to E_{1}, we note that F_{1}^{(k)} = 1 (again by definition of our initial conditions) and that

\frac{1}{2} = m(2) < m(α) < m(2 − 1/k) = 1

which immediately gives us |E_{1}| < 1/2.

As for E_{n} with n ≥ 2, we know from Lemma 5 that

E_{n} = E_{n−1} + E_{n−2} + ⋯ + E_{n−k} (for n ≥ 2)

Suppose for some n ≥ 2 that |E_{n}| ≥ 1/2. Let n_{0} be the smallest positive such n. Now, subtracting the following two equations:

E_{n_{0}+1} = E_{n_{0}} + E_{n_{0}−1} + ⋯ + E_{n_{0}−(k−1)}
E_{n_{0}} = E_{n_{0}−1} + E_{n_{0}−2} + ⋯ + E_{n_{0}−k}

gives us:

E_{n_{0}+1} = 2E_{n_{0}} − E_{n_{0}−k}

Since |E_{n_{0}}| ≥ |E_{n_{0}−k}| (the first, by assumption, being larger than, and the second smaller than, 1/2), we can conclude that |E_{n_{0}+1}| > |E_{n_{0}}|. In fact, we can apply this argument repeatedly to show that |E_{n_{0}+i}| > ⋯ > |E_{n_{0}+1}| > |E_{n_{0}}|. However, this contradicts the observation from Eq. (3) that the error must eventually go to 0. We conclude that |E_{n}| < 1/2 for all n ≥ 2, and thus for all n ≥ 2 − k. □

6 Acknowledgement

The first author would like to thank J. Siehler for inspiring this paper with his work on Tribonacci numbers.

References

[1] M. Cipu and F. Luca, On the Galois group of the generalized Fibonacci polynomial, An. Ştiinţ. Univ. Ovidius Constanţa Ser. Mat. 9 (2001), 27–38.

[2] David E. Ferguson, An expression for generalized Fibonacci numbers, Fibonacci Quart. 4 (1966), 270–273.

[3] I. Flores, Direct calculation of k-generalized Fibonacci numbers, Fibonacci Quart. 5 (1967), 259–266.

[4] Hyman Gabai, Generalized Fibonacci k-sequences, Fibonacci Quart. 8 (1970), 31–38.

[5] Dan Kalman, Generalized Fibonacci numbers by matrix methods, Fibonacci Quart. 20 (1982), 73–76.

[6] David Kessler and Jeremy Schiff, A combinatoric proof and generalization of Ferguson’s formula for k-generalized Fibonacci numbers, Fibonacci Quart. 42 (2004), 266–273.

[7] Gwang-Yeon Lee, Sang-Gu Lee, Jin-Soo Kim, and Hang-Kyun Shin, The Binet formula and representations of k-generalized Fibonacci numbers, Fibonacci Quart. 39 (2001), 158–164.

[8] Claude Levesque, On mth order linear recurrences, Fibonacci Quart. 23 (1985), 290– 293.

[9] E. P. Miles, Jr., Generalized Fibonacci numbers and associated matrices, Amer. Math. Monthly 67 (1960), 745–752.

[10] M. D. Miller, On generalized Fibonacci numbers, Amer. Math. Monthly 78 (1971), 1108–1109.

[11] W. R. Spickerman, Binet’s formula for the Tribonacci sequence, Fibonacci Quart. 20 (1982), 118–120.

[12] W. R. Spickerman and R. N. Joyner, Binet’s formula for the recursive sequence of order k, Fibonacci Quart. 22 (1984), 327–331.

[13] D. A. Wolfram, Solving generalized Fibonacci recurrences, Fibonacci Quart. 36 (1998), 129–145.

2000 Mathematics Subject Classification: Primary 11B39, Secondary 11C08, 33F05, 65D20. Keywords: k-generalized Fibonacci numbers, Binet form, Tribonacci number, Tetranacci number, Pentanacci number.

(Concerned with sequences \underline{A000073}, \underline{A000078}, and \underline{A001591}.)

Received October 15 2008; revised versions received February 19 2014; February 23 2014. Published in Journal of Integer Sequences, February 26 2014.

Return to Journal of Integer Sequences home page.