Keo's Notes

LEGACY Recurrence Relations

3 min read

Definition

A Recurrence Relation describes a term of a sequence as in terms of previous terms. They can use varying amounts of previous terms (go back further) and you can describe this by the order which is defined as the difference between the lowest & highest subscript. They are strongly related to Differential Equations and are often solved in the same/similar ways as recurrence relations are basically discrete differential equations

A-Level Further Pure 2

First Order Recurrence Relations

First order linear recurrence relations are in the form

Homogenous

If then the equation is homogeneous and the general solution is

This is proved by back substitution or more rigorously with Proof by Induction

Non-Homogenous

For , the general solution is

To find the general solution to where is , Where is the solution to which is and is a particular solution to the equation.

Form of Form of

Solving Second Order Recurrence Relations

A 2nd order linear recurrence relation can be written in the form

If and are particular solutions to a linear recurrence relation then is a solution.

Homogenous

The general solution to a homogeneous 2nd order linear recurrence relation of depends on the auxiliary equation

This quadratic leads to 3 cases.

  • The auxiliary equation has 2 real root
  • The auxiliary equation has 1 repeated root .
  • The auxiliary equation has two complex conjugate roots

Non-Homogeneous

For non-homogeneous the general solution is

Form of Form of particular solution
with
, with
with
with
with
with
with
with
with
(When or you have to multiply the by so otherwise there will be redundancy and overlap and and are supposed to be linearly independent. This stacks if then multiply by twice which is the same as multiplying by )

Proving closed forms

You can rigorously prove a closed for by using Proof by Induction. This will require multiple base cases if the order of the relationship is . In general for an ordered recurrence relation, you will need to prove the base case for the first terms

Graph View

Backlinks