EF Solving through iteration

Section 11.3 Solving through iteration

Given a recursively defined sequence

{a_{k}},

we can “unravel” the recursive definition to determine an explicit formula for the general term

a_{k}

which involves only the index

k .

🔗

Worked Example 11.3.1.

🔗

Solve the recurrence relation from Example 11.2.1.

Solution.

The sequence in the example was defined recursively by

h_{0} = 100

and

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

We can apply this formula to every term in the sequence, except for the first, using the pattern “each term is three-quarters of the previous term.” That is,

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

Therefore, for

k \geq 1,

we can calculate

\begin{aligned} h_{k} & = \frac{3}{4} h_{k - 1} \\ = \frac{3}{4} (\frac{3}{4} h_{k - 2}) = {(\frac{3}{4})}^{2} h_{k - 2} \\ = {(\frac{3}{4})}^{2} (\frac{3}{4} h_{k - 3}) = {(\frac{3}{4})}^{3} h_{k - 3} \\ ⋮ \\ = {(\frac{3}{4})}^{k} h_{0} = {(\frac{3}{4})}^{k} (100) . \end{aligned}

(Note that this formula is also valid for

k = 0 .

)

We can verify our formula by substituting it into the original recurrence relation:

RHS = \frac{3}{4} h_{k - 1} = \frac{3}{4} {(\frac{3}{4})}^{k - 1} h_{0} = {(\frac{3}{4})}^{k} h_{0} = h_{k} = LHS .

We could also prove our formula is correct by induction.

🔗

Worked Example 11.3.2.

🔗

Solve the recurrence relation

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

for

k \geq 1,

where

r

is a constant and the first term

a_{0}

is arbitrarily chosen.

Solution.

Through iteration, we obtain

a_{k} = r a_{k - 1} = r (r a_{k - 2}) = r (r (r a_{n - 3})) = \dots = r^{k} a_{0} .

🔗

Worked Example 11.3.3.

🔗

Solve the recurrence relation from Example 11.2.2.

Solution.

The sequence in the example was defined recursively by

a_{0} = 1

and

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

Therefore, for

k \geq 1,

we have

\begin{aligned} a_{k} & = k a_{k - 1} \\ = k ((k - 1) a_{k - 2}) \\ = k ((k - 1) ((k - 2) a_{k - 3})) \\ ⋮ \\ = k (k - 1) (k - 2) \dots (k - (k - 1)) a_{k - k} . \end{aligned}

Simplifying this last expression leads to

a_{k} = k (k - 1) (k - 2) \dots 1 \cdot a_{0} = k! .

Note that the formula

a_{k} = k!

is also valid for

k = 0

when we adopt the convention

0! = 1 .

🔗

Checkpoint 11.3.4.

🔗

Verify that the formula in the solution to the above worked example satisfies the recurrence relation.

🔗

Worked Example 11.3.5.

🔗

Solve the recurrence relation

a_{0} = 1,

a_{1} = \frac{1}{2},

and

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

Solution.

Iterating, we obtain

\begin{aligned} a_{k} & = \frac{k}{2 (k - 1)} a_{k - 1} \\ = \frac{k}{2 (k - 1)} (\frac{k - 1}{2 (k - 2)} a_{k - 2}) = \frac{k}{2^{2} (k - 2)} a_{k - 2} \\ = \frac{k}{2^{2} (k - 2)} (\frac{k - 2}{2 (k - 3)} a_{k - 3}) = \frac{k}{2^{3} (k - 3)} a_{k - 3} \\ ⋮ \\ = \frac{k}{2^{k - 1} (k - (k - 1))} a_{k - (k - 1)} . \end{aligned}

Simplifying this last expression, we obtain

a_{k} = \frac{k}{2^{k - 1}} a_{1} = \frac{k}{2^{k}} .

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 11.3 Solving through iteration

Worked Example 11.3.1.

Worked Example 11.3.2.

Worked Example 11.3.3.

Checkpoint 11.3.4.

Worked Example 11.3.5.