sensagent's content

• definitions
• synonyms
• antonyms
• encyclopedia

Dictionary and translator for handheld

New : sensagent is now available on your handheld

sensagent's office

Shortkey or widget. Free.

Windows Shortkey: . Free.

Vista Widget : . Free.

Webmaster Solution

Alexandria

A windows (pop-into) of information (full-content of Sensagent) triggered by double-clicking any word on your webpage. Give contextual explanation and translation from your sites !

Try here  or   get the code

SensagentBox

With a SensagentBox, visitors to your site can access reliable information on over 5 million pages provided by Sensagent.com. Choose the design that fits your site.

WordGame

The English word games are:
○   Anagrams
○   Wildcard, crossword
○   Lettris
○   Boggle.

Lettris

Lettris is a curious tetris-clone game where all the bricks have the same square shape but different content. Each square carries a letter. To make squares disappear and save space for other squares you have to assemble English words (left, right, up, down) from the falling squares.

boggle

Boggle gives you 3 minutes to find as many words (3 letters or more) as you can in a grid of 16 letters. You can also try the grid of 16 letters. Letters must be adjacent and longer words score better. See if you can get into the grid Hall of Fame !

English dictionary
Main references

Most English definitions are provided by WordNet .
English thesaurus is mainly derived from The Integral Dictionary (TID).
English Encyclopedia is licensed by Wikipedia (GNU).

The wordgames anagrams, crossword, Lettris and Boggle are provided by Memodata.
The web service Alexandria is granted from Memodata for the Ebay search.
The SensagentBox are offered by sensAgent.

Translation

Change the target language to find translations.
Tips: browse the semantic fields (see From ideas to words) in two languages to learn more.

last searches on the dictionary :

6374 online visitors

computed in 0.062s

»

# Generalizations of Fibonacci numbers

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 objects other than numbers.

## Extension to negative integers

Using Fn-2 = Fn - Fn-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)nFn.

## 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

$F_n = \frac{\phi^n-(1-\phi)^n}{\sqrt{5}}.$

The analytic function

$Fe(x) = \frac{\phi^x - \phi^{-x}}{\sqrt{5}}$

has the property that Fe(n) = Fn for even integers n. [1] Similarly, the analytic function:

$Fo(x) = \frac{\phi^x + \phi^{-x}}{\sqrt{5}}$

satisfies Fo(n) = Fn for odd integers n.

Finally, putting these together, the analytic function

$Fib(x) = \frac{\phi^x - \cos(x \pi)\phi^{-x}}{\sqrt{5}}$

satisfies Fib(n)=Fn for all integers n. [2]

This formula can be used to compute the generalized Fibonacci function of a complex variable. For example,

$Fib(3+4i) \approx -5248.5 - 14195.9 i$

## 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

### Fibonacci integer sequences

The 2-dimensional Z-module of Fibonacci integer sequences consists of all integer sequences satisfying g(n+2) = g(n) + g(n+1). Expressed in terms of two initial values we have:

g(n) = F(n)g(1) + F(n-1)g(0) = $g(1){{\varphi^n-(-\varphi)^{-n}} \over {\sqrt 5}}+g(0){{\varphi^{n-1}-(-\varphi)^{1-n}} \over {\sqrt 5}}\, ,$

where $\varphi$ is the golden ratio.

Written in the form

$a\varphi^n+b(-\varphi)^{-n}$

a = 0 if and only if b = 0.

Thus the ratio between two consecutive elements converges to the golden ratio, except in the case of the sequence which is constantly zero.

Written in this form the simplest non-trivial example (a = b = 1) is the sequence of Lucas numbers:

$L_n = \varphi^n + (- \varphi)^{- n}$

We have L(1) = 1 and L(2) = 3. The properties include:

$\varphi^n = \left( \frac 1 2 \left( 1 + \sqrt{5} \right) \right)^n = \frac 1 2 \left( L(n) + F(n) \sqrt{5} \right).$
$L\left(n\right)=F\left(n-1\right)+F\left(n+1\right).\,$

### Lucas sequences

