Subsection 8.10.6 Recursion and Induction
Sometimes the easiest way to define an object is in terms of other (generally smaller) objects just like it. We call such definitions recursive.
Recursive definitions generally have a structure that is very similar to the structure of an inductive proof:
We begin by writing a simple (nonrecursive) definition of a small number of base cases.
Then we write a general definition, useful for all other values, that constructs values from others that are closer to the base case(s).
We’ve already seen several recursive definitions. We just didn’t call them that.
Recall that we defined the Fibonacci sequence as follows, using two base cases:
f1 = 1, (i.e., the first element of the sequence is 1) f2 = 1, (and so is the second element) for all k > 2, fk+1 = fk + fk-1 (other elements are computed from the two previous ones) The first several terms of the sequence are 1, 1, 2, 3, 5, 8, 13.
Because recursive definitions and inductive proofs share the same structure, it’s often the case that the most straightforward way to prove claims about objects that have been defined recursively is by induction.
Recall that we’ve already proved the following claim about the Fibonacci sequence: For all n 1: (∑_(i=1)^n▒〖f_i^2)〗= f_n f_(n+1) Also, in an optional section we used (strong) induction to prove: For all n 1: f_n (3/2)^(n-2)