Discrete Mathematics cheatsheet

Sequences

A sequence is an ordered list of numbers, where each number is called a term. It can be represented as, whereis 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.

whereis the common difference.

Geometric Sequences

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

whereis 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 limitif, for any, there exists a natural numbersuch 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 asand 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 theterms astends to infinity:

Arithmetic Series

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

whereis 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 seriesconverges if:
  1. is monotonically decreasing.
  2. .

Power Series

A power series has the form:

whereis the center of the series.

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

Theorems

Theorem of Convergence of Series

A seriesconverges if the sequence of the partial sumsconverges to a limit.

Convergence Criteria

• Comparison Criterion: Ifandconverges, thenalso converges.
• Root Criterion: For:

Abel’s Theorem

Ifconverges andis monotonically decreasing and converges to 0, thenconverges.

Integers and Number Theory

Divisibility

Prime Numbers

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

Composite Numbers

A numberis composite if it has more than two divisors.

Fermat’s Little Theorem

Ifis a prime number andis 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 integersand:

Properties of GCD

• Non-negativity:.
• Commutativity:.
• Divisibility Property: If, thendivides any linear combination ofand.

Euclidean Algorithm

To find the GCD of two numbersand:

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 integersand:

Properties of LCM

• Non-negativity:andonly ifor.
• Commutativity:.

Relationship Between GCD and LCM

Modular Arithmetic

Modular Congruence

Properties

Ifand, then: ---

Chinese Remainder Theorem

Ifare pairwise coprime integers, then for any system of congruences:

There exists a unique solution, where.