Recurrence relations

Introduction to Recurrence Relations

• Recurrence relations model scenarios where the current term is dependent on previous terms. They are often used in combinatorics, and several techniques can be used to solve them.
• The ‘initial conditions’ are the given terms at the start: it’s essential to take these into account when solving recurrence relations.

First Order Linear Recurrence Relations

• Recurrence relations, where each term depends on the term before, are called first-order linear recurrence relations.
• These relations can be solved using methods such as iterating - progressing manually through each term - and finding the common difference or ratio.
• A first order linear recurrence relation is called homogeneous if the right-hand side is zero, where there’s no term independent of the previous term(s).

Second Order Linear Recurrence Relations

• A second-order linear recurrence relation is one where the current term depends on the two terms before.
• Sometimes using generating functions or characteristic equations can solve second order relations.
• A second order linear recurrence relation is homogeneous if the right-hand side is zero, where term(s) are not depending on the previous term(s).

Non-linear Recurrence Relations

• Non-linear recurrence relations contain products of earlier terms and possibly the current term. They’re much more complex to solve, and may require advanced techniques or software.
• Cobwebbing and staircasing diagrams can be used to understand the evolution and stability of non-linear recurrence relations.