1 Definition and notation

A sequence is an ordered collection of elements, usually numbers, arranged according to an indexing rule. In discrete mathematics, the position of each element matters as much as the element itself, so changing the order produces a different sequence. Sequences appear throughout mathematics because they provide a precise way to describe repeated processes, patterns, and counted arrangements.

1.1 Formal definition

Formally, a sequence can be viewed as a function whose domain is a discrete index set, most often the natural numbers. The value of the function at each index is called a term of the sequence. This perspective makes sequences compatible with the language of functions while preserving their ordered character.

1.2 Indexing and terms

The index identifies the location of a term in the sequence. Commonly, the first term is written as a1 or a0, depending on the chosen starting index. A sequence is determined not only by the values of its terms but also by the indexing convention, since the same list of values may be described differently under distinct starting points.

1.3 Finite and infinite sequences

A finite sequence has a fixed number of terms and ends after a last index. An infinite sequence continues without bound, with terms defined for all indices in the chosen domain. Finite sequences often arise in counting and enumeration, while infinite sequences are central in analysis and the study of long-term behavior.

1.4 Common notation

Sequences are often written in list form, such as a1, a2, a3, and so on, or by using ellipses to indicate continuation. Another common notation is {an}, which emphasizes the indexed family of terms. When the formula for the nth term is known, the sequence may be defined compactly by an expression involving n.

2 Types of sequences

Sequences are commonly classified by the rule that generates their terms. Some follow simple additive or multiplicative patterns, while others are defined recursively or alternate between values. These categories help describe their structure and make it easier to analyze their behavior.

2.1 Arithmetic sequences

An arithmetic sequence has a constant change from one term to the next. Each new term is obtained by adding the same value to the previous term, producing a linear pattern. Such sequences are among the simplest and most frequently studied in elementary discrete mathematics.

2.1.1 Common difference

The constant amount added between successive terms is called the common difference. If the difference is positive, the sequence increases steadily; if negative, it decreases. This uniform spacing gives arithmetic sequences a regular structure that is easy to recognize.

2.1.2 Explicit formula

An arithmetic sequence can be written using a closed formula for the nth term. If a1 is the first term and d is the common difference, then an depends linearly on n. This explicit form allows direct computation of any term without listing earlier values.

2.2 Geometric sequences

A geometric sequence changes by a constant multiplicative factor. Instead of adding the same number each time, each term is obtained by multiplying the previous term by a fixed ratio. These sequences frequently model repeated growth or decay.

2.2.1 Common ratio

The constant multiplier is called the common ratio. When the ratio exceeds 1, the terms typically grow in magnitude; when it lies between 0 and 1, the terms often shrink toward zero. Negative ratios produce alternating signs, which can create oscillating patterns.

2.2.2 Explicit formula

If a1 is the initial term and r is the common ratio, then the nth term of a geometric sequence is expressed as a power of r times the first term. This formula reveals the exponential nature of the sequence and makes it easy to evaluate distant terms.

2.3 Recursive sequences

Recursive sequences are defined by giving one or more starting values and a rule that expresses later terms in terms of earlier ones. They are especially useful when a sequence is naturally built from preceding information. Many important sequences in discrete mathematics are recursive.

2.3.1 Recurrence relations

A recurrence relation specifies how each term depends on previous terms. The dependence may involve one earlier term or several, and the rule may be linear or nonlinear. Recurrences are a central tool for modeling processes that evolve step by step.

2.3.2 Initial conditions

Initial conditions provide the starting values needed to generate the sequence from its recurrence. Without them, the relation alone may describe many possible sequences. The combination of a recurrence and initial conditions determines the sequence uniquely in typical cases.

2.4 Constant and alternating sequences

A constant sequence has the same value in every position. An alternating sequence switches between two or more values according to a fixed pattern, such as changing sign from term to term. Both types are simple examples that illustrate how sequences can encode regular repetition.

3 Representation of sequences

Sequences can be described in several ways, depending on the purpose of the discussion. A sequence may be written out term by term, given by a formula, defined recursively, or represented through generating functions. Each method highlights a different aspect of the same object.

3.1 Listing terms

The most direct representation is to list the terms in order. This approach is useful for short sequences and for displaying patterns visually. However, it becomes impractical for long or infinite sequences, where a compact rule is preferable.

3.2 Formula-based definition

A formula-based definition gives the nth term directly as a function of the index. This method is efficient when a simple closed form is available. It allows one to compute specific terms quickly and to study general properties using algebraic techniques.

