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"

(→‎Problems: from watlinkshere, more probls)
m (+ problem)
Line 1: Line 1:
−
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. The first few terms are <br><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>\displaystyle 0, 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>.
+
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]].
  
 
== Phi ==
 
== Phi ==
  
−
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]].
+
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]].  
  
 
== Binet's formula ==
 
== Binet's formula ==
Line 17: Line 17:
 
=== 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>
 
# 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>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>
 
=== Olympiad ===
 
=== Olympiad ===

Revision as of 22:16, 7 September 2007

The Fibonacci sequence is a sequence of integers 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
$\displaystyle 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...$.

The Fibonacci sequence can be written recursively as $F_n=F_{n-1}+F_{n-2}$. There is also an explicit definition below.

Phi

Ratios between successive terms, $\frac{1}{1}$, $\frac{2}{1}$, $\frac{3}{2}$, $\frac{5}{3}$, $\frac{8}{5}$, tend towards the limit phi.

Binet's formula

Binet's formula is an explicit formula used to find any nth term. It is $\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$.

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 }$

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 $i/j^{}_{}$, in lowest terms, be the probability that heads never occur on consecutive tosses. Find $i+j_{}^{}$.

Olympiad

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

See also

This article is a stub. Help us out by expanding it.

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