7.1: Recursively Defined Sequences
Read Section 4, "Recursion Equations," up to example 27 on pages DT-42 - DT-46.
Notice that the definition of induction, in "Unit IS: Induction, Sequences and Series," is in terms of A(n), an assertion dependent on n. The A(n), n = 1, ..., n, ... is a sequence. In induction, A(n-1) is used to prove A(n). If A(n) is defined using A(n - 1), the sequence is recursively defined. Thus, induction and recursion both exploit a relationship between A(n) and A(n-1).
Given a recursive relation, the terms of its recursively defined sequence are computed by evaluating the relation for the base value, say n = 1, then evaluating it for successive values of n.
Given a recursive equation, also called a recursive relation, Theorem 7 on page DT-43 of the reading in Subunit 7.1 tells us how to verify a solution for it.
Let f(n) be an explicit formula for the nth term, An, of a sequence and assume that f(n) = A bn + K = A bn + K + Kb - Kb = A bn + Kb + K - Kb = b (A bn-1 + K) + K ( 1 - b) = b f(n - 1) + K(1 - b). Thus, f(n) = b f(n - 1) + C, a recursive equation, i.e. relation.
For the Fibonacci numbers, see theorem 9 and example 29 on pages DT-48 - DT-49. Example 29 starts with the sequence, F0 = F1 = 1, Fk = Fk -1 + Fk -2, and develops a formula for Fn which does not utilize an earlier F in the sequence.
For the Towers of Hanoi problem, see example 11 on pages DT-18 - DT-19.
This example solves a famous puzzle with a recursive solution, namely a solution for n discs in terms of a solution for n-1 and 1 discs.
This reading presents an alternative illustration of the use of a recursive equation to solve the Tower of Hanoi problem. Read Section 1 on pages 1 - 5.