Solving Recurrence Relations – Win Vector LLC
A neat bit of “engineering mathematics” is solving recurrence relations. The solution method falls out of the notation itself, and harkens back to a time where formal sums were often used in place of vector subscript notation.
Unfortunately the variety of such solutions is small enough to allow teaching by memorization. In this note I try to avoid memorization, and motivate the methodology. I feel this is facilitated by separating a number of often smeared together representations (formulas, sequences, vectors, linear checks, characteristic polynomial, and polynomial check families) into distinct realizations. We are also going to emphasize calculating and confirming claims in Python.
A simple form of the recurrence problem is to write down a general solution for a subscripted family of linear equations such as the following
Fn+2 = Fn+1 + Fn
where n is a subscript varying over all positive integers.
The question is: if we are given initial conditions F1 = 1 and F2 = 1, what is Fn (for general non-negative integer n)?
