Difference between revisions of "Fibonacci sequence"
(→Binet's formula: moved majority of section to new article) |
|||
Line 1: | Line 1: | ||
{{WotWAnnounce|week=Dec 6-12}} | {{WotWAnnounce|week=Dec 6-12}} | ||
− | The '''Fibonacci sequence''' is a [[sequence]] of [[integer]]s in which the first and second | + | The '''Fibonacci sequence''' is a [[sequence]] of [[integer]]s in which the first and second terms are both equal to 1 and each subsequent term is the sum of the two preceding it. The first few terms are <math>1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...</math>. |
− | The Fibonacci sequence can be written [[recursion|recursively]] as <math>F_n=F_{n-1}+F_{n-2}</math>. There is also an explicit | + | The Fibonacci sequence can be written [[recursion|recursively]] as <math>F_1 = F_2 = 1</math> and <math>F_n=F_{n-1}+F_{n-2}</math> for <math>n \geq 3</math>. This is the simplest nontrivial example of a [[linear recursive sequence with constant coefficients]]. There is also an explicit formula [[#Binet's formula|below]]. |
− | == | + | Readers should be wary: some authors give the Fibonacci sequence with the [[initial condition]]s <math>F_0 = F_1 = 1</math> (or equivalently <math>F_1 = 1, F_2 = 2</math>). This change in [[indexing of a sequence | indexing]] does not affect the actual numbers in the sequence, but it does change which member of the sequence is refered to by the symbol <math>F_n</math> and so also changes the appearance of certain [[identity | identities]] involving the Fibonacci numbers. |
− | + | == Running backwards == | |
+ | As with many [[linear recursion]]s, we can run the Fibonacci sequence backwards by solving its recursion relation for the term of smallest index, in this case <math>F_{n - 2} = F_{n} - F_{n - 1}</math>. This allows us to compute, for example, that <math>F_0 = F_2 - F_1 = 0</math>, <math>F_{-1} = 1</math>, <math>F_{-2} = -2</math>, and so on. Because these preceding terms are uniquely defined by the recursion, one frequently sees the definition of the Fibonacci sequence given in the form <math>F_0 = 0</math>, <math>F_1 = 1</math> and <math>F_n = F_{n - 1} + F_{n - 2}</math> for <math>n \geq 2</math>. In general, one can show that <math>F_n = (-1)^{n+1}F_{-n}</math>. | ||
− | == Binet's formula == | + | == Phi and Binet's formula== |
{{main|Binet's formula}} | {{main|Binet's formula}} | ||
− | + | The ratios <math>\frac{1}{1}</math>, <math>\frac{2}{1}</math>, <math>\frac{3}{2}</math>, <math>\frac{5}{3}</math>, <math>\frac{8}{5}</math>, ..., between successive terms of the sequence tend towards the limit <math>\frac{1 + \sqrt{5}}{2}</math>, a constant often denoted <math>\varphi</math> (the Greek letter [[phi]]). One possible explanation for this fact is that the Fibonacci numbers are given explicitly by ''Binet's formula''. It is | |
− | It is <math>\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)</math>. | + | <math>F_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)</math>. |
+ | (Note that this formula is valid for all integers <math>n</math>.) | ||
+ | It is so named because it was derived by mathematician Jacques Philippe Marie Binet, though it was already known by Abraham de Moivre. | ||
− | + | == Identities == | |
==Problems== | ==Problems== | ||
Line 33: | Line 36: | ||
==See also== | ==See also== | ||
* [[Combinatorics]] | * [[Combinatorics]] | ||
+ | * [[Lucas number]] | ||
{{stub}} | {{stub}} |
Revision as of 10:44, 8 December 2007
This is an AoPSWiki Word of the Week for Dec 6-12 |
The Fibonacci sequence is a sequence of integers in which the first and second terms are both equal to 1 and each subsequent term is the sum of the two preceding it. The first few terms are .
The Fibonacci sequence can be written recursively as and for . This is the simplest nontrivial example of a linear recursive sequence with constant coefficients. There is also an explicit formula below.
Readers should be wary: some authors give the Fibonacci sequence with the initial conditions (or equivalently ). This change in indexing does not affect the actual numbers in the sequence, but it does change which member of the sequence is refered to by the symbol and so also changes the appearance of certain identities involving the Fibonacci numbers.
Contents
[hide]Running backwards
As with many linear recursions, we can run the Fibonacci sequence backwards by solving its recursion relation for the term of smallest index, in this case . This allows us to compute, for example, that , , , and so on. Because these preceding terms are uniquely defined by the recursion, one frequently sees the definition of the Fibonacci sequence given in the form , and for . In general, one can show that .
Phi and Binet's formula
- Main article: Binet's formula
The ratios , , , , , ..., between successive terms of the sequence tend towards the limit , a constant often denoted (the Greek letter phi). One possible explanation for this fact is that the Fibonacci numbers are given explicitly by Binet's formula. It is . (Note that this formula is valid for all integers .) It is so named because it was derived by mathematician Jacques Philippe Marie Binet, though it was already known by Abraham de Moivre.
Identities
Problems
Introductory
- The Fibonacci sequence starts with two 1s, and each term afterwards is the sum of its two predecessors. Which one of the ten digits is the last to appear in the units position of a number in the Fibonacci sequence?
- Find .
Intermediate
- Seven line segments, with lengths no greater than 10 inches, and no shorter than 1 inch, are given. Show that one can choose three of them to represent the sides of a triangle. (Manhattan Mathematical Olympiad 2004)
- Except for the first two terms, each term of the sequence is obtained by subtracting the preceding term from the one before that. The last term of the sequence is the first negative term encounted. What positive integer produces a sequence of maximum length?
- A fair coin is to be tossed times. Let , in lowest terms, be the probability that heads never occur on consecutive tosses. Find .
- Find if and are integers such that is a factor of .
Olympiad
- Determine the maximum value of , where and are integers satisfying and .
See also
This article is a stub. Help us out by expanding it.