The tutor introduces a first degree non-homogeneous recurrence relation.

An equation that describes a list of terms by a relationship among consecutive ones is called a recurrence relation. Some people call it a difference equation. An example:

17a_n+1 – 5a_n = 11

The above is a first degree, nonhomogeneous recurrence relation. First degree means that the next term only depends on the current one. Nonhomogeneous means that there is a value in the equation that is independent from the sequence terms; in the case above, it’s 11. A homogeneous recurrence relation looks like

10a_n+1 – 7a_n = 0

Example:

Solution:

Note the sequence starts at the zeroth term: a₀ = 12. With n=0, the relation becomes

2a₁ – a₀ = 3

which leads to

2a₁ – 12 = 3

2a₁ = 15

a₁ = 7.5

Setting n=1, we have

2a₂ – a₁ = 3

Then, putting in 7.5 for a₁, we have

2a₂ – 7.5 = 3

which yields a₂ = 5.25

Continuing the same way, we come up with

and so on.

Arriving at, for instance, the 20th term using the method above would be laborious. The general solution to a recurrence relation means a formula that can get the nth term, a_n, from just inputting the specific n. For example, if you need the 20th term, you can just substitute 20 for n in the general solution and calculate a₂₀.

Next post I’ll show how to find the general solution to the recurrence relation of today’s example.

Source:

Grimaldi, Ralph P. Discrete and Combinatorial Mathematics. Don Mills: Addison-
  Wesley, 1994.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.