Skip to main content

Section 11.3 Solving through iteration

Given a recursively defined sequence \(\{a_k\} \text{,}\) we can “unravel” the recursive definition to determine an explicit formula for the general term \(a_k \) which involves only the index \(k \text{.}\)

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{align*} h_k \amp = \frac{3}{4} \, h_{k-1} \text{,} \amp k \amp \ge 1 \text{.} \end{align*}
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{align*} h_k \amp = \frac{3}{4} \, h_{k-1} \text{,} \amp h_{k-1} \amp = \frac{3}{4} \, h_{k-2} \text{,} \amp h_{k-2} \amp = \frac{3}{4} \, h_{k-3} \text{,} \amp \amp \dotsc\text{.} \end{align*}
Therefore, for \(k \ge 1 \text{,}\) we can calculate
\begin{align*} h_k \amp = \frac{3}{4}\,h_{k-1} \\ \amp = \frac{3}{4}\left(\frac{3}{4}\,h_{k-2}\right) = \left(\frac{3}{4}\right)^2 h_{k-2}\\ \amp = \left(\frac{3}{4}\right)^2\left(\frac{3}{4}\,h_{k-3}\right) = \left(\frac{3}{4}\right)^3 h_{k-3}\\ \amp \vdots \\ \amp = \left(\frac{3}{4}\right)^k h_0 = \left(\frac{3}{4}\right)^k (100). \end{align*}
(Note that this formula is also valid for \(k=0 \text{.}\))
We can verify our formula by substituting it into the original recurrence relation:
\begin{equation*} \mathrm{RHS} = \frac{3}{4}\,h_{k-1} = \frac{3}{4}\,\left(\frac{3}{4}\right)^{k-1} h_0 = \left(\frac{3}{4}\right)^k h_0 = h_k = \mathrm{LHS}\text{.} \end{equation*}
We could also prove our formula is correct by induction.
We can generalize Worked Example 11.3.1 by replacing the “bounce factor” \(3 / 4 \) by an arbitrary factor \(r \text{.}\)

Worked Example 11.3.2.

Solve the recurrence relation \(a_k = r a_{k-1} \) for \(k \ge 1 \text{,}\) where \(r \) is a constant and the first term \(a_0 \) is arbitrarily chosen.
Solution.
Through iteration, we obtain
\begin{equation*} a_k = r a_{k-1} = r (r a_{k-2}) = r \bbrac{r (r a_{n-3})} = \dotsb = r^k a_0\text{.} \end{equation*}

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{align*} a_k \amp = ka_{k-1} \text{,} \amp k \amp \ge 1 \text{.} \end{align*}
Therefore, for \(k \ge 1 \text{,}\) we have
\begin{align*} a_k \amp = k a_{k-1} \phantom{(k-1)(k-2) \dotsm \bbrac{k - (k-1)} = k(k-1)(k-2) \dotsm 1 \cdot a_0 = k!.}\\ \amp = k \bbrac{ (k-1) a_{k-2} } \\ \phantom{a_k} \amp = k \Bbrac{ (k-1) \bbrac{ (k-2) a_{k-3} } } \\ \amp \vdots \\ \amp = k(k-1)(k-2)\dotsm \bbrac{k - (k-1)} a_{k-k} \text{.} \end{align*}
Simplifying this last expression leads to
\begin{equation*} a_k = k(k-1)(k-2)\dotsm 1 \cdot a_0 = k! \text{.} \end{equation*}
Note that the formula \(a_k = k! \) is also valid for \(k=0 \) when we adopt the convention \(0! = 1 \text{.}\)

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 \text{,}\) \(a_1 = \frac{1}{2} \text{,}\) and
\begin{align*} a_k \amp = \frac{k}{2(k-1)}\, a_{k-1} \text{,} \amp k \amp \ge 2 \text{.} \end{align*}
Solution.
Iterating, we obtain
\begin{align*} a_k \amp = \frac{k}{2(k-1)}\, a_{k-1} \\ \amp = \frac{k}{2(k-1)} \left( \frac{k-1}{2(k-2)}\, a_{k-2} \right) = \frac{k}{2^2(k-2)} \, a_{k-2}\\ \amp = \frac{k}{2^2(k-2)} \left( \frac{k-2}{2(k-3)}\, a_{k-3} \right) = \frac{k}{2^3(k-3)} \, a_{k-3}\\ \amp \vdots \\ \amp = \frac{k}{2^{k-1} \bbrac{k-(k-1)}} \, a_{k-(k-1)} \text{.} \end{align*}
Simplifying this last expression, we obtain
\begin{equation*} a_k = \frac{k}{2^{k-1}} \, a_1 = \frac{k}{2^k} \text{.} \end{equation*}
PrevTopNext