Recursive Sequences and the Fibonacci Sequence, precalculus lesson

Put 100 dollars in a jar and add 20 more every week. Nobody describes that jar with a formula in the week number. You say what it holds now and how next week’s amount comes from this week’s. Many sequences arise exactly like this, one step at a time from the terms before.

Key terms

Recursive rule

Definition A recursive rule, or recurrence relation, expresses each term of a sequence after the first few through earlier terms. A rule of order $k$ gives $a_n$ from the index $n$ and the $k$ terms just before it,

\begin{gathered} a_n = g(n, a_{n-1}, a_{n-2}, \dots, a_{n-k}) \\[0.4em] \text{for every } n \ge n_0 + k, \end{gathered}

where $n_0$ is the first index. At every step the rule has to produce a real number, so for instance it may never call for a division by $0$ .

In plain words A recursive rule tells you how to get the next term from the ones you already have. It says nothing about where to start.

Example If the jar holds $a_n$ dollars after $n$ weeks, its rule is $a_n = a_{n-1} + 20$ for $n \ge 1$ , a rule of order $1$ . Many books, and the calculus lessons, write the same rule one index higher, as $a_{n+1} = a_n + 20$ for $n \ge 0$ . A rule can also break down. Take $a_1 = 2$ and

a_n = \frac{1}{a_{n-1} - 1} \quad \text{for } n \ge 2.

Then $a_2 = 1$ , and the next step asks for $1/0$ , so there is no $a_3$ .

Initial value

Definition The initial values of a recursively defined sequence are the terms given directly, before the rule takes over. A rule of order $k$ needs $k$ initial values $a_{n_0}, a_{n_0 + 1}, \dots, a_{n_0 + k - 1}$ . When these are given and the rule produces a real number at every step, exactly one sequence has these initial values and satisfies the rule.

In plain words The rule says how to take a step. The initial values say where you stand before the first step, and a different start gives a different sequence.

Example The jar starts with $a_0 = 100$ , so its amounts are $100, 120, 140, 160, \dots$ dollars. The table runs one rule, $a_n = 2a_{n-1}$ for $n \ge 2$ , from three different initial values.

Initial value	First five terms
$a_1 = 3$	$3, 6, 12, 24, 48$
$a_1 = -1$	$-1, -2, -4, -8, -16$
$a_1 = 0$	$0, 0, 0, 0, 0$

Generating terms

Definition To generate the terms of a recursively defined sequence of order $k$ , start from the $k$ initial values and apply the rule for $n = n_0 + k$ , then $n = n_0 + k + 1$ , and so on in order. Each new term needs only the $k$ most recent terms, but reaching $a_n$ this way requires every term before it.

In plain words Work forward one term at a time and keep the last few terms in view, as many as the rule looks back. There is no skipping ahead.

Example Take $a_1 = 1$ , $a_2 = 3$ and $a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 3$ . Each step uses the two latest terms and then forgets the older one.

$n$	Terms used	$a_n$
$3$	$a_2 = 3$ and $a_1 = 1$	$3 + 2 \cdot 1 = 5$
$4$	$a_3 = 5$ and $a_2 = 3$	$5 + 2 \cdot 3 = 11$
$5$	$a_4 = 11$ and $a_3 = 5$	$11 + 2 \cdot 5 = 21$
$6$	$a_5 = 21$ and $a_4 = 11$	$21 + 2 \cdot 11 = 43$

Fibonacci recurrence

Definition The Fibonacci sequence is the sequence of order two given by

\begin{gathered} F_1 = 1, \qquad F_2 = 1, \\[0.4em] F_n = F_{n-1} + F_{n-2} \quad \text{for } n \ge 3. \end{gathered}

Many texts also use $F_0 = 0$ , which fits the same rule since $F_2 = F_1 + F_0$ .

In plain words Start with two ones. From then on each number is the sum of the two before it.

Example The first twelve Fibonacci numbers are

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

The ratios of neighboring terms swing above and below one value and close in on it.

$n$	$1$	$2$	$3$	$4$	$5$	$6$	$10$
$F_{n+1} / F_n$	$1$	$2$	$1.5$	$1.667$	$1.6$	$1.625$	$1.618$

It can be shown that these ratios approach the golden ratio

\frac{1 + \sqrt{5}}{2} \approx 1.618034.

Explicit versus recursive description

Definition An explicit description gives $a_n$ as a formula in $n$ alone. A recursive description gives initial values and a rule in terms of earlier terms. Two descriptions define the same sequence when they agree at every index. An explicit formula fits a recursive description when it produces the initial values and turns the rule into an identity that holds for every $n$ the rule covers. These two checks prove that the formula gives every term, by mathematical induction.

