# 1.10 Recursive Definitions

Recursion occurs in programming when a subroutine is defined—partially, at least—in terms of itself. But recursion also occurs outside of program- ming. 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.

As already noted, there is a recursive definition for $$n!$$, for $$n$$ in $$\mathbb{N}$$. We can define $$0! = 1$$ and $$n! = n·(n−1)!$$ for $$n > 0$$. 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

$f_{0} = 0 \nonumber$

$f_{1} = 1 \nonumber$

$f_{n} = f_{n - 1} + f_{n-2} \text{ for } n>0$

Using this definition, we can compute that

$f_{2} =f_{1} +f_{0} =0+1=1 \nonumber$

$f_{3} =f_{2} +f_{1} =1+1=2 \nonumber$

$f_{4} =f_{3} +f_{2} =2+1=3 \nonumber$

$f_{5} =f_{4} +f_{3} =3+2=5 \nonumber$

$f_{6} =f_{5} +f_{4} =5+3=8 \nonumber$

$f_{7} =f_{6} +f_{5} =8+5=13 \nonumber$

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 1.17

The Fibonacci sequence, $$f_{0} , f_{1} , f_{2}$$ , . . . , $$f_{0}, f_{1}, f_{2},...,$$ satisfies $$f_{n} > (\frac{3}{2})^{n-1}, for \(n>6$$.

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 $$fn > 1.5^{n−1} \text{ 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} \text{ for } n=k−1 \text{ and for } n=k−2$$. We want to show that the inequality then holds for $$n = k$$ as well. But

$f_{k} = f_{k−1} + f_{k−2} \nonumber$

$> 1.5^{(k−1)−1} + 1.5^{(k−2)−1} \text{ (by the induction hypothesis) } \nonumber$

$= 1.5^{k−2} + 1.5^{k−3} \nonumber$

$= (1.5) · (1.5^{k−3}) + (1.5^{k−3}) \nonumber$

$= (2.5) · (1.5^{k−3})$

$> (1.5^{2}) · (1.5^{k-3}) \text{ (since 1.5^{2} = 2.25) }\nonumber$

$= 1.5^{k-1}$

This string of equalities and inequalities shows that $$f_{k} > 1.5^{k−1}$$. This completes the induction and proves the theorem.

### Exercises

1. Prove that the Fibonacci sequence, $$f_{0}, f_{1}, f_{2}$$, . . . , satisfies $$f_{n} < 2^{n}$$ for all natural numbers {n}.

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} =2_{a_{n}−1} +2^{n−1} \text{ for } n>1$$. Prove that $$a_{n} =n2^{n−1}$$ for every positive integer \(n).