ABSTRACT
Our introduction to recursion is the Fibonacci sequence, which is 1,1,2,3,5,8, 13, . . . and is defined by Fn = Fn−1 + Fn−2. There are lots of interesting identities one can prove about the Fibonacci sequence (just as we saw there are for binomial coefficients). Many of these can be proven by induction-as foreshadowed in Chapter 4, this proof technique is pervasive.