A generalization of the Fibonacci sequence are the Lucas sequences of the kind defined as follows:

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.

### Fibonacci numbers of higher order

A Fibonacci sequence of order n is an integer sequence in which each sequence element is the sum of the previous n elements (with the exception of the first n elements in the sequence). The usual Fibonacci numbers are a Fibonacci sequence of order 2. The cases n=3 and n=4 have been thoroughly investigated. The number of compositions of nonnegative integers into parts that are at most n is a Fibonacci sequence of order n.

#### 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, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, … (sequence A000073 in OEIS)

The tribonacci constant $\frac{1+\sqrt[3]{19+3\sqrt{33}}+\sqrt[3]{19-3\sqrt{33}}}{3}$ is the ratio toward which adjacent tribonacci numbers tend. It is a root of the polynomial x3 − x2 − x − 1, approximately 1.83929 (sequence A058265 in OEIS), 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[3]

$T(n) = \left[ 3 \, b \frac{\left(\frac{1}{3} \left( a_{+} + a_{-} + 1\right)\right)^n}{b^2-2b+4} \right]$

where the outer brackets denote the nearest integer function and

$a_{\pm} = \left(19 \pm 3 \sqrt{33}\right)^{1/3}$
$b = \left(586 + 102 \sqrt{33}\right)^{1/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, … (sequence A000078 in OEIS)

The tetranacci constant is the ratio toward which adjacent tetranacci numbers tend. It is a root of the polynomial x4x3x2x − 1, approximately 1.92756, and also satisfies the equation x + x−4 = 2.

#### Higher orders

Pentanacci, hexanacci, and heptanacci numbers have been computed. The pentanacci numbers are:

0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, … (sequence A001591 in OEIS)

Hexanacci numbers:

0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, … (sequence A001592 in OEIS)

Heptanacci numbers:

0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, … (sequence A122189 in OEIS)

The limit of the ratio of successive terms of an n-nacci series tends to a root of the equation $x+x^{-n}=2\,$

An alternate recursive formula for the limit of ratio r of two consecutive n-nacci numbers can be expressed as $r=\sum_{k=0}^{n-1}r^{-k}$.

The special case n=2 is the traditional Fibonacci series yielding the gold section $\phi=1+\frac{1}{\phi}$.

The above formulas for the ratio hold even for n-nacci series generated from arbitrary numbers. The limit of this ratio is 2 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.

And the kth element of the n-nacci sequence is given by

$F_k^{(n)}=\left[ \frac{r^{k-1} (r-1)}{(n+1)r-2n}\right]$

where the outer brackets denote the nearest integer function and r is the n-nacci constant which is the root of $x+x^{-n}=2$ near to 2.[4]

A Coin Tossing Problem is related to the n-nacci sequence. The probability that no n consecutive tails will occur in m tosses of an idealized coin is $\frac{F_{m+2}^{(n)}}{2^m}$. [5]

## Fibonacci word

In analogy to its numerical counterpart, the Fibonacci word is defined by:

$F_n := F(n):= \begin{cases} b & \mbox{if } n = 0; \\ a & \mbox{if } n = 1; \\ F(n-1)+F(n-2) & \mbox{if } n > 1. \\ \end{cases}$

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.

If "a" and "b" represent two different materials or atomic bond lengths, the structure corresponding to a Fibonacci string is a Fibonacci quasicrystal, an aperiodic quasicrystal structure with unusual spectral properties.

## Other generalizations

The Fibonacci polynomials are another generalization of Fibonacci numbers.

The Padovan sequence is generated by the recurrence P(n) = P(n − 2) + P(n − 3).

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 such 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, … (sequence A007629 in OEIS)

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 $L(n)=2F(n-1)+F(n)$.

## References

1. ^ What is a Fibonacci Number ?
2. ^ Pravin Chandra and Eric W. Weisstein, "Fibonacci Number" from MathWorld.
3. ^ Simon Plouffe, 1993
4. ^ Du, Zhao Hui, 2008
5. ^ Eric W. Weisstein, "Coin Tossing" from MathWorld.