EF Recurrence relations

Skip to main content

Section 11.2 Recurrence relations

recursively-defined sequence: 🔗
a sequence ${a_{k}}$ from a set $A,$ where $a_{0}, a_{1}, \dots, a_{K - 1}$ are defined explicitly, and for $k \geq K,$ the term $a_{k}$ is defined in terms of some (or all) of the previous terms in the sequence $a_{0}, a_{1}, \dots, a_{k - 1}$
recurrence relation: 🔗
for a recursively-defined sequence, the formula that defines the general term $a_{k}$ recursively in the previous terms $a_{0}, a_{1}, \dots, a_{k - 1}$

Example 11.2.1. A bouncing ball.

A ball is dropped from a height of 100 cm. On each bounce, it returns to

75 %

of its previous height.

Let

h_{k}

be the height in centimetres after the

k^{th}

bounce. Then

h_{0} = 100

and the recurrence relation is

\begin{aligned} h_{k} & = \frac{3 h_{k - 1}}{4}, & k & \geq 1 . \end{aligned}

The terms of the sequence are

100, 75, 56.25, 42.1875, \dots .

Example 11.2.2. Factorial.

Set

a_{0} = 1,

and let

a_{k} = k a_{k - 1}

for

k \geq 1 .

Then the terms of the sequence are

1, 1, 2, 6, 24, 120, \dots .

Example 11.2.3. Fibonacci sequence.

The sequence

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots

can be defined recursively by

a_{0} = 0,

a_{1} = 1,

and

\begin{aligned} a_{k} & = a_{k - 1} + a_{k - 2}, & k & \geq 2 . \end{aligned}

Example 11.2.4. A sequence of sets.

Define a sequence

{A_{k}}

from

P (N)

recursively as follows. Let

A_{0} = \emptyset,

and take the recurrence relation to be

\begin{aligned} A_{k} & = A_{k - 1} \cup {k}, & k & \geq 1 . \end{aligned}

Then the terms of the sequence are

\emptyset, {1}, {1, 2}, {1, 2, 3}, \dots, {1, 2, \dots, k}, \dots .

<Prev ^Top Next>