Mathematics - Discrete Mathematics - Sequences and Recurrence Relat...

Introduction

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

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).

Terms

A commonly used representation of the terms is:

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

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

Note: Having the 0^th 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 a₁ as the first one is also feasible, but it should be mentioned in the sequence definition, in some way:

Definition

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

A closed formula defines the n^th 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.

RESOURCES:

References

Images

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

Block diagrams and other visualizations were made using draw.io.

Previous articles of the series

Introduction → Discrete Mathematics, Why Discrete Math, Series Outline
Sets → Set Theory, Sets (Representation, Common Notations, Cardinality, Types)
Set Operations → Venn Diagrams, Set Operations, Properties and Laws
Sets and Relations → Cartesian Product of Sets, Relation and Function Terminology (Domain, Co-Domain and Range, Types and Properties)
Relation Closures → Relation Closures (Reflexive, Symmetric, Transitive), Full-On Example
Equivalence Relations → Equivalence Relations (Properties, Equivalent Elements, Equivalence Classes, Partitions)
Partial Order Relations and Sets → Partial Order Relations, POSET (Elements, Max-Min, Upper-Lower Bounds), Hasse Diagrams, Total Order Relations, Lattices
Combinatorial Principles → Combinatorics, Basic Counting Principles (Additive, Multiplicative), Inclusion-Exclusion Principle (PIE)
Combinations and Permutations → Factorial, Binomial Coefficient, Combination and Permutation (with / out repetition)
Combinatorics Topics → Pigeonhole Principle, Pascal's Triangle and Binomial Theorem, Counting Derangements
Propositions and Connectives → Propositional Logic, Propositions, Connectives (∧, ∨, →, ↔ and ¬)
Implication and Equivalence Statements → Truth Tables, Implication, Equivalence, Propositional Algebra
Proof Strategies (part 1) → Proofs, Direct Proof, Proof by Contrapositive, Proof by Contradiction
Proof Strategies (part 2) → Proof by Cases, Proof by Counter-Example, Mathematical Induction