Sequences and Summations in Discrete Mathematics

Introduction to Sequences

Definition of Sequences

  • A sequence is defined as a function from a subset of integers (typically {0, 1, 2,…} or {1, 2, 3,…}) to a set S.

  • The notation an is used to denote the image of the integer n, where an is referred to as a term of the sequence.

  • Sequences can be finite or infinite, depending on the number of terms they contain.

Example of a Sequence

  • Consider the sequence defined by an = 1/n.

  • The first few terms of this sequence are: a1 = 1, a2 = 1/2, a3 = 1/3, a4 = 1/4, ...

  • This sequence converges to 0 as n approaches infinity, illustrating the concept of limits in sequences.

Types of Sequences

Geometric Progression

  • A geometric progression is a sequence of the form a, ar, ar², …, arⁿ, where a is the initial term and r is the common ratio.

  • It serves as a discrete analogue of the exponential function f(x) = ar^x.

  • Example sequences include:

  • {bn} with bn = (-1)ⁿ: -1, 1, -1, ... (a = -1, r = -1)

    • {cn} with cn = 10·5ⁿ: 10, 50, 250, ... (a = 10, r = 5)

    • {dn} with dn = 2·(1/3)ⁿ: 2, 2/3, 2/9, ... (a = 2, r = 1/3)

Arithmetic Progression

  • An arithmetic progression is defined as a sequence of the form a, a+d, a+2d, …, a+nd, where a is the initial term and d is the common difference.

  • This type of sequence is a discrete analogue of the linear function f(x) = dx + a.

  • Example sequences include:

  • {sn} with sn = -1 + 4n: -1, 3, 7, 11, ... (a = -1, d = 4)

    • {tn} with tn = 7 - 3n: 7, 4, 1, -2, ... (a = 7, d = -3)

Strings and Their Applications

Definition of Strings

  • In computer science, sequences of the form a1, a2, …, an are referred to as strings.

  • A string is denoted by concatenating its terms, e.g., a1a2…an, and its length is the number of terms it contains.

  • The empty string, denoted by λ, has no terms and a length of zero.

  • Example: The string 'abcd' is a string of length four.

Summation Notation

Understanding Summation

  • Summation notation is represented as Σ, which denotes the sum of a sequence of terms.

  • The index of summation (j) indicates the current term being summed, while m and n represent the lower and upper limits, respectively.

  • The expression Σ from j=m to n of a_j = a_m + a_(m+1) + ... + a_n.

Example Exercises

  • Express the sum of the first 100 terms of the sequence {an}, where an = 1/n for n=1, 2, 3,...

  • Calculate the value of Σ from j=1 to 8 of (j-1)(1).

  • Determine the value of Σ from i=1 to 4 of Σ from j=1 to 3 of 1.