3.3 Recurrence-based definition

A recurrence-based definition describes each term through earlier terms and initial values. This form is natural for processes that unfold iteratively. It is often easier to derive than a closed formula, especially when the sequence arises from a combinatorial or algorithmic rule.

3.4 Generating functions

A generating function encodes a sequence as coefficients of a formal power series. This representation transforms a sequence into an algebraic object that can be manipulated using techniques from combinatorics and algebra. Generating functions are especially useful for solving recurrences and deriving identities.

4 Properties of sequences

Sequences are studied not only by their definitions but also by the behavior of their terms. Important properties include whether the order of terms matters, whether the values increase or decrease, whether they remain within fixed bounds, and whether they repeat periodically.

4.1 Order and uniqueness of terms

The defining feature of a sequence is that each position corresponds to a specific term. Even if the same value appears more than once, its occurrences at different indices are distinct. This positional uniqueness distinguishes sequences from unordered sets.

4.2 Monotonicity

A sequence is monotonic if its terms never decrease or never increase. Increasing and decreasing sequences are common examples. Monotonicity is useful in studying long-term behavior because it often simplifies arguments about convergence and boundedness.

4.3 Boundedness

A sequence is bounded if all of its terms lie within a fixed range. Upper and lower bounds help describe how large or small the terms can become. Boundedness is especially important when analyzing infinite sequences, since it can limit possible growth.

4.4 Periodicity

A periodic sequence repeats its values after a fixed number of steps. The repeating block is called a period. Periodic sequences occur in alternating patterns, modular arithmetic, and other settings where repeated cycles are present.

5 Operations on sequences

Sequences can be combined and transformed in systematic ways. These operations create new sequences from old ones and are useful in both algebraic manipulation and modeling. They also help compare sequences with similar structure.

5.1 Addition and subtraction

Two sequences of the same indexing set can be added or subtracted term by term. The resulting sequence has terms formed by combining corresponding positions. This operation is often used to build new patterns from simpler ones.

5.2 Termwise multiplication

Termwise multiplication produces a sequence whose nth term is the product of the nth terms of two given sequences. This operation can reveal interactions between patterns, especially when one sequence describes growth and another describes scaling or masking.

5.3 Shifts and subsequences

A shift changes the starting index or moves the sequence forward by a fixed number of positions. A subsequence is formed by selecting terms according to a chosen rule, such as every other term or terms at increasing indices. These constructions are important in examining structure and long-term behavior.

5.4 Composition and transformation

Sequences may be transformed by applying a function to each term, or by combining the index with the terms in a new rule. Such transformations can change magnitude, sign, or growth rate. They are useful for generating related sequences with predictable properties.

6 Special sequences in discrete mathematics

Certain sequences occur so often in combinatorics, recurrence theory, and counting problems that they have become standard examples. These sequences are studied for their distinctive formulas, structural properties, and wide range of applications.

6.1 Fibonacci sequence

The Fibonacci sequence is one of the best-known recursive sequences. Each term is obtained by adding the two preceding terms, beginning from specified initial values. Its simple rule produces a rich structure that appears in many areas of mathematics.

6.1.1 Recursive structure

The recursive pattern of the Fibonacci sequence depends on the sum of the previous two terms. This two-step dependence makes it a classic example of a second-order recurrence relation. The sequence illustrates how a simple local rule can generate complex global behavior.

6.1.2 Closed-form expression

Although the Fibonacci sequence is defined recursively, it also has a closed-form expression. This formula expresses the nth term directly using algebraic constants and powers. Such a representation is valuable for theoretical analysis, even when the recursive definition is easier for computation.

6.2 Factorial sequence

The factorial sequence consists of values of n!, where each term is the product of the positive integers up to n. It grows very rapidly and is central in counting permutations and arrangements. The sequence begins with small values but increases faster than polynomial sequences.

6.3 Binomial coefficient sequence

Binomial coefficient sequences are formed from entries of Pascal’s triangle or from expressions of the form C(n, k) with one index fixed or varying. These sequences encode combinations and arise in algebraic expansions. Their symmetry and recurrence properties make them especially important in discrete mathematics.

6.4 Fibonacci-like and linear recurrence sequences

Many sequences follow the same general pattern as the Fibonacci sequence but with different coefficients or initial values. Linear recurrence sequences can involve one or several earlier terms combined linearly. They provide a broad framework for studying structured growth and counting phenomena.

