submited by

Style Pass

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

F_{n+2} = F_{n+1} + F_{n}

where n is a subscript varying over all positive integers.

The question is: if we are given initial conditions F_{1} = 1 and F_{2} = 1, what is F_{n} (for general non-negative integer n)?

Read more win-vector.c...