On Fibonacci Numbers and Their Friends
By Titus Piezas III
Summary: We provide a simple, general method to find exact and approximate formulas for the kth Fibonacci n-step number and the kth Lucas n-step number.
Keywords: Fibonacci numbers, tribonacci, tetranacci, pentanacci, Lucas numbers, recurrence relations.
Contents:
I. Introduction
II. Formulas For Fibonacci n-step Numbers
III. Formulas For Lucas n-step Numbers
IV. Conclusion
What is so special about the Fibonacci numbers, the sequence of numbers {1,1,2,3,5,8,13,21,34…}? As one can see, it is the sequence defined such that, a) starting with 1, each succeeding number is b) the sum of the two numbers preceding it.
They were named after Leonardo Fibonacci (1170-1250) who introduced them in his book Liber Abaci (1202) in the context of, of all things, breeding rabbits. As a side note, Fibonacci was also the man who, in the same book, promoted the use of Hindu-Arabic numerals in the Western world, leading to the present-day ease of using a positional numeral system which involves only ten symbols. Try multiplying the Roman numerals (CMLXIII)*(CCXLVII) and you will appreciate his insight.
Fibonacci numbers appear in seemingly unrelated mathematical contexts, such as in Pascal’s triangle, polynomial sequences, and even in solvable quintics. See “On A Connection Between Solvable Quintics And Fibonacci Numbers” by the same author. It also has an intimate connection to the golden ratio f = (1+Ö5)/2 = 1.61803… the continued fraction of which has a beautiful q-analogue continued fraction mentioned by Ramanujan in his first letter to Hardy.
We can generalize the concept of Fibonacci numbers. There are two ways we can do so, basing on the italicized phrases a) and b) in the first paragraph: First, we can change the initial value without changing the second term v2 = 1, and second, we can change the recurrence relation or the number of terms that need to be added.
For the first way, there is already a well-established companion to the Fibonacci numbers, namely the Lucas numbers, a sequence that has the same recurrence relation as the former but with the different initial value of {2} leading to the sequence {2,1,3,4,7,11…}. We can arbitrarily limit ourselves to these two sequences and find further generalizations in terms of changing their recurrence relations. Thus, we have the “Fibonacci n-step numbers”, with initial value v =1, and where n refers to the number of preceding terms that must be added to produce the next term. For n = 2, we have the usual Fibonacci numbers. For n > 2, we have the tribonacci, tetranacci, pentanacci, etc. These numbers have an interpretation in terms of probabilities involved in n coin tosses. See http://mathworld.wolfram.com/Fibonacci-StepNumber.html for more details.
However, we can also have the “Lucas n-step numbers”, analogous to the above, but with initial value v = 2. For the usual Lucas numbers, of course, n = 2 and these numbers also have a combinatorial interpretation. Whether the Lucas n-step numbers for other n have combinatorial or probability interpretations remains to be seen.
We shall see that we can easily find formulas, both exact and approximate formulas, that will enable us to find the kth Fibonacci n-step or Lucas n-step number, for any step n.
The limit of the ratio of consecutive Fibonacci n-step terms Fk and Fk+1, or limk Fk+1/Fk as k ® ¥ is given by the simple equation,
xn(2-x) = 1
Thus, for the traditional Fibonacci numbers with n = 2, we have,
x2(2-x) = 1
or,
(x-1)(x2-x-1) = 0
disregarding the spurious factor x-1.
A. Fibonacci {1,1,2,3,5,8,13,21,34,55…}
Given the equation,
x2-x-1=0
where,
x1 = (1+Ö5)/2; x2 = (1-Ö5)/2
and the system of equations,
r1x1+r2x2 = 1
r1x12+r2x22 = 1
We find that,
r1 = 1/Ö5; r2 = -1/Ö5
or, forming its defining equation,
5(r-r1)(r-r2) = 5r2-1 = 0
We can call the equation in x as the Fibonacci limit equation and the equation in r as the Fibonacci auxiliary equation. For the latter equation, we will find that it is not only the Fibonacci numbers that have such an equation but also the other n-step sequences.
Hence, the exact formula for the kth Fibonacci number is given by,
Fk = r1x1k + r2x2k
Or,
Fk = (x1k – x2k) /Ö5
also known as Binet’s Fibonacci number formula.
The approximate formula is given by,
Fk = Nint [r xk]
where x = (1+Ö5)/2, r = 1/Ö5, and Nint is the nearest integer function, or simply, rounding a real number to the nearest integer.
Example for approximate formula. For k = 1-6,
{0.72, 1.17, 1.89, 3.06, 4.95, 8.02}
or to the nearest integer, {1,1,2,3,5,8}.
We will find that the exact and approximate formulas for the other Fibonacci n-step numbers will be analogous to these formulas.
B. Tribonacci {1,1,2,4,7,13,24,44,81,149…}
For n = 3, these numbers have been given the quaint name of tribonacci numbers. To find the formulas, both exact and approximate, for the kth tribonacci number, we’ll use the same approach used earlier.
Given the limit equation,
x3(2-x) = 1
or,
(x-1)(x3-x2-x-1) = 0
so,
x3-x2-x-1=0
and labeling the roots xi with their approximate values,
x1 = 1.83929…
x2 = -0.4196-0.6062 I
x3 = -0.4196+0.6062 I
and the system of equations,
r1x1+ r2x2 + r3x3 = 1
r1x12+ r2x22 + r3x32 = 1
r1x13+ r2x23 + r3x33 = 2
we have,
r1 = 0.336228…
r2 = -0.1681 + 0.1983 I
r3 = -0.1681 - 0.1983 I
and to find the coefficients of the tribonacci auxiliary equation,
44(r-r1)(r-r2)(r-r3) = 44r3-2r-1 = 0
So the exact formula for the kth tribonacci number is given by,
Fk = r1x1k + r2x2k + r3x3k
while the approximate formula is,
Fk = Nint [r xk]
where x is the real root of the tribonacci limit equation, x = 1.83929…and r is the real root of the tribonacci auxiliary equation, r = 0.336228…
Example for approximate formula. For k = 1-6,
{0.61, 1.13, 2.09, 3.84, 7.07, 13.01}
or to the nearest integer, {1,1,2,4,7,13}.
This approximate formula we derived here for the kth tribonacci number is identical to the one found by S. Plouffe using the LLL algorithm. See http://mathworld.wolfram.com/TribonacciNumber.html. In fact, originally I found the auxiliary equations for the Fibonacci n-step numbers for n = 3 to 7 using the integer relations algorithm in http://www.cecm.sfu.ca/projects/IntegerRelations/. However, when I realized there was another approach, it was satisfying to see that the equations found from both methods agreed with each other.
C. Tetranacci {1,1,2,4,8,15,29,56,108,208…}
For n = 4, the sequence was given the name tetranacci numbers, after the Greek tessares, meaning “four” (which, by the way, is the also the root of the word “tessellation”).
Given,
x4-x3-x2-x-1=0
where,
x1 = -0.774804…
x2 = 1.92756…
x3 = -0.07637-0.8147 I
x4 = -0.07637+0.8147 I
and the system of equations,
r1x1 + r2x2 + r3x3 + r4x4 = 1
r1x12 + r2x22 +r3x32 + r4x42 = 1
r1x13 + r2x23 + r3x33 + r4x43= 2
r1x14 + r2x24 + r3x34 + r4x44 = 4
we have,
r1 = -0.192912…
r2 = 0.293813…
r3 = -0.05045 + 0.1696 I
r4 = -0.05045 - 0.1696 I
so,
563(r-r1)(r-r2)(r-r3)(r-r4) = 563r4- 20r2-5r-1= 0
Thus, the exact formula for the kth tetranacci number is given by,
Fk = r1x1k + r2x2k + r3x3k + r4x4k
and the approximate,
Fk = Nint [r xk]
where x is the positive real root of the tetranacci limit equation, x = 1.92756… and r is the positive real root of the tetranacci auxiliary equation, r = 0.293813…
Example for approximate formula. For k = 1-6,
{0.56, 1.09, 2.10, 4.05, 7.81, 15.07}
or to the nearest integer, {1,1,2,4,8,15}.
D. Pentanacci {1,1,2,4,8,16,31,61,120,236…}
Since the convention seems to use Greek prefixes, I figured it would be appropriate to call this sequence the pentanacci numbers.
Given,
x5-x4-x3-x2-x-1=0
where,
x1 = 1.96595…
x2 = -0.6783-0.4585 I
x3 = -0.6783+0.4585 I
x4 = 0.1953-0.8488 I
x5 = 0.1953+0.8488 I
and the system,
r1x1 + r2x2 + r3x3 + r4x4 + r5x5 = 1
r1x12 + r2x22 +r3x32 + r4x42 r5x52 = 1
r1x13 + r2x23 + r3x33 + r4x43 + r5x53 = 2
r1x14 + r2x24 + r3x34 + r4x44 + r5x54 = 4
r1x15 + r2x25 + r3x35 + r4x45 + r5x55 = 8
then,
r1 = 0.273621…
r2 = -0.1285 + 0.0737 I
r3 = -0.1285 - 0.0737 I
r4 = -0.0082 + 0.1314 I
r5 = -0.0082 + 0.1314 I
so,
9584(r-r1)(r-r2)(r-r3)(r-r4)(r-r5) = 9584r5- 300r3- 68r2- 9r-1 = 0
and the exact formula for the kth pentanacci number is given by,
Fk = r1x1k + r2x2k + r3x3k + r4x4k + r5x5k
and the approximate,
Fk = Nint [r xk]
where x = 1.96595… and r = 0.273621…
Example for approximate formula. For k = 1-6,
{0.53, 1.05, 2.07, 4.08, 8.03, 15.79}
or to the nearest integer, {1,1,2,4,8,16}.
We can continue our method for the hexanacci (6-step) but due to space constraints only for the approximate formula,
Fk = Nint [r xk]
where x = 1.98358… and r = 0.263045…
with defining equations,
x6-x5-x4-x3-x2-x-1=0
and,
205937r6-6048r4-1288r3-161r2-14r-1 = 0
and for the heptanacci (7-step),
Fk = Nint [r xk]
where x = 1.99196… and r = 0.257261…
with defining equations,
x7-x6-x5-x4-x3-x2-x-1=0
and,
5390272r7-153664r5-31360r4-3768r3-320r2-20r-1 = 0
…ad infinitum.
Before we go to the Lucas n-step numbers, we can have an overview of the values and equations we have found so far. To recall, the appropriate root x of the limit equations for n = 2 to 7 were,
1.61083, 1.83929, 1.92756, 1.96594, 1.98358, 1.99196
so x is approaching 2 as n ® ¥. What about the root r of the auxiliary equations?
0.447214, 0.336228, 0.293813, 0.273621, 0.263045, 0.257261
It seems to be also converging to some value, though I must say I don’t know what it is. It should be interesting to know. (See update at end of article.) And how about the auxiliary equations themselves?
5r2-1 = 0
44r3-2r-1 = 0
563r4- 20r2-5r-1 = 0
9584r5- 300r3- 68r2- 9r-1 = 0
205937r6-6048r4-1288r3-161r2-14r-1 = 0
5390272r7-153664r5-31360r4-3768r3-320r2-20r-1 = 0
It would be convenient if it had some common form like xn(2-x) = 1 just like the limit equation, though I wasn’t able to find one. I did realize what the leading coefficient (5, 44, 563, 9584, 205937, 5390272…} was. It is the unsigned discriminant of the limit equation! Now why that would suddenly appear as a coefficient in the auxiliary equation makes these numbers ever more wondrous.
III. Formulas For Lucas n-step Numbers
We can use the same approach to find exact and approximate formulas for the kth Lucas n-step numbers, namely, solving a system of k equations in k unknowns using the first k terms and powers of the roots xi of the limit equation to find the roots ri of the auxiliary equation. The limit equation for these sequences is the same, namely, xn(2-x) = 1. However, instead of the initial value of v = 1, what will be used for these sequences is v = 2. In analogy with the previous chapter, perhaps we can call these sequences, for n = 2 and above, as the Lucas numbers (of course), trilucas, tetralucas, pentalucas, hexalucas, and so on.
To spare us from tedium, we will give the exact formula only for the Lucas numbers and only the approximate formula for the other kinds.
A. Lucas Numbers {2,1,3,4,7,11,18,29,47,76…}
Given the equation,
x2-x-1=0
where,
x1 = (1+Ö5)/2; x2 = (1-Ö5)/2
and the system of equations,
r1x1+r2x2 = 2
r1x12+r2x22 = 1
we have,
r1 = (-1+Ö5)/2; r2 = (-1-Ö5)/2
so,
(r-r1)(r-r2) = r2+r-1 = 0
then the exact formula is,
Lk = r1x1k+r2x2k
However, since,
r1x1= ((-1+Ö5)/2) ((1+Ö5)/2) = 1
r2x2= ((-1-Ö5)/2) ((1-Ö5)/2) = 1
Then,
Lk+1 = x1k+x2k
And the approximate formula is,
Lk = Nint [r xk]
or,
Lk+1 = Nint [xk]
for n > 2, where x = (1+Ö5)/2.
(Note: There is a common error that gives these formulas as Lk = x1k+x2k and Lk = Nint[xk], and hence is displaced by one term, though admittedly we are being fussy.)
Example for the approximate formula for k = 1 to 8,
{1, 1.61, 2.61, 4.23, 6.85, 11.09, 17.94, 29.03}
to the nearest integer, {x,x,3,4,7,11,18,29}.
Notice that the approximate formula for the Lucas numbers (as well as for the other Lucas n-step numbers) is unreliable for the first two values of k but progressively becomes better for higher values.
B. Other Lucas n-step Numbers
For the trilucas {2,1,3,6,10,19,35,64,118,217…}, tetralucas {2,1,3,6,12,22,43,83,160,308…}, pentalucas {2,1,3,6,12,24,46,91,179,352…}, and so on, the approximate formula has the common template,
Lk = Nint [r xk]
where x is the positive real root of the limit equation xn(2-x) = 1 (disregarding the spurious factor x-1) and r is the positive real root of the auxiliary equation of degree n given by,
44r3 + 16r- 13 = 0
563r4- 73r2 +52r- 29 = 0
9584r5- 588r3- 464r2 +171r- 61 = 0
205937r6- 12138r4- 3677r3- 2178r2 + 541r- 125 = 0
5390272r7- 313600r5- 102400r4- 15888r3- 9032r2 + 1618r- 253 = 0
ad infinitum, with correct roots (approximate) as 0.489653, 0.435199, 0.408063, 0.39348, 0.385372, respectively. Again, they seem to be converging to some unknown value. And again, the unsigned discriminants of the limit equation are the leading coefficients of the auxiliary equations (other than for the Lucas numbers).
We have presented a simple way to find exact and approximate formulas for the Fibonacci n-step numbers and the Lucas n-step numbers. However, we can discuss some points. First, we have left unanswered some questions: are the roots r of the auxiliary equations for both kinds of n-step numbers actually converging to some value and if so, what is that value?
Second, in this article we didn’t even begin to investigate possible relationships between the two kinds of n-step numbers. There is a plethora of relations between Fibonacci and Lucas numbers. See, for starters, Ron Knott’s excellent webpage http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormulae.html. But how about, say, between the tribonacci and the trilucas numbers, as well as the others? I have observed some tentative connections but didn’t include it here.
Third, the Lucas number sequence is only one possible alternative initial value, namely v = 2 to Fibonacci’s v = 1. Suppose we use other initial values, say, v = 3, and find the whole family of n-step numbers from it. What would be the connections then, if any, between these three n-step families? What would the roots r of the auxiliary equations of this new family converge to, if it does at all?
So many questions. And to think, it just started with rabbits.
(Update Mar 19, 2005)
I realized there was a way to answer several points we raised in the conclusion. The other method to find the terms of the Fibonacci and Lucas n-step numbers is to use generating functions, though this method doesn’t just give you the kth term Fk but all other intermediate terms as well. Since the root r of the auxiliary equation is the limit of the ratio Fk/xk where x is the positive root of the limit equation, then by using suitably large k, we can find the r of the n-step numbers for progressively larger values of n, and we can see if it is converging and to what value.
For the Fibonacci n-step numbers, we stopped at n = 7 with r = 0.257261. For n = 10, 20, 30, we have r as,
{0.251233, 0.2500023, 0.2500000034…}
so indeed it is converging and to the value 0.25 or ¼.
For the Lucas n-step numbers, at n = 7, we had r = 0.385372. For n = 10, 20, 30, r is,
{0.376788, 0.3750035, 0.3750000051…}
so it is also converging and to the value 0.375 or 3/8.
We also pointed out in our conclusion that the Fibonacci and Lucas n-step numbers are just the smallest members of an infinite family of n-step sequences, using initial values v = {1, 2}, respectively, and where the second term remains fixed at v2 = 1. Suppose we use other initial terms? For v = 3, at n = 10, 20, 30, the root r is approximately,
{0.502343, 0.5000046, 0.5000000068…}
converging to ½. For v = 4,
{0.627898, 0.6250057, 0.6250000085…}
converging to 0.625 or 5/8.
It may have been a fruitful experiment. Since r is the limit of the ratio Fk/xk, it seems that as n ® ¥, then r ® (v+1)/8, where n is the number of terms to be added and v is the initial value. At least for these values of v. Whether it is true for all higher v is one more question added to our list.
-- End --
© 2005
Titus Piezas III
Mar. 18, 2005
www.oocities.org/titus_piezas/ ¬ (Click here for an index of papers, articles.)
References