Sequences are closely connected to several major ideas in discrete mathematics. They provide the terms that are added in series, the outputs generated by recurrences, and the numerical data underlying combinatorial formulas and discrete functions.

7.1 Series and summation

A series is formed by adding the terms of a sequence. Summation notation gives a compact way to express these totals. Sequences therefore serve as the starting point for many questions about accumulated values and convergence of sums.

7.2 Recurrences and difference equations

Recurrence relations describe sequences through relationships among successive terms, while difference equations study these relations in a systematic way. The two concepts overlap substantially in discrete mathematics. They are often used to model iterative processes and derive exact or approximate solutions.

7.3 Permutations and combinations

Sequences appear naturally in counting permutations and combinations. Ordered arrangements correspond directly to sequences, while combinatorial identities often produce sequences of numerical coefficients. This connection makes sequences a core tool in enumeration.

7.4 Functions from discrete domains

A sequence can be interpreted as a function defined on a discrete set such as the natural numbers. This viewpoint links sequence theory to general function theory and makes it easier to use mappings, transformations, and domain restrictions. It also clarifies why indexing is fundamental.

8 Applications

Sequences are used across mathematics and computer science to describe repeated steps, enumerate possibilities, and model changing quantities. Their simplicity makes them useful in both theoretical reasoning and practical computation.

8.1 Algorithm analysis

In algorithm analysis, sequences often describe the number of operations performed as input size changes. Recurrence relations are used to model recursive procedures and iterative algorithms. Studying these sequences helps estimate running time and resource usage.

8.2 Counting problems

Many counting problems produce sequences of integers that record the number of possible outcomes for each size or stage of a problem. Such sequences can reveal hidden patterns and lead to general formulas. They are a natural language for enumerative combinatorics.

8.3 Computer science and data structures

Sequences are fundamental in computing because arrays, lists, and many other data structures store ordered data. They also appear in memory access patterns, input streams, and generated test cases. Their ordered nature makes them ideal for representing stepwise processes.

8.4 Mathematical modeling

Sequences are used to model discrete-time phenomena, such as population counts, savings plans, or repeated measurements. They capture how a quantity changes from one stage to the next. Recursive models are especially common when the next state depends on earlier ones.

9 Advanced topics

Beyond basic definitions and examples, sequences support deeper study of limiting behavior, subsequences, and asymptotic growth. These topics are especially important when sequences are infinite or when their long-term pattern matters more than individual terms.

9.1 Convergence of sequences

A convergent sequence approaches a fixed value as the index becomes large. Convergence is a central concept in analysis, but it also has discrete analogues when studying long-term stability. Sequences that do not converge may still display other organized behaviors.

9.2 Limit behavior

Limit behavior concerns what happens to the terms of a sequence as the index grows. A sequence may approach infinity, oscillate, stabilize, or vary irregularly. Understanding this behavior helps classify sequences by their eventual tendencies.

9.3 Subsequence analysis

A subsequence is formed by choosing terms from a sequence in increasing index order. Studying subsequences can reveal patterns not immediately visible in the full sequence. Subsequence methods are useful for identifying convergence, divergence, and repeated structure.

9.4 Infinite sequences and asymptotics

Infinite sequences are examined not only term by term but also through their asymptotic growth. Asymptotic analysis compares how fast sequences increase, decrease, or approach a limit. This viewpoint is especially valuable in combinatorics, algorithmics, and discrete modeling.

</INTERNAL_LINK_CANDIDATES> Natural numbers (the standard discrete index set for sequences) Function (a rule assigning each index a term) Indexing (the assignment of positions in a sequence) Term (an individual element of a sequence) Finite sequence (a sequence with finitely many terms) Infinite sequence (a sequence with endlessly many terms) Arithmetic sequence (a sequence with constant additive change) Common difference (the fixed amount added in an arithmetic sequence) Explicit formula (a direct nth-term expression) Geometric sequence (a sequence with constant multiplicative change) Common ratio (the fixed multiplier in a geometric sequence) Recurrence relation (a rule defining terms from earlier terms) Initial conditions (starting values for a recursive sequence) Generating function (a power-series encoding of a sequence) Monotonicity (the property of always increasing or decreasing) Boundedness (the property of staying within fixed limits) Periodicity (repetition of terms after a fixed interval) Subsequence (a sequence formed by selected terms of another) Convergence (approach of a sequence to a limit) Asymptotics (description of long-term growth behavior)