3.7. Recursive Definitions

Recursion occurs in programming when a subroutine is defined—or at least partially defined—in terms of itself. But recursion also occurs outside of programming. A recursive definition is a definition that includes a reference to the term that is being defined. A recursive definition defines something at least partially in terms of itself. As in the case of recursive subroutines, mathematical induction can often be used to prove facts about things that are defined recursively.

Fig. 3.1 Fibonacci numbers occur in nature, as in this model of the florets in the head of a sunflower. Source: commons.wikimedia.org/wiki/File:SunflowerModel.svg

As we already noted, there is a recursive definition for \(n!\), for \(n\) in \(\mathbb{N}\), and we can use this definition to prove facts about the factorials. We can define \(0!=1\) and \(n!=n\cdot(n-1)!\) for \(n>0\). Do you see how the base case and the inductive case in an inductive proof can correspond to the two parts of the recursive definition?

Other sequences of numbers can also be defined recursively. For example, the famous Fibonacci sequence is the sequence of numbers \(f_0\), \(f_1\), \(f_2\), … , defined recursively by

\[\begin{split}\begin{align*} f_0 &= 0\\ f_1 &= 1\\ f_n &= f_{n-1}+f_{n-2} \text{for $n>1$}\\ \text{ Using this definition, we compute that }\\ f_2 &= f_1 + f_0 = 0 + 1 = 1\\ f_3 &= f_2 + f_1 = 1 + 1 = 2\\ f_4 &= f_3 + f_2 = 2 + 1 = 3\\ f_5 &= f_4 + f_3 = 3 + 2 = 5\\ f_6 &= f_5 + f_4 = 5 + 3 = 8\\ f_7 &= f_6 + f_5 = 8 + 5 = 13 \end{align*}\end{split}\]

and so on. Based on this definition, we can use induction to prove facts about the Fibonacci sequence. We can prove, for example, that \(f_n\) grows exponentially with \(n\), even without finding an exact formula for \(f_n\):

Theorem 3.12

The Fibonacci sequence, \(f_0\), \(f_1\), \(f_2\), … , satisfies \(f_n > \big(\frac{3}{2}\big)^{n-1}\), for \(n\ge6\).

Proof. We prove this by induction on \(n\). For \(n=6\), we have that \(f_n=8\) while \(1.5^{n-1}=1.5^5\), which is about \(7.6\). So \(f_n > 1.5^{n-1}\) for \(n=6\). Similarly, for \(n=7\), we have \(f_n=13\) and \(1.5^{n-1}=1.5^6\), which is about 11.4. So \(f_n > 1.5^{n-1}\) for \(n=7\).

Now suppose that \(k\) is an arbitrary integer with \(k>7\). Suppose that we already know that \(f_n>1.5^{n-1}\) for \(n=k-1\) and for \(n=k-2\). We want to show that the inequality then holds for \(n=k\) as well. But

\[\begin{split}\begin{align*} f_k &= f_{k-1}+f_{k-2}\\ &> 1.5^{(k-1)-1}+1.5^{(k-2)-1} & \text{(by the induction hypothesis)}\\ &= 1.5^{k-2}+1.5^{k-3}\\ &= (1.5)\cdot(1.5^{k-3}) + (1.5^{k-3})\\ &= (2.5)\cdot(1.5^{k-3})\\ &> (1.5^2)\cdot(1.5^{k-3}) & \text{(since $1.5^2=2.25$)}\\ &= 1.5^{k-1} \end{align*}\end{split}\]

This string of equalities and inequalities shows that \(f_k>1.5^{k-1}\). This completes the induction and proves the theorem.

□

3.7.1. Exercises

Exercise (1†)

Prove that the Fibonacci sequence, \(f_0\), \(f_1\), \(f_2\), … , satisfies \(f_n<2^n\) for all natural numbers \(n \geq 1\).

Exercise (2†)

Suppose that \(a_1\), \(a_2\), \(a_3\), … , is a sequence of numbers which is defined recursively by \(a_1=1\) and \(a_n=2a_{n-1}+2^{n-1}\) for \(n>1\). Prove that \(a_n=n2^{n-1}\) for every positive integer \(n\).