Functions, Sequences, and Sums

Functions encode assignment. A function does not merely relate two sets; it assigns exactly one output to each input. Sequences are functions whose domains are ordered integer sets, and summations are compact notation for adding indexed families of values. Together these ideas support algorithm analysis, counting, recurrence relations, and probability.

This page connects three habits that appear throughout discrete mathematics: describe a rule, list the values generated by the rule, and add or transform those values. A careful distinction between domain, codomain, and range prevents many mistakes when proving injectivity, surjectivity, and bijectivity.

Definitions

A function $f:A\to B$ assigns each element of $A$ exactly one element of $B$. The set $A$ is the domain, $B$ is the codomain, and the range or image is

$$\operatorname{range}(f)=\{f(a):a\in A\}.$$

A function is one-to-one or injective if distinct inputs have distinct outputs. Equivalently,

$$f(a)=f(b)\to a=b.$$

It is onto or surjective if every element of the codomain is hit:

$$\forall b\in B\,\exists a\in A(f(a)=b).$$

It is a bijection if it is both one-to-one and onto. A bijection has an inverse function $f^{-1}:B\to A$.

The composition of $f:A\to B$ and $g:B\to C$ is $g\circ f:A\to C$, defined by

$$(g\circ f)(a)=g(f(a)).$$

A sequence is a function from a subset of the integers, usually $\mathbb{N}$ or $\mathbb{Z}^+$, into a set. Terms may be written $a_0,a_1,a_2,\dots$ or $a_1,a_2,\dots$. A sequence can be given by an explicit formula, such as $a_n=2n+1$, or recursively, such as $a_0=1$ and $a_n=2a_{n-1}+1$.

A summation uses sigma notation:

$$\sum_{i=m}^{n} a_i=a_m+a_{m+1}+\cdots+a_n.$$

If the upper index is smaller than the lower index, many authors define the sum as $0$, but this convention should be stated when used.

Key results

For finite sets with $\vert A\vert =\vert B\vert$, a function $f:A\to B$ is one-to-one if and only if it is onto. Proof idea: if $f$ is one-to-one, the $\vert A\vert$ distinct inputs produce $\vert A\vert =\vert B\vert$ distinct outputs, so every element of $B$ appears. Conversely, if $f$ is onto and two different inputs mapped to the same output, then $\vert A\vert$ inputs would produce fewer than $\vert B\vert$ distinct outputs, contradicting onto-ness.

Compositions preserve injectivity and surjectivity in predictable ways. If $f$ and $g$ are injective, then $g\circ f$ is injective. If $f$ and $g$ are surjective, then $g\circ f$ is surjective. If both are bijections, then $g\circ f$ is a bijection and

$$(g\circ f)^{-1}=f^{-1}\circ g^{-1}.$$

Useful summation formulas:

$$\begin{aligned} \sum_{i=1}^{n} i &= \frac{n(n+1)}{2},\\ \sum_{i=1}^{n} i^2 &= \frac{n(n+1)(2n+1)}{6},\\ \sum_{i=0}^{n} ar^i &= a\frac{r^{n+1}-1}{r-1}\quad(r\ne1),\\ \sum_{i=0}^{n} r^i &= \frac{r^{n+1}-1}{r-1}\quad(r\ne1). \end{aligned}$$

The first formula has a classic pairing proof. Write $S=1+2+\cdots+n$ and also $S=n+(n-1)+\cdots+1$. Adding vertically gives $2S=n(n+1)$, so $S=n(n+1)/2$.

Visual

Property	Finite check	Infinite proof pattern	Common failure
injective	no repeated outputs	assume $f(a)=f(b)$, prove $a=b$	two inputs share one output
surjective	range equals codomain	solve $f(a)=b$ for arbitrary $b$	codomain has an unreachable value
bijective	both checks pass	prove injective and surjective, or build inverse	range confused with codomain
sequence formula	test first terms	prove by induction if recursive	off-by-one index

Worked example 1: Decide whether a function is a bijection

Problem. Let $f:\mathbb{Z}\to\mathbb{Z}$ be $f(n)=3n-2$. Determine whether $f$ is injective, surjective, and bijective.

Method.

1. Check injectivity. Suppose $f(a)=f(b)$.

$$\begin{aligned} 3a-2&=3b-2\\ 3a&=3b\\ a&=b. \end{aligned}$$

So $f$ is injective.

2. Check surjectivity. To be onto $\mathbb{Z}$, every integer $y$ must have an integer preimage $n$ satisfying

$$3n-2=y.$$

3. Solving gives

$$n=\frac{y+2}{3}.$$

4. This is not always an integer. For example, if $y=0$, then $n=2/3$.

Checked answer. The function is injective but not surjective onto $\mathbb{Z}$. Therefore it is not a bijection. If the codomain were changed to the set $\{m\in\mathbb{Z}:m\equiv1\pmod3\}$, then the same formula would become onto that codomain.

Worked example 2: Evaluate and verify a summation

Problem. Evaluate

$$\sum_{i=2}^{8}(3i-1).$$

Method.

1. Separate the sum using linearity:

$$\sum_{i=2}^{8}(3i-1)=3\sum_{i=2}^{8}i-\sum_{i=2}^{8}1.$$

2. Compute the integer sum:

$$\sum_{i=2}^{8}i=\sum_{i=1}^{8}i-1=\frac{8\cdot9}{2}-1=36-1=35.$$

3. Count the number of terms from $2$ through $8$:

$$8-2+1=7.$$

4. Substitute:

$$3\cdot35-7=105-7=98.$$

5. Direct expansion checks the result:

$$5+8+11+14+17+20+23=98.$$

Checked answer. The summation equals $98$. The direct expansion agrees with the formula calculation, which also verifies the endpoint count.

Code

def is_injective(domain, f):
    seen = {}
    for x in domain:
        y = f(x)
        if y in seen and seen[y] != x:
            return False
        seen[y] = x
    return True

def is_surjective(domain, codomain, f):
    return {f(x) for x in domain} == set(codomain)

def arithmetic_sum(start, stop, rule):
    return sum(rule(i) for i in range(start, stop + 1))

sample_domain = range(-10, 11)
sample_codomain = range(-20, 21)
print(is_injective(sample_domain, lambda n: 3 * n - 2))
print(is_surjective(sample_domain, sample_codomain, lambda n: 3 * n - 2))
print(arithmetic_sum(2, 8, lambda i: 3 * i - 1))

Finite sampling cannot prove a statement over all integers, but it can quickly expose repeated outputs, missing codomain values, and indexing errors in a proposed formula.

Common pitfalls

• Confusing codomain and range. Surjectivity is about hitting every element of the codomain, not merely describing the outputs that occur.
• Claiming a function is not injective without giving two different inputs with the same output.
• Proving surjectivity by solving $f(x)=y$ but forgetting to show the solution lies in the domain.
• Reversing composition order. $(g\circ f)(x)$ means apply $f$ first, then $g$.
• Dropping endpoints in a summation. The number of integers from $m$ through $n$ is $n-m+1$.
• Treating recursive and explicit formulas as interchangeable before proving they define the same sequence.

For injectivity proofs, the equation method is usually best: assume $f(a)=f(b)$ and algebraically force $a=b$. For functions defined by cases, every pair of cases must be considered or an inverse argument must cover them all at once. A graph or table can disprove injectivity on a finite domain, but an infinite-domain proof requires a general argument.

For surjectivity proofs, start with an arbitrary element $y$ of the codomain and solve $f(x)=y$. The last step is crucial: verify that the proposed $x$ belongs to the domain. For example, $f:\mathbb{Z}\to\mathbb{Z}$ given by $f(n)=2n$ is not onto $\mathbb{Z}$ because solving $2n=y$ gives an integer $n$ only when $y$ is even.

Composition changes domains and codomains, so check that the output of the first function lies in the domain of the second. If $f:A\to B$ and $g:C\to D$, then $g\circ f$ is defined only when $f(a)\in C$ for all relevant $a$. In textbook examples this condition is often arranged silently, but in applications it is a real type check.

Summation notation is compact but not magical. Before applying a formula, compare the index range to the formula's range. A formula for $\sum_{i=1}^{n}i$ does not directly evaluate $\sum_{i=4}^{n}i$ until the missing first terms are subtracted. For arithmetic expressions, linearity lets constants move outside sums and lets sums split term by term.

Sequences also have indexing conventions. Some begin at $0$ and some at $1$. Fibonacci numbers, array positions, and recurrence initial conditions can shift formulas by one. Always calculate the first two or three terms from the definition and compare them with the proposed closed form.

A compact way to audit a function problem is to ask four questions: what is the domain, what is the codomain, what is the rule, and what is the range? Many wrong injectivity or surjectivity claims come from answering only the rule question. The same formula can define different functions when the domain or codomain changes.

For sums, write the first and last terms before applying a formula. This exposes endpoint mistakes and confirms the number of terms. If the summand has a shift, such as $a_{i-1}$ or $2i+3$, expanding a few terms usually makes the needed substitution clear before any algebra begins.

When proving two formulas define the same sequence, do not rely only on visual pattern matching. Show that they have the same initial values and satisfy the same recurrence, or derive one expression from the other algebraically. This is the sequence version of proving two functions equal by checking all inputs.

For finite domains, a table can reveal the range, collisions, and missing codomain values at once. For infinite domains, the table becomes evidence only; the proof must use algebra, inequalities, or a constructed inverse to cover all possible inputs.

The distinction between evidence and proof is especially important when a pattern appears in the first few terms of a sequence.

Connections

• Sets and set operations supplies domains, codomains, Cartesian products, and power sets.
• Cardinality compares set sizes using bijections.
• Recurrence relations studies recursively defined sequences in depth.
• Counting principles uses functions to model assignments and choices.
• Algorithms and complexity uses sums to count loop work.