Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Fibonacci sequence"

m (→‎Binet's formula)
 
(25 intermediate revisions by 14 users not shown)
Line 1: Line 1:
−
{{WotWAnnounce|week=Dec 6-12}}
+
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''' is a [[sequence]] of [[integer]]s in which the first and second term are both equal to 1, and each subsequent term is the sum of the two preceding it. Often, there is a zero-th term added in equal to 0. The first few terms are <br><math>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...</math>.   
+
==Recursion==
 +
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 recursion]] with constant coefficients.  There is also an explicit formula [[#Binet's formula|below]].
  
−
The Fibonacci sequence can be written [[recursion|recursively]] as <math>F_n=F_{n-1}+F_{n-2}</math>. There is also an explicit definition [[#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 referred to by the symbol <math>F_n</math> and so also changes the appearance of certain [[identity | identities]] involving the Fibonacci numbers.  
  
−
== Phi ==
+
== 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 <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>.
  
−
Ratios between successive terms, <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>, tend towards the limit [[phi]].
+
== <math>\varphi</math>, <math>\psi</math>, and Binet's Formula==
 +
{{main|Binet's formula}}
  
−
== 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]], also written <math>\phi</math>).  <math>\varphi</math> is a solution of the quadratic equation <math>x^2-x-1=0</math>.  The other root is <math>\psi = \frac{1-\sqrt{5}}{2}</math> (the Greek letter [[psi]]). One possible explanation for this fact is that the Fibonacci numbers are given explicitly by Binet's formula. It is <math>F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}</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 and Euler before him. Another explanation is that you can continue the fibonacci numbers backward, too. Then you get something like <math>\dots -8,5,-3,2,-1,1,0,1,1,2,3,5,8\dots</math> . The ratios between successive terms has you continue backwards is <math>\psi</math>.
  
−
'''Binet's formula''' is an explicit formula used to find the <math>n</math>th term of the Fibonacci sequence.
+
==When to use them==
−
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>.
 
  
−
'''Proof''': If we experiment with fairly large numbers, we see that the quotient of consecutive terms of the sequence approach <math>1.618\ldots</math> (see above). Thus we have a sequence resembling that of a [[geometric sequence]], which we let be <math>a \cdot r^n</math>. Then, <math>F_{n+1} = F_n + F_{n-1} \Longrightarrow a \cdot r^{n+1} = a \cdot r^{n} + a \cdot r^{n-1} </math> <math>\Longrightarrow r^2 = r + 1</math>. Using the [[quadratic formula]], we find <math>r = \frac{1 \pm \sqrt{5}}{2}</math>.
+
Usually, fibonacci-like recursions show up when organisms like rabbits produce babies but babies need to grow up which takes time. Two other places are when you make domino tilings in a <math>2\times n</math> rectangle or when you make a string of a's and b's of a fixed length but you can't have 2 a's together. Many things can be turned into either the fibonacci recursion <math>F_n=F_{n-1}+F_{n-2}</math> or another recursion that also produces the fibonacci numbers: <math>a_n=b_{n-1}</math> and <math>b_n=b_{n-1}+a_{n-1}</math>. There are other recursions, but these two are the most frequent.
 +
 
 +
== Identities ==
 +
The most important identity regarding the Fibonacci sequence is its recursive definition, <math>F_{n+1} = F_n + F_{n-1}</math>. The following identities involving the Fibonacci numbers can be proved by [[induction]].
 +
 
 +
*<math>F_0 + F_1 + \cdots + F_{n} = F_{n+2} - 1</math>
 +
*<math>F_0 - F_1 + F_2 - \cdots - F_{2n-1} + F_{2n} = F_{2n-1} - 1</math>
 +
*<math>F_0^2 + F_1^2 + F_2^2 + \cdots + F_n^2 = F_n \cdot F_{n+1}</math>
 +
*<math>F_{n-1}\cdot F_{n+1} = F_{n}^2 + (-1)^n</math>
 +
*<math>F_{m+n+1} = F_{m+1} \cdot F_{n+1} + F_{m} \cdot F_n</math>
  
−
We now have two sequences <math>G_n = a \left(\frac{1 + \sqrt{5}}{2}\right)^n</math> and <math>H_n = a \left(\frac{1 - \sqrt{5}}{2}\right)^n</math>, but neither match up with the Fibonacci sequence. In particular, <math>F_0 = 0</math>, but for <math>G_0, H_0</math> to be zero, we need <math>a = 0</math>, but then the sequence just generates a constant <math>0</math>. After a bit of experimenting with these two sequences to find a sequence where the zeroth term being zero, notice that <math>G_{n+1} - H_{n+1} = G_{n} - H_{n} + G_{n-1} - H_{n-1}</math>, so <math>G_{n} - H_{n}</math> also satisfies this recurrence. If we match up the numbers of <math>F_n</math> and <math>G_n - H_n = a\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)</math>, we note that <math>F_0 = G_0 - H_0 = 0</math>. However, <math>F_1 = 1 = G_1 - H_1</math>, which implies that <math>a = \frac{1}{\sqrt{5}}</math>. Now, <math>G_n - H_n</math> satisfies the same recurrence as <math>F_n</math> and has the same initial terms, so we are done.
 
  
 
