العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolGENERALIZATIONS OF FIBONACCI NUMBERS
(Redirected from Tetranacci number)
In mathematics, the Fibonacci numbers form a sequence defined recursively by:
:''F''(0) = 0
:''F''(1) = 1
:''F''(''n'') = ''F''(''n''-1) + ''F''(''n''-2), for integer ''n'' > 1
That is, after two starting values, each number is the sum of the two preceding numbers.
The Fibonacci sequence has been studied extensively and generalized in many ways. For example by starting with other numbers than 0 and 1, by adding more than two numbers to generate the next number, or by adding other objects than numbers.
Using ''F''''n''-2 = ''Fn'' - ''F''''n''-1, one can extend the Fibonacci numbers to negative integers. So we get: ... -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ... and ''F-n'' = -(-1)''n''''Fn''.
There are a number of possible generalizations of the Fibonacci numbers which include the real numbers (and sometimes the complex numbers) in their domain. These each involve the golden ratio φ, and are based on Binet's formula
:
The analytic function
:
has the property that ''Fe''(''n'') = ''F''n for even integers ''n''. [1] Similarly, the analytic function:
:
satisfies ''Fo''(''n'') = ''F''n for odd integers ''n''.
Finally, putting these together, the analytic function
:
satisfies ''Fib''(''n'')=''F''n for all integers ''n''. [2]
This formula can be used to compute the generalized Fibonacci function of a complex variable. For example,
:
The term ''Fibonacci sequence'' is also applied more generally to any function ''g'' from the integers to a field for which ''g''(''n''+2) = ''g''(''n'') + ''g''(''n''+1). These functions are precisely those of the form ''g''(''n'') = ''F''(''n'')''g''(1) + ''F''(''n''-1)''g''(0), so the Fibonacci sequences form a vector space with the functions ''F''(''n'') and ''F''(''n''-1) as a basis.
More generally, the range of ''g'' may be taken to be any abelian group (regarded as a Z-module). Then the Fibonacci sequences form a 2-dimensional Z-module in the same way.
In particular, the Fibonacci sequence ''L'' with ''L''(1) = 1 and ''L''(2) = 3 is referred to as the 'Lucas numbers', after Edouard Lucas. This sequence was described by Leonhard Euler in 1748, in the ''Introductio in Analysin Infinitorum''. The significance in the Lucas numbers ''L(n)'' lies in the fact that raising the golden ratio to the ''n''th power yields
:
Lucas numbers are related to Fibonacci numbers by the relation
:
A generalization of the Fibonacci sequence are the Lucas sequences. One kind can be defined thus:
: ''U''(0) = 0
: ''U''(1) = 1
: ''U''(''n'' + 2) = ''PU''(''n'' + 1) − ''QU''(''n'')
where the normal Fibonacci sequence is the special case of ''P'' = 1 and ''Q'' = −1. Another kind of Lucas sequence begins with ''V''(0) = 2, ''V''(1) = ''P''. Such sequences have applications in number theory and primality proving.
The Padovan sequence is generated by the recurrence ''P''(''n'') = ''P''(''n'' − 2) + ''P''(''n'' − 3).
The 'tribonacci numbers' are like the Fibonacci numbers, but instead of starting with two predetermined terms, the sequence starts with three predetermined terms and each term afterwards is the sum of the preceding three terms. The first few tribonacci numbers are :
:0 (number), 0 (number), 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, …
The 'tribonacci constant' is the ratio toward which adjacent tribonacci numbers tend. It is a root of the polynomial ''x''3 − ''x''2 − ''x'' − 1, approximately 1.83929, and also satisfies the equation ''x'' + ''x''−3 = 2. It is important in the study of the snub cube.
The tribonacci numbers are also given by
:
where the outer brackets denote the nearest integer function and
:
:. [3]
The 'tetranacci numbers' start with four predetermined terms, each term afterwards being the sum of the preceding four terms. The first few tetranacci numbers are :
:0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, …
The 'tetranacci constant' is the ratio toward which adjacent tetranacci numbers tend. It is a root of the polynomial ''x''4 − ''x''3 − ''x''2 − ''x'' − 1, approximately 1.92756, and also satisfies the equation ''x'' + ''x''−4 = 2.
Pentanacci, hexanacci and heptanacci numbers have been computed, with perhaps less interest so far in research.. In the limit, the ratio of successive terms of an ''n''-nacci sequence tends to a root of the equation .
Thus, this has a limit as ''n'' increases. A 'polynacci' sequence, if one could be described, would after an infinite number of zeroes yield the sequence [..., 0, 0, 1,] 1, 2, 4, 8, 16, 32, ... which are simply powers of 2.
In analogy to its numerical counterpart, a 'Fibonacci string' is defined by:
:,
where + denotes the concatenation of two strings. The sequence of Fibonacci strings starts:
:b, a, ab, aba, abaab, abaababa, abaababaabaab, …
The length of each Fibonacci string is a Fibonacci number, and similarly there exists a corresponding Fibonacci string for each Fibonacci number.
Fibonacci strings appear as inputs for the worst case in some computer algorithms.
The Fibonacci polynomials are another generalization of Fibonacci numbers.
A 'random Fibonacci sequence' can be defined by tossing a coin for each position ''n'' of the sequence and taking ''F''(''n'')=''F''(''n''−1)+''F''(''n''−2) if it lands heads and ''F''(''n'')=''F''(''n''−1)−''F''(''n''−2) if it lands tails. Work by Furstenburg and Kesten guarantees that this sequence almost surely grows exponentially at a constant rate: the constant is independent of the coin tosses and was computed in 1999 by Divakar Viswanath. It is now known as Viswanath's constant.
A 'repfigit' or 'Keith number' is an integer, that when its digits start a Fibonacci sequence with that number of digits, the original number is eventually reached. An example is 47, because the Fibonacci sequence starting with 4 and 7 (4,7,11,18,29,47) reaches 47. A repfigit can be a tribonacci sequence if there are 3 digits in the number, a tetranacci number if the number has four digits, etc. The first few repfigits are :
:14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909, …
Since the set of sequences satisfying the relation ''S''(''n'') = ''S''(''n''−1) + ''S''(''n''−2) is closed under termwise addition and under termwise multiplication by a constant, it can be viewed as a vector space. Any such sequence is uniquely determined by a choice of two elements, so the vector space is two-dimensional. If we abbreviate such a sequence as (''S''(0), ''S''(1)), the Fibonacci sequence ''F''(''n'') = (0, 1) and the shifted Fibonacci sequence ''F''(''n''−1) = (1, 0) are seen to form a canonical basis for this space, yielding the identity:
: ''S''(''n'') = ''S''(0)''F''(''n''−1) + ''S''(1)''F''(''n'')
for all such sequences ''S''. For example, if ''S'' is the Lucas sequence 2, 1, 3, 4, 7, 11…, then we obtain .
1. What is a Fibonacci Number ?
2.
3. Simon Plouffe, 1993
In mathematics, the Fibonacci numbers form a sequence defined recursively by:
:''F''(0) = 0
:''F''(1) = 1
:''F''(''n'') = ''F''(''n''-1) + ''F''(''n''-2), for integer ''n'' > 1
That is, after two starting values, each number is the sum of the two preceding numbers.
The Fibonacci sequence has been studied extensively and generalized in many ways. For example by starting with other numbers than 0 and 1, by adding more than two numbers to generate the next number, or by adding other objects than numbers.
Extension to negative integers
Using ''F''''n''-2 = ''Fn'' - ''F''''n''-1, one can extend the Fibonacci numbers to negative integers. So we get: ... -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ... and ''F-n'' = -(-1)''n''''Fn''.
Extension to all real or complex numbers
There are a number of possible generalizations of the Fibonacci numbers which include the real numbers (and sometimes the complex numbers) in their domain. These each involve the golden ratio φ, and are based on Binet's formula
:
The analytic function
:
has the property that ''Fe''(''n'') = ''F''n for even integers ''n''. [1] Similarly, the analytic function:
:
satisfies ''Fo''(''n'') = ''F''n for odd integers ''n''.
Finally, putting these together, the analytic function
:
satisfies ''Fib''(''n'')=''F''n for all integers ''n''. [2]
This formula can be used to compute the generalized Fibonacci function of a complex variable. For example,
:
Vector space
The term ''Fibonacci sequence'' is also applied more generally to any function ''g'' from the integers to a field for which ''g''(''n''+2) = ''g''(''n'') + ''g''(''n''+1). These functions are precisely those of the form ''g''(''n'') = ''F''(''n'')''g''(1) + ''F''(''n''-1)''g''(0), so the Fibonacci sequences form a vector space with the functions ''F''(''n'') and ''F''(''n''-1) as a basis.
More generally, the range of ''g'' may be taken to be any abelian group (regarded as a Z-module). Then the Fibonacci sequences form a 2-dimensional Z-module in the same way.
Similar integer sequences
Lucas numbers
In particular, the Fibonacci sequence ''L'' with ''L''(1) = 1 and ''L''(2) = 3 is referred to as the 'Lucas numbers', after Edouard Lucas. This sequence was described by Leonhard Euler in 1748, in the ''Introductio in Analysin Infinitorum''. The significance in the Lucas numbers ''L(n)'' lies in the fact that raising the golden ratio to the ''n''th power yields
:
Lucas numbers are related to Fibonacci numbers by the relation
:
A generalization of the Fibonacci sequence are the Lucas sequences. One kind can be defined thus:
: ''U''(0) = 0
: ''U''(1) = 1
: ''U''(''n'' + 2) = ''PU''(''n'' + 1) − ''QU''(''n'')
where the normal Fibonacci sequence is the special case of ''P'' = 1 and ''Q'' = −1. Another kind of Lucas sequence begins with ''V''(0) = 2, ''V''(1) = ''P''. Such sequences have applications in number theory and primality proving.
The Padovan sequence is generated by the recurrence ''P''(''n'') = ''P''(''n'' − 2) + ''P''(''n'' − 3).
Tribonacci numbers
The 'tribonacci numbers' are like the Fibonacci numbers, but instead of starting with two predetermined terms, the sequence starts with three predetermined terms and each term afterwards is the sum of the preceding three terms. The first few tribonacci numbers are :
:0 (number), 0 (number), 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, …
The 'tribonacci constant' is the ratio toward which adjacent tribonacci numbers tend. It is a root of the polynomial ''x''3 − ''x''2 − ''x'' − 1, approximately 1.83929, and also satisfies the equation ''x'' + ''x''−3 = 2. It is important in the study of the snub cube.
The tribonacci numbers are also given by
:
where the outer brackets denote the nearest integer function and
:
:. [3]
Tetranacci numbers
The 'tetranacci numbers' start with four predetermined terms, each term afterwards being the sum of the preceding four terms. The first few tetranacci numbers are :
:0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, …
The 'tetranacci constant' is the ratio toward which adjacent tetranacci numbers tend. It is a root of the polynomial ''x''4 − ''x''3 − ''x''2 − ''x'' − 1, approximately 1.92756, and also satisfies the equation ''x'' + ''x''−4 = 2.
Other -nacci numbers
Pentanacci, hexanacci and heptanacci numbers have been computed, with perhaps less interest so far in research.. In the limit, the ratio of successive terms of an ''n''-nacci sequence tends to a root of the equation .
Thus, this has a limit as ''n'' increases. A 'polynacci' sequence, if one could be described, would after an infinite number of zeroes yield the sequence [..., 0, 0, 1,] 1, 2, 4, 8, 16, 32, ... which are simply powers of 2.
Fibonacci strings
In analogy to its numerical counterpart, a 'Fibonacci string' is defined by:
:,
where + denotes the concatenation of two strings. The sequence of Fibonacci strings starts:
:b, a, ab, aba, abaab, abaababa, abaababaabaab, …
The length of each Fibonacci string is a Fibonacci number, and similarly there exists a corresponding Fibonacci string for each Fibonacci number.
Fibonacci strings appear as inputs for the worst case in some computer algorithms.
Other generalizations
The Fibonacci polynomials are another generalization of Fibonacci numbers.
A 'random Fibonacci sequence' can be defined by tossing a coin for each position ''n'' of the sequence and taking ''F''(''n'')=''F''(''n''−1)+''F''(''n''−2) if it lands heads and ''F''(''n'')=''F''(''n''−1)−''F''(''n''−2) if it lands tails. Work by Furstenburg and Kesten guarantees that this sequence almost surely grows exponentially at a constant rate: the constant is independent of the coin tosses and was computed in 1999 by Divakar Viswanath. It is now known as Viswanath's constant.
A 'repfigit' or 'Keith number' is an integer, that when its digits start a Fibonacci sequence with that number of digits, the original number is eventually reached. An example is 47, because the Fibonacci sequence starting with 4 and 7 (4,7,11,18,29,47) reaches 47. A repfigit can be a tribonacci sequence if there are 3 digits in the number, a tetranacci number if the number has four digits, etc. The first few repfigits are :
:14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909, …
Since the set of sequences satisfying the relation ''S''(''n'') = ''S''(''n''−1) + ''S''(''n''−2) is closed under termwise addition and under termwise multiplication by a constant, it can be viewed as a vector space. Any such sequence is uniquely determined by a choice of two elements, so the vector space is two-dimensional. If we abbreviate such a sequence as (''S''(0), ''S''(1)), the Fibonacci sequence ''F''(''n'') = (0, 1) and the shifted Fibonacci sequence ''F''(''n''−1) = (1, 0) are seen to form a canonical basis for this space, yielding the identity:
: ''S''(''n'') = ''S''(0)''F''(''n''−1) + ''S''(1)''F''(''n'')
for all such sequences ''S''. For example, if ''S'' is the Lucas sequence 2, 1, 3, 4, 7, 11…, then we obtain .
References
1. What is a Fibonacci Number ?
2.
3. Simon Plouffe, 1993
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
