Recurrence relationships

Understanding Recurrence Relationships

  • Recurrence relationships also known as recurrence relations, sequences or recursions, deal with functions whose output for a certain input relies on the results from a same function, but with different inputs.

  • In mathematical terms, a recurrence relationship can be defined as a set of rules that defines a sequence based on terms that have come before.

  • These relationships can be applied to model situations where the current state of a system is dependent on its previous states, such as population growth, interest compounding, and many concepts in computer science.

Formulating Recurrence Relationships

  • A basic first order recurrence relationship is of the form aₙ = f(aₙ₋₁), where aₙ is the output, f represents the function, and aₙ₋₁ is the predecessor input.

  • Higher order relationships involve more earlier terms. For example, the second order recurrence relationship aₙ = f(aₙ₋₁, aₙ₋₂) depends on the two previous terms.

Solving Recurrence Relationships

  • Solving a recurrence relationship can mean finding an expression for the n-th term in the form of an explicit formula that doesn’t rely on previous terms, or finding the limit of the sequence as n approaches infinity, if it exists.

  • You might need to use mathematical induction, or other mathematical transformations to get an explicit solution.

  • Sometimes, however, it may not be possible to find an explicit solution. In such cases, you may seek an algorithmic solution that allows you to compute the sequence efficiently.

Applications of Recurrence Relationships

  • Understanding recurrence relationships is vital in fields such as finance and computer science where calculations depend on previous results.

  • In computer science, they are commonly used in algorithms that exploit the repetition of a problem to create efficient solutions, such as in dynamic programming and divide-and-conquer algorithms.

Key Points to Remember

  • Recurrence relationships define a sequence based on preceding terms, and solving them can involve finding explicit formulas for terms or calculating their limits.

  • Mastering the solution of recurrence relationships provides a powerful tool for problem solving in mathematics and its applications in various fields. As with any mathematical concept, the key to developing this skill lies in consistent practice.