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.
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.
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.
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*}