==Problems==
 
==Problems==
 
=== Introductory ===
 
=== Introductory ===
 
# The Fibonacci sequence <math>1,1,2,3,5,8,13,21,\ldots </math> starts with two 1s, and each term afterwards is the sum of its two predecessors. Which one of the ten [[digit]]s is the last to appear in the units position of a number in the Fibonacci sequence?<br><br><math> \mathrm{(A) \ 0 } \qquad \mathrm{(B) \ 4 } \qquad \mathrm{(C) \ 6 } \qquad \mathrm{(D) \ 7 } \qquad \mathrm{(E) \ 9 }  </math><div style="text-align:right">([[2000 AMC 12 Problems/Problem 4|2000 AMC 12, Problem 4]])</div>
 
# The Fibonacci sequence <math>1,1,2,3,5,8,13,21,\ldots </math> starts with two 1s, and each term afterwards is the sum of its two predecessors. Which one of the ten [[digit]]s is the last to appear in the units position of a number in the Fibonacci sequence?<br><br><math> \mathrm{(A) \ 0 } \qquad \mathrm{(B) \ 4 } \qquad \mathrm{(C) \ 6 } \qquad \mathrm{(D) \ 7 } \qquad \mathrm{(E) \ 9 }  </math><div style="text-align:right">([[2000 AMC 12 Problems/Problem 4|2000 AMC 12, Problem 4]])</div>
−
# Find <math>gcd(F_n,F_{n+1})</math>.
+
# A colony has <math>1</math> rabbit. A rabbit produces one offspring every month. An offspring rabbit takes one month to grow up. Find a formula for the number of rabbits (including offspring) in the <math>n</math>th month.
 +
## How about if the colony starts with <math>a</math> rabbits and <math>b</math> offspring?
 +
## Use this result to prove the identity <math>F_{m+n+1} = F_{m+1} \cdot F_{n+1} + F_{m} \cdot F_n</math>.
 +
# Find <math>\gcd(F_n,F_{n+1})</math>.
 +
# Prove the above [[#Identities|identites]].
  
 
=== Intermediate ===
 
=== 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. <div style="text-align:right">(Manhattan Mathematical Olympiad 2004)</div>
 
# 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. <div style="text-align:right">(Manhattan Mathematical Olympiad 2004)</div>
 
# Except for the first two terms, each term of the sequence <math>1000, x, 1000 - x,\ldots</math> 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 <math>x</math> produces a sequence of maximum length? <div style="text-align:right">([[1998 AIME Problems/Problem 8|1998 AIME, Problem 8]])</div>
 
# Except for the first two terms, each term of the sequence <math>1000, x, 1000 - x,\ldots</math> 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 <math>x</math> produces a sequence of maximum length? <div style="text-align:right">([[1998 AIME Problems/Problem 8|1998 AIME, Problem 8]])</div>
−
# A [[fair]] coin is to be tossed <math>10_{}^{}</math> times. Let <math>i/j^{}_{}</math>, in lowest terms, be the [[probability]] that heads never occur on consecutive tosses. Find <math>i+j_{}^{}</math>. <div style="text-align:right">([[1990 AIME Problems/Problem 9|1990 AIME, Problem 9]])</div>
+
# A fair coin is to be tossed <math>10_{}^{}</math> times. Let <math>\frac ij^{}_{}</math>, in lowest terms, be the [[probability]] that heads never occur on consecutive tosses. Find <math>i+j_{}^{}</math>. <div style="text-align:right">([[1990 AIME Problems/Problem 9|1990 AIME, Problem 9]])</div>
−
#Find <math>a</math> if <math>a</math> and <math>b</math> are [[integer]]s such that <math>x^2 - x - 1</math> is a factor of <math>ax^{17} + bx^{16} + 1</math>. <div style="text-align:right">([[1998 AIME Problems/Problem 13|1998 AIME, Problem 13]])</div>
+
#Find <math>a</math> if <math>a</math> and <math>b</math> are [[integer]]s such that <math>x^2 - x - 1</math> is a factor of <math>ax^{17} + bx^{16} + 1</math>. <div style="text-align:right">([[1988 AIME Problems/Problem 13|1988 AIME, Problem 13]])</div>
  
 
=== Olympiad ===
 
=== Olympiad ===
Line 34: Line 48:
 
==See also==
 
==See also==
 
* [[Combinatorics]]
 
* [[Combinatorics]]
 +
* [[Lucas Numbers]]
  
−
{{stub}}
+
==External Links==
 +
