Recurrence relations
A rule tells you how each term grows out of the ones before it. When can you skip the steps and name the hundredth term directly?
Where you are 6 inside
What this area is about
A recurrence relation is a rule that builds each term of a sequence from earlier terms, together with enough starting values to begin. It fixes every term, but only one at a time. This area is about running such rules, finding them in counting problems, and, for one well-behaved family, replacing them with a closed formula proved correct for every n.
How these fit together
Running a rule. Generating a sequence from a rule produces terms from the starting values and looks at what comes out. Closed form versus recursive form compares a step rule with a formula in n, for rules that look back one term.
The model example. The Fibonacci sequence, F_1 = F_2 = 1 and F_n = F_{n-1} + F_{n-2} for n \ge 3, collects its identities and proves them by induction.
Building rules. Setting up a recurrence from a counting problem sorts objects of size n by their first or last piece.
Solving rules. For a_n = c_1 a_{n-1} + c_2 a_{n-2} with constants c_2 \ne 0, solving a two-term recurrence handles two distinct characteristic roots, and repeated roots handles the double root, when c_1^2 + 4c_2 = 0.
A path through it
Generating a sequence from a rule comes before Fibonacci, and Fibonacci before setting up recurrences from counting. Closed versus recursive form comes before solving a two-term recurrence, which also needs proof by induction; repeated roots come last.
Finish here and you can set up a recurrence for a count, and turn a two-term linear rule with constant coefficients into a closed formula proved for every n.