Discrete Mathematics CheatSheet

Sequences

A sequence is an ordered list of numbers, where each number is called a term. It can be represented as , where is a positive integer indicating the position of the term in the sequence.

Definition

A sequence is defined as:

Example: The sequence of natural numbers:

Types of Sequences

Arithmetic Sequences

They are characterized by having a constant difference between consecutive terms.

where is the common difference.

Geometric Sequences

They are characterized by having a constant ratio between consecutive terms.

where is the common ratio.

Alternating Sequences

They are characterized by alternating between two or more values.

Example: produces the sequence

Monotonic Sequences

• Monotonically Increasing:
• Monotonically Decreasing:

Convergence and Divergence

Convergence

A sequence converges to a limit if, for any , there exists a natural number such that for all :

Divergence

A sequence diverges if it does not converge to a finite limit.

Series

A series is the sum of the terms of a sequence. It is generally denoted as and can be represented as follows:

Types of Series

Finite Series

Sum of a finite number of terms.

Example:

Infinite Series

Sum of infinitely many terms. It is defined as the limit of the sum of the terms as tends to infinity:

Arithmetic Series

The sum of an arithmetic series can be calculated using the formula:

where is the -th term.

Geometric Series

The sum of a geometric series, where , can be calculated as:

Alternating Series

Alternating series have terms that change sign. An important criterion for convergence is the Leibniz Criterion:

• An alternating series converges if:
  1. is monotonically decreasing.
  2. .

Power Series

A power series has the form:

where is the center of the series.

Convergence is determined in the interval of convergence, given by the radius :

Theorems

Theorem of Convergence of Series

A series converges if the sequence of the partial sums converges to a limit.

Convergence Criteria

• Comparison Criterion: If and converges, then also converges.
• Root Criterion: For :

Abel’s Theorem

If converges and is monotonically decreasing and converges to 0, then converges.

Integers and Number Theory

Divisibility

Prime Numbers

A number is prime if it is only divisible by 1 and itself.

Composite Numbers

A number is composite if it has more than two divisors.

Fermat’s Little Theorem

If is a prime number and is an integer such that , then:

Greatest Common Divisor

The Greatest Common Divisor (GCD) of two or more integers is the largest integer that divides all those numbers without leaving a remainder.

For two integers and :

Properties of GCD

• Non-negativity: .
• Commutativity: .
• Divisibility Property: If , then divides any linear combination of and .

Euclidean Algorithm

To find the GCD of two numbers and :

Least Common Multiple (LCM)

The Least Common Multiple of two or more integers is the smallest positive integer that is a multiple of all those numbers.

For two integers and :

Properties of LCM

• Non-negativity: and only if or .
• Commutativity: .

Relationship Between GCD and LCM

Modular Arithmetic

Modular Congruence

Properties

If and , then: - - -

Chinese Remainder Theorem

If are pairwise coprime integers, then for any system of congruences:

There exists a unique solution , where .