Skip to main content

Discrete Mathematics: An Active Approach to Mathematical Reasoning

Jennifer Firkins Nordstrom

Section 5.6 Solving Recurrence Relations by Iteration

Given a sequence defined recursively, we want to be able to find an explicit formula for the sequence. In general, this can be difficult and can involve very sophisticated mathematical tools. We will learn one method, the method of iteration, just to get a taste for the ideas.
To find an explicit formula for a recursive sequence using the methods of iteration:
  1. Calculate several terms of the sequence, often without simplifying the terms.
  2. See a pattern.
  3. Guess an explicit formula for the pattern. Keep in mind your formula should just depend on \(n\text{.}\)
  4. Prove your explicit formula using induction.

Example 5.6.1. Finding an Explicit Formula.

Find the first five terms of the sequence given by \(a_k=a_{k-1}+3, k\geq 1\text{,}\) \(a_0=4\text{.}\)
Answer.
\(a_0=4, a_1=7, a_2=10, a_3=13, a_4=16\)
It might be difficult to see a pattern, so we will calculate the terms without simplifying at all.
\begin{align*} a_0& =4\\ a_1& =4+3\\ a_2& =(4+3)+3\\ a_3& =((4+3)+3)+3\\ a_4& =(((4+3)+3)+3)+3 \end{align*}
Now it should be easier to see a pattern. It seems we have \(a_n=4+3n\text{,}\) which is an explicit formula.
To prove this is the correct formula, we would assume \(a_k=a_{k-1}+3\) and prove \(a_n=4+3n\) by induction.

Proof.

Let \(a_k=a_{k-1}+3, a_0=4\text{.}\) Prove \(a_n=4+3n, n\geq 0\)
Base Step: Let \(n=0\text{.}\) Then \(a_n=a_0=4\text{.}\) And \(4+3n=4+3(0)=4\text{.}\) Thus, \(a_n=4+3n\) for \(n=0\text{.}\)
Induction Step: Assume \(a_k=4+3k\) for some \(k\geq 0\text{.}\)
Show \(a_{k+1}=4+3(k+1)\text{.}\)
Proof of induction step: By the recursive definition of the sequence, \(a_{k+1}=a_{k}+3\text{.}\) Thus,
\begin{align*} a_{k+1}&=a_k+3\\ &=4+3k+3\ \ \text{ by induction assumption}\\ &=4+3(k+1) \end{align*}
Therefore, by induction, \(a_n=4+3n, n\geq 0\text{.}\)

Definition 5.6.2.

An arithmetic sequence is given recursively by
\begin{equation*} a_k=a_{k-1}+d \end{equation*}
where \(d\) is constant.

Activity 5.6.1.

Generalize Example 5.6.1 to find an explicit formula for an arithmetic sequence.

(a)

Let \(d=5, a_0=2\text{.}\) Write out the first 6 terms of the arithmetic sequence. Can you find an explicit formula for the sequence (one that just depends on \(n\))?

(b)

Write out the first 6 terms of the sequence without simplifying at all. Now can you find an explicit formula?

(c)

Using the same technique of writing out the terms without simplifying, find an explicit formula for the general form, \(a_k=a_{k-1}+d\text{,}\) of an arithmetic sequence.

Definition 5.6.3.

A geometric sequence is given recursively by
\begin{equation*} a_k=ra_{k-1} \end{equation*}
where \(r\) is constant.

Activity 5.6.2.

Use the method of iteration to find an explicit formula for a geometric sequence.

(a)

Let \(r=2, a_0=3\text{.}\) Write out the first 6 terms of the geometric sequence. Can you find an explicit formula for the sequence (one that just depends on \(n\))?

(b)

Write out the first 6 terms of the sequence without simplifying at all. Now can you find an explicit formula?

(c)

Using the same technique of writing out the terms without simplifying, find an explicit formula for the general form, \(a_k=ra_{k-1}\text{,}\) of a geometric sequence.

Proving a Recursive Sequence Satisfies an Explicit Formula.

To prove a recursively defined sequence satisfies an explicit formula:
  • Assume the recursive formula for the sequence.
  • Show, using an induction proof, that the explicit formula holds. You need to prove the base step for all initial terms. You will need to use the recurrence relation in the inductive step.

Activity 5.6.3.

Prove if \(a_0=2\) and \(a_k=a_{k-1}+5\text{,}\) then \(a_n=2+5n\) for \(n\geq 0\) by induction.
Hint.
You are assuming the recursive relationship holds. The statement you are proving by induction is that \(a_n=2+5n\) for \(n\geq 0\text{.}\)

Activity 5.6.4.

Prove if \(a_k=ra_{k-1}\text{,}\) then \(a_n=a_0r^n\) for \(n\geq 0\) by induction.
Hint.
You are assuming the recursive relationship holds. The statement you are proving by induction is that \(a_n=a_0r^n\) for \(n\geq 0\text{.}\)
As promised, in Example 5.6.4 we will prove an explicit formula for the Fibonacci sequence. We will not derive it as that is beyond the scope of this course. But we can prove that it works using induction. Before working through the proof, it will be helpful to see the algebraic simplification in the next activity.

Activity 5.6.5.

Simplify \(\Bigl(\frac{1+\sqrt{5}}{2}\Bigr)^2\) and \(\Bigl(\frac{1-\sqrt{5}}{2}\Bigr)^2\text{.}\)

Example 5.6.4. Proving Explicit Formula for the Fibonacci Sequence.

Let \(F_k=F_{k-1}+F_{k-2}, k\geq 1\text{,}\) \(F_0=1, F_1=1\) be the Fibonacci sequence.
Prove \(F_n=\frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{n+1}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{n+1}\biggr]\text{.}\)

Proof.

Let \(F_k=F_{k-1}+F_{k-2}, F_0=1, F_1=1\text{.}\)
Base Step: Let \(n=0\text{.}\) Then \(F_0=1\text{.}\) And
\begin{equation*} \frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{0+1}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{0+1}\biggr] = \frac{1}{\sqrt{5}}\biggl[\frac{2\sqrt{5}}{2}\biggr]=1 \end{equation*}
Let \(n=1\text{.}\) Then \(F_1=1\text{.}\) And
\begin{equation*} \frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{1+1}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{1+1}\biggr]= \frac{1}{\sqrt{5}}\biggl[\frac{6+2\sqrt{5}}{4}-\frac{6-2\sqrt{5}}{4}\biggr]=1 \end{equation*}
Induction Step: Assume
\begin{equation*} F_i=\frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{i+1}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{i+1}\biggr], 0\leq i\leq k \end{equation*}
for some \(k\geq 0\) (strong induction).
Show
\begin{equation*} F_{k+1}=\frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{k+2}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{k+2}\biggr]. \end{equation*}
Proof of induction step: By the recursive definition of the sequence, \(F_{k+1}=F_{k}+F_{k-1}\text{.}\) Thus,
\begin{align*} F_{k+1}&=\frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{k+1}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{k+1}\biggr]+ \frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{k}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{k}\biggr]\\ &=\frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{k+1}+\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{k}- \biggl(\frac{1-\sqrt{5}}{2}\biggr)^{k+1}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{k}\biggr]\\ &=\frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{k}\biggl(\frac{1+\sqrt{5}}{2}+1\biggr)- \biggl(\frac{1-\sqrt{5}}{2}\biggr)^{k}\biggl(\frac{1-\sqrt{5}}{2}+1\biggr)\biggr]\\ &=\frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{k}\biggl(\frac{3+\sqrt{5}}{2}\biggr)- \biggl(\frac{1-\sqrt{5}}{2}\biggr)^{k}\biggl(\frac{3-\sqrt{5}}{2}\biggr)\biggr]\\ &=\frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{k}\biggl(\frac{1+\sqrt{5}}{2}\biggr)^2- \biggl(\frac{1-\sqrt{5}}{2}\biggr)^{k}\biggl(\frac{1-\sqrt{5}}{2}\biggr)^2\biggr]\\ &=\frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{k+2}- \biggl(\frac{1-\sqrt{5}}{2}\biggr)^{k+2}\biggr] \end{align*}
Therefore, by induction, \(F_n=\frac{1}{\sqrt{5}}\biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{n+1}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{n+1}\biggr]\text{.}\)
Note, the proof contains some algebraic steps that may not be obvious. But all of them can be checked. For example, it is easier to see that \(\biggl(\frac{3+\sqrt{5}}{2}\biggr)=\biggl(\frac{1+\sqrt{5}}{2}\biggr)^2\) by squaring the RHS and simplifying.
It can be confusing to remember when to use induction and when to use a LHS/RHS proof. The following summary gives guidelines for when to use each technique.

Summary of Techniques for Sequences.

If you are given a sequence where each term is just a formula for \(n\text{:}\)
  • You sequence is defined explicitly.
  • For example, \(a_n=n^2+5\text{.}\)
  • To prove a recurrence relation, use LHS/RHS proof.
  • You are assuming the explicit formula and proving the recurrence relation. Thus, use the explicit formula in your proof. Do not assume the recurrence relation.
If you are given a sequence where each term is defined by previous terms:
  • You sequence is defined recursively.
  • For example, \(a_n=3a_{n-1}+2a_{n-2}\text{.}\)
  • To prove an explicit formula, use induction on the explicit formula.
  • You are assuming the recurrence formula and proving the explicit formula. Thus, use the recurrence formula in your proof, generally in the induction step. Your base step, assume statement, and show statement all involve the explicit formula.

Reading Questions Check Your Understanding

1.

Find a recurrence relation for \(3, 6, 12, 24, 48, \ldots\text{.}\)

2.

Find an explicit formula for \(3, 6, 12, 24, 48, \ldots\text{.}\)

3.

Find a recurrence relation for \(2, 6, 10, 14, 18, \ldots\text{.}\)

4.

Find an explicit formula for \(2, 6, 10, 14, 18, \ldots\text{.}\)

5.

Simplify \(\biggl(\frac{1-\sqrt{5}}{2}\biggr)^2\text{.}\)

Exercises Exercises

1.

Use iteration to conjecture an explicit formula for the sequence
\begin{equation*} a_0=1 \end{equation*}
\begin{equation*} a_k=ka_{k-1}, k\geq1. \end{equation*}

2.

Use iteration to conjecture an explicit formula for the sequence
\begin{equation*} b_1=1 \end{equation*}
\begin{equation*} b_k=3b_{k-1}+1, k\geq2. \end{equation*}
Hint.
The formula for a geometric sum, (5.2.2), might be helpful.

3.

Use iteration to conjecture an explicit formula for the sequence
\begin{equation*} r_0=3 \end{equation*}
\begin{equation*} r_k=r_{k-1}+2k, k\geq1. \end{equation*}
Hint.
The formula for the sum of the first \(n\) integers, (5.2.1) might be helpful.

4.

Suppose \(d\) is a fixed constant and \(a_0, a_1, a_2,\ldots\) is a sequence that satisfies the recurrence relation \(a_k=a_{k-1}+d\) for all integers \(k\geq 1\text{.}\) Use mathematical induction to prove that \(a_n=a_0+nd\) for all integers \(n\geq 0\text{.}\)

5.

Suppose \(r\) is a fixed constant and \(a_0, a_1, a_2,\ldots\) is a sequence that satisfies the recurrence relation \(a_k=ra_{k-1}\) for all integers \(k\geq 1\text{.}\) Use mathematical induction to prove that \(a_n=a_0r^n\) for all integers \(n\geq 0\text{.}\)
You have attempted of activities on this page.
PrevTopNext