Difference between revisions of "Fibonacci sequence"

Revision as of 18:06, 6 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 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
$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 the $n$ th term of the Fibonacci sequence. It is $\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$ .

Proof: If we experiment with fairly large numbers, we see that the quotient of consecutive terms of the sequence approach $1.618\ldots$ (see above). Thus we have a sequence resembling that of a geometric sequence, which we let be $a \cdot r^n$ . Then, $F_{n+1} = F_n + F_{n-1} \Longrightarrow a \cdot r^{n+1} = a \cdot r^{n} + a \cdot r^{n-1}$ $\Longrightarrow r^2 = r + 1$ . Using the quadratic formula, we find $r = \frac{1 \pm \sqrt{5}}{2}$ .

We now have two sequences $G_n = a \left(\frac{1 + \sqrt{5}}{2}\right)^n$ and $H_n = a \left(\frac{1 - \sqrt{5}}{2}\right)^n$ , but neither match up with the Fibonacci sequence. In particular, $F_0 = 0$ , but for $G_0, H_0$ to be zero, we need $a = 0$ , but then the sequence just generates a constant $0$ . After a bit of experimenting with these two sequences to find a sequence where the zeroth term being zero, notice that $G_{n+1} - H_{n+1} = G_{n} - H_{n} + G_{n-1} - H_{n-1}$ , so $G_{n} - H_{n}$ also satisfies this recurrence. If we match up the numbers of $F_n$ and $G_n - H_n = a\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$ , we note that $F_0 = G_0 - H_0 = 0$ . However, $F_1 = 1 = G_1 - H_1$ , which implies that $a = \frac{1}{\sqrt{5}}$ . Now, $G_n - H_n$ satisfies the same recurrence as $F_n$ and has the same initial terms, so we are done.

Problems

Introductory

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 }$
(2000 AMC 12, Problem 4)
Find $gcd(F_n,F_{n+1})$ .

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 $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?
(1998 AIME, Problem 8)
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_{}^{}$ .
(1990 AIME, Problem 9)
Find $a$ if $a$ and $b$ are integers such that $x^2 - x - 1$ is a factor of $ax^{17} + bx^{16} + 1$ .
(1998 AIME, Problem 13)

Olympiad

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$ .
(1981 IMO, Problem 3)

@@ Line 14: / Line 14: @@
 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>.
+'''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>.
 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.

Page

Toolbox

Search