* [http://www.scriptspedia.org/Fibonacci_Numbers Fibonacci Algorithm implementation in C++, Java and Javascript]
 +
[[Category:Combinatorics]]

Latest revision as of 13:57, 24 June 2024

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 $1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...$.

Recursion

The Fibonacci sequence can be written recursively as $F_1 = F_2 = 1$ and $F_n=F_{n-1}+F_{n-2}$ for $n \geq 3$. This is the simplest nontrivial example of a linear recursion with constant coefficients. There is also an explicit formula below.

Readers should be wary: some authors give the Fibonacci sequence with the initial conditions $F_0 = F_1 = 1$ (or equivalently $F_1 = 1, F_2 = 2$). This change in indexing does not affect the actual numbers in the sequence, but it does change which member of the sequence is referred to by the symbol $F_n$ and so also changes the appearance of certain identities involving the Fibonacci numbers.

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 $F_{n - 2} = F_{n} - F_{n - 1}$. This allows us to compute, for example, that $F_0 = F_2 - F_1 = 0$, $F_{-1} = 1$, $F_{-2} = -2$, 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 $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n - 1} + F_{n - 2}$ for $n \geq 2$. In general, one can show that $F_n = (-1)^{n+1}F_{-n}$.

$\varphi$, $\psi$, and Binet's Formula

Main article: Binet's formula

The ratios $\frac{1}{1}$, $\frac{2}{1}$, $\frac{3}{2}$, $\frac{5}{3}$, $\frac{8}{5}$, ..., between successive terms of the sequence tend towards the limit $\frac{1 + \sqrt{5}}{2}$, a constant often denoted $\varphi$ (the Greek letter phi, also written $\phi$). $\varphi$ is a solution of the quadratic equation $x^2-x-1=0$. The other root is $\psi = \frac{1-\sqrt{5}}{2}$ (the Greek letter psi). One possible explanation for this fact is that the Fibonacci numbers are given explicitly by Binet's formula. It is $F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$. (Note that this formula is valid for all integers $n$.) It is so named because it was derived by mathematician Jacques Philippe Marie Binet, though it was already known by Abraham de Moivre and Euler before him. Another explanation is that you can continue the fibonacci numbers backward, too. Then you get something like $\dots -8,5,-3,2,-1,1,0,1,1,2,3,5,8\dots$ . The ratios between successive terms has you continue backwards is $\psi$.

When to use them

Usually, fibonacci-like recursions show up when organisms like rabbits produce babies but babies need to grow up which takes time. Two other places are when you make domino tilings in a $2\times n$ rectangle or when you make a string of a's and b's of a fixed length but you can't have 2 a's together. Many things can be turned into either the fibonacci recursion $F_n=F_{n-1}+F_{n-2}$ or another recursion that also produces the fibonacci numbers: $a_n=b_{n-1}$ and $b_n=b_{n-1}+a_{n-1}$. There are other recursions, but these two are the most frequent.

Identities

The most important identity regarding the Fibonacci sequence is its recursive definition, $F_{n+1} = F_n + F_{n-1}$. The following identities involving the Fibonacci numbers can be proved by induction.

  • $F_0 + F_1 + \cdots + F_{n} = F_{n+2} - 1$
  • $F_0 - F_1 + F_2 - \cdots - F_{2n-1} + F_{2n} = F_{2n-1} - 1$
  • $F_0^2 + F_1^2 + F_2^2 + \cdots + F_n^2 = F_n \cdot F_{n+1}$
  • $F_{n-1}\cdot F_{n+1} = F_{n}^2 + (-1)^n$
  • $F_{m+n+1} = F_{m+1} \cdot F_{n+1} + F_{m} \cdot F_n$


Problems

Introductory

  1. The Fibonacci sequence $1,1,2,3,5,8,13,21,\ldots$ 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?

    $\mathrm{(A) \ 0 } \qquad \mathrm{(B) \ 4 } \qquad \mathrm{(C) \ 6 } \qquad \mathrm{(D) \ 7 } \qquad \mathrm{(E) \ 9 }$
  2. A colony has $1$ rabbit. A rabbit produces one offspring every month. An offspring rabbit takes one month to grow up. Find a formula for the number of rabbits (including offspring) in the $n$th month.
    1. How about if the colony starts with $a$ rabbits and $b$ offspring?
    2. Use this result to prove the identity $F_{m+n+1} = F_{m+1} \cdot F_{n+1} + F_{m} \cdot F_n$.
  3. Find $\gcd(F_n,F_{n+1})$.
  4. Prove the above identites.

Intermediate

  1. 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)
  2. Except for the first two terms, each term of the sequence $1000, x, 1000 - x,\ldots$ 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 $x$ produces a sequence of maximum length?
  3. A fair coin is to be tossed $10_{}^{}$ times. Let $\frac ij^{}_{}$, in lowest terms, be the probability that heads never occur on consecutive tosses. Find $i+j_{}^{}$.
  4. Find $a$ if $a$ and $b$ are integers such that $x^2 - x - 1$ is a factor of $ax^{17} + bx^{16} + 1$.

Olympiad

  1. Determine the maximum value of $m^2 + n^2$, where $m$ and $n$ are integers satisfying $m, n \in \{ 1,2, \ldots , 1981 \}$ and $( n^2 - mn - m^2 )^2 = 1$.

See also

External Links

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Fibonacci_sequence&oldid=221019"