In plain words An explicit formula lets you jump to any term. A recursive rule is often how the sequence actually arises, but you must walk to each term. When you have both, use whichever suits the question.

Example The rule $a_1 = 1$ , $a_n = a_{n-1} + 2n - 1$ for $n \ge 2$ gives $1, 4, 9, 16, 25$ , which suggests $a_n = n^2$ . The formula gives $1^2 = 1$ at the start, and putting it into the right side of the rule gives

\begin{aligned} &(n - 1)^2 + 2n - 1 \\[0.4em] &\quad = n^2 - 2n + 1 + 2n - 1 \\[0.4em] &\quad = n^2, \end{aligned}

so it fits. Going the other way, the explicit formula $b_n = 5 \cdot 2^n$ for $n \ge 0$ has the recursive description $b_0 = 5$ and $b_n = 2b_{n-1}$ for $n \ge 1$ . The Fibonacci numbers have an explicit formula too, Binet’s formula

\begin{aligned} F_n = \frac{1}{\sqrt{5}}\Biggl[&\left(\frac{1 + \sqrt{5}}{2}\right)^n \\[0.8em] &\quad - \left(\frac{1 - \sqrt{5}}{2}\right)^n\Biggr]. \end{aligned}

It gives $F_{10} = 55$ exactly, although nothing in the simple rule hints at square roots.

Recursion alone does not guarantee convergence

Definition A sequence converges to a number $L$ when its terms get and stay as close to $L$ as you like once $n$ is large enough. The exact definition comes in the lesson on sequence behavior and limiting values. A recursive rule defines a sequence as long as every step is defined, but that sequence need not converge. It may grow without bound, swing back and forth, or repeat a cycle, and under one rule the outcome can depend on the initial value. For a rule $a_n = g(a_{n-1})$ where $g$ is a polynomial, or more generally a function continuous at $L$ , a sequence that converges to $L$ must have $L = g(L)$ . The converse is false, so a solution of $L = g(L)$ does not show that the sequence converges.

In plain words Being able to compute terms forever does not mean they are heading anywhere. Solving $L = g(L)$ only tells you where the sequence could settle, if it settles at all.

Example For the rule $a_n = 2a_{n-1} - 1$ with $n \ge 2$ the equation $L = 2L - 1$ has the single solution $L = 1$ .

Initial value	First five terms	Behavior
$a_1 = 1$	$1, 1, 1, 1, 1$	constant, converges to $1$
$a_1 = 1.5$	$1.5, 2, 3, 5, 9$	grows without bound
$a_1 = 0$	$0, -1, -3, -7, -15$	decreases without bound

Only the start $a_1 = 1$ converges. Compare the rule

a_n = \frac{a_{n-1}}{2} + 1 \quad \text{for } n \ge 2

with $a_1 = 0$ , which gives $0, 1, 1.5, 1.75, 1.875$ and does settle on $2$ . The convergence of sequences lesson in calculus makes this precise.

Check yourself

Generate the first five terms of $a_1 = 2$ , $a_n = 3a_{n-1} - 2$ for $n \ge 2$ . Then check that $a_n = 3^{n-1} + 1$ fits this description.

Show the answer

The terms are $2, 4, 10, 28, 82$ . The formula gives $3^0 + 1 = 2$ at the start, and

3\left(3^{n-2} + 1\right) - 2 = 3^{n-1} + 1,

so it satisfies the rule as well.

Find $F_{12}$ , then add the first ten Fibonacci numbers. How does the sum compare with $F_{12}$ ?

Show the answer

From the list above $F_{12} = 144$ . The sum is

\begin{aligned} &1 + 1 + 2 + 3 + 5 + 8 \\[0.4em] &\quad + 13 + 21 + 34 + 55 = 143, \end{aligned}

which is one less than $F_{12}$ .

Use the rule $a_n = 2 - a_{n-1}$ for $n \ge 2$ with $a_1 = 0$ and then with $a_1 = 1$ . Which start gives a convergent sequence?

Show the answer

Starting at $0$ gives $0, 2, 0, 2, \dots$ , which keeps jumping and does not converge. Starting at $1$ gives $1, 1, 1, \dots$ , which converges to $1$ . The equation $L = 2 - L$ gives $L = 1$ whatever the start, yet only one of the two starts settles there.

Recursive Sequences and the Fibonacci Sequence

Key terms

Recursive rule

Initial value

Generating terms

Fibonacci recurrence

Explicit versus recursive description

Recursion alone does not guarantee convergence

Check yourself

How this lesson connects

Builds on

Used later in

Where this leads in Calculus