Mathematics - Discrete Mathematics - Sequences and Recurrence Relations

in STEMGeeks2 years ago

[Image 1]


Hey it's a me again @drifter1!

Today we continue with Mathematics, and more specifically the branch of "Discrete Mathematics", in order to get into Sequences and Recurrence Relations.

So, without further ado, let's get straight into it!


Sequences are ordered lists of numbers. So, they are different from usual sets, where the order mostly doesn't matter. The sequence of all natural numbers is thus different from the set of all natural numbers (N).


A commonly used representation of the terms is:

The entire sequence is usually represented by an . Of course, the letter a can be easily replaced with any other letter.

Sequences usually starts from term a0. The subscript is the index of the number in the sequence. So, a0 is the 0th term of the sequence.

Note: Having the 0th term be the first one in the sequence may be a little bit confusing (maybe not for computer scientists). If it's too confusing, using a1 as the first one is also feasible, but it should be mentioned in the sequence definition, in some way:


Sequences are commonly specified using functions. These are either closed formulas or recursive definitions.

A closed formula defines the nth term of the sequence only in terms of n.

For example:

So, the term at index n = 3 is simply:

In recursive definitions (or relations) previous terms of the sequence are considered as well. Initial values need to be provided for the first terms of such sequences.

A widely-known recursive sequence is the Fibonacci sequence:

where each term is the sum of the two previous terms:

Arithmetic Sequences

If the terms differ only by a constant then the sequence is said to be arithmetic. Such sequences can be represented with either definition:

In these d is the difference between the terms and a the initial term of the sequence.

Geometric Sequences

If the ratio between successive terms is constant then the sequence is called geometric.

where r is the common ratio and a is the initial term.

Solving Recurrence Relations

Usually, sequences are easier to define in a recursive way. But, there's a way to convert them into closed formulas. This is basically a form of "solving" them. Some can be solved through "iteration" and "telescoping" while others require more complicated methods.

First of all, recurrence relations are basically difference equations with an order equal to the difference between the highest and lowest indices of the terms. These relations are solved by finding the roots of characteristic polynomials.

Solving the polynomial can easily become quite complicated...

For example, a recurrence relation of the form:

can be solved through the characteristic polynomial:

The roots of the equation:

result in the solution of the recurrence relation, which is:

The constants a and b are determined from the initial conditions.

Recurrence relations of this form are linear homogeneous recurrence relations with constant coefficients.






Mathematical equations used in this article, have been generated using quicklatex.

Block diagrams and other visualizations were made using

Previous articles of the series

Final words | Next up

And this is actually it for today's post!

Next time we will continue on with an Introduction to Probability Theory...

See ya!

Keep on drifting!

Posted with STEMGeeks