Using Induction to Prove Correctness of Recurrence Relation Closed Formulas
Proving a Closed Formula for a Recursively Defined Sequence is Correct
In the previous lesson, we discussed how, if given a recursively defined sequence \(\{a_n\}_{n=1}^\infty\), one can guess a closed formula for \(a_n\) by using the recurrence relation and expanding out all the arithmetic for the first several elements of the sequence, \(a_1,\) \(a_2\), \(a_3,\), \(a_4\), etc, seeing if there is a pattern.
For instance, in the previous lesson, for the sequence \(\{a_n\}_{n=0}^\infty\) defined recursively with initial conditions \(a_0=3\) and recurrence relation \(a_n=a_{n-1}\cdot 2\) for all \(n\geq 1\), we were able to guess that a closed formula for the \(n\)th term of the sequence is given by \(a_n=3\cdot 2^n\).
However, no matter how correct that formula feels, we have not by any means shown that it is correct, or rather, that it “fits” the recursive definition provided. Below, we show how to use induction to prove the correctness of closed formulas.
Proof:
(Base Case) Note that when \(n=0\), \(3\cdot 2^0=3\cdot 1=3=a_0\) which matches the initial condition given for our sequence.
(Inductive Case) Now let \(k\geq 0\) and suppose that \(a_k=3\cdot 2^k\). We want to show that \(a_{k+1}=3\cdot 2^{k+1}\). So note that by our recurrence relation and how we defined \(a_n\),
$$\begin{align} a_{k+1}&=a_{(k+1)-1}\cdot 2& & \\& a_{k}\cdot 2& & \\ &=(3\cdot 2^k)\cdot 2 & & \text{by the induction hypothesis}\\ &=3\cdot 2^{k+1}& &\text{because } 2^k\cdot 2^1=2^{k+1}\end{align}$$
So by the inductive case and the base case above, we have shown that the formula \(3\cdot 2^n\) is indeed equal to \(a_n\) for all \(n\geq 0\). QED
That is, we inductively verified that the closed formula produces exactly the same values as the sequence recurrence relation formula and its initial conditions. Therefore the closed formula works just as well for producing sequence entries as the recurrence relation.
Proof:
(Base Case) Let \(n=0\). Note that \(5+3(0)=5=a_0\), indicating that the formula matches the initial condition.
(Inductive Case) Let \(k\geq 0\) and suppose \(a_k=5+3k\). We want to show that \(a_{k+1}=5+3(k+1)\). So notice
$$\begin{align} a_{k+1}&=a_{k}+3& &\text{because} (k+1)-1=k\\ &=(5+3k)+3& &\text{by induction hypothesis}\\ &=5+3k+3& &\text{dropped the parentheses}\\&=5+3(k+1)& &\text{factored out a 3}\end{align}$$
but this is exactly what we wanted to show.
Therefore, by the base and inductive cases, we can conclude that the closed formula given in the problem is correct. QED
Proof: (Base Case) Let \(n=0\). Note that the formula gives us \(12-3(0)=12=c_0\), which indicates that the closed formula correctly produces the initial conditions of the given sequence.
(Inductive Case) Let \(k\geq 0\) and suppose that \(c_k=12-3k\). We want to show that \(c_{k+1}=12-3(k+1)\). Thus note
$$\begin{align} c_{k+1}&=c_k-3& & \text{because} (k+1)-1=k\\ &=(12-3k)-3& & \text{by induction hypothesis}\\ &=12-3(k+1)& &\text{dropped the parentheses, and factored out } -3\end{align}$$
but this is exactly what we wanted to demonstrate. Therefore, by the base case and the inductive case, we can conclude that the closed formula given in the statement of the problem matches the recurrence relation formula and the initial conditions (i.e. the closed formula is correct). QED.
Proof: (Base Case) Let \(n=0\). Notice that \(8\cdot\left(\frac{1}{2}\right)^0=8\cdot 1=8=d_0.\) Thus the base case holds (the formula produces the initial conditions).
(Inductive Case) Let \(k\geq 0\) and suppose that \(d_k=8\cdot\left(\frac{1}{2}\right)^k\). We want to show that \(d_{k+1}=8\cdot\left(\frac{1}{2}\right)^{k+1}\). Note that
$$\begin{align} a_{k+1}&=d_{k}\cdot \frac{1}{2}& &\\&=\left(8\cdot\left(\frac{1}{2}\right)^k\right)\cdot \frac{1}{2}& &\text{by induction hypothesis} \\&=8\cdot \left(\frac{1}{2}\right)^{k+1}& & \end{align}$$
which is exactly what we wanted to show. Thus by the base and inductive cases, we can conclude that the closed formula for the given sequence is indeed correct (because we just showed that the recursive formula matches the closed formula for every possible \(n\geq 0\)). QED
Proof: (Base Case) Let \(n=1\). Notice that \(n!=1!=1=a_1\). Therefore, the closed formula matches the initial conditions when \(n=1\), satisfying the base case.
(Inductive Case) Let \(k\geq 1\) and suppose that \(a_k=k!\). We want to show that \(a_{k+1}=(k+1)!\). Notice that
$$\begin{align} a_{k+1}&=(k+1)\cdot a_{k}& & \\ &=(k+1)\cdot (k!)& &\text{by the induction hypothesis}\\ &=(k+1)(k \cdot (k-1)\cdot (k-2)\cdot \ldots \cdot 3\cdot 2 \cdot 1)& & \text{expanding the factorial}\\ &=(k+1)!& & \end{align}$$
which is exactly what we wanted to show. Therefore by the base case and the inductive case, we can conclude that \(a_n=n!\) for all \(n\geq 1\), as was to be shown. QED.
Proof:
(Base case) let \(n=1\). Notice that
$$\begin{align}\sum_{i=1}^n 2^{n-i}\cdot i&=\sum_{i=1}^1 2^{1-i}\cdot i\\&=2^{1-1}\cdot 1\\&=2^0\cdot 1\\&=1\end{align}$$
Therefore the base case is satisfied.
(Inductive Case) Let \(k\in \mathbb{Z}\) such that \(k\geq 1\). Suppose that \(g_k=\sum_{i=1}^k 2^{k-i}\cdot i\). We want to show (WTS) that \(g_{k+1}=\sum_{i=1}^{k+1} 2^{(k+1)-i}\cdot i\). Notice that
$$\begin{align} g_{k+1}&=2\cdot g_{k}+(k+1)& &\text{using the recursive definition}\\&=2\cdot \sum_{i=1}^{k}2^{k-i}\cdot i+(k+1)& & \text{by the induction hypothesis}\\&= \sum_{i=1}^{k}2^1\cdot 2^{k-i}\cdot i+(k+1)& &\text{bringing the 2 factor inside the sum (distributing)}\\&=\sum_{i=1}^{k}\cdot 2^{(k+1)-i}\cdot i+(k+1)& &\text{added the exponents on the 2’s}\\&=\sum_{i=1}^{k}\cdot 2^{(k+1)-i}\cdot i+2^{0}(k+1)& &\text{starting a trick so this looks like what we WTS}\\&=\sum_{i=1}^{k}\cdot 2^{(k+1)-i}\cdot i+2^{(k+1)-(k+1)}\cdot(k+1)& &\text{changed the 0 exponent to help next step}\\&=\left[2^{(k+1)-1}\cdot 1+2^{(k+1)-2}\cdot 2+…+2^{(k+1)-k}\cdot k\right]+2^{(k+1)-(k+1)}\cdot (k+1)& &\text{expanded the sum, note last term follows the pattern}\\&=\sum_{i=1}^{k+1} 2^{(k+1)-i}\cdot i& & \text{wrote the whole thing in sigma notation}\end{align}$$
Therefore the inductive case holds. Thus, we can conclude by the two cases shown above that \(g_n=\sum_{i=1}^n 2^{n-i}\cdot i\) for all \(n\geq 1\). QED