Monotonicity and boundedness
Learning Objectives
- Define increasing, non-decreasing, decreasing, non-increasing, and monotone sequences.
- Define bounded above, bounded below, and bounded sequences.
- Distinguish strict from weak (non-strict) monotonicity.
- Prove and apply the propagation of monotonicity across non-adjacent indices.
Motivation
The previous two lessons told us what a sequence is and how to specify one. Now we begin to classify sequences by their behaviour, so that we can speak about whole families of them at once.
Two of the most basic properties concern direction and range. A sequence may increase, decrease, or do neither. Its terms may stay within a fixed interval, or they may wander out to arbitrary values. These two questions — which way does it move, and how far can it go — are the gateway to almost every later notion in the theory of sequences: limits, convergence, monotone convergence, the comparison of growth rates, and the analysis of recursive procedures.
Monotone sequences
Let \((a_n)_{n \in \mathbb{N}}\) be a sequence of real numbers. We say that \((a_n)\) is:
non-decreasing (or weakly increasing) if \(a_n \leq a_{n+1}\) for every \(n \in \mathbb{N}\);
strictly increasing if \(a_n < a_{n+1}\) for every \(n \in \mathbb{N}\);
non-increasing (or weakly decreasing) if \(a_n \geq a_{n+1}\) for every \(n \in \mathbb{N}\);
strictly decreasing if \(a_n > a_{n+1}\) for every \(n \in \mathbb{N}\).
A sequence that satisfies any one of these four conditions is called monotone. If it is either strictly increasing or strictly decreasing, it is called strictly monotone.
Examples of monotone sequences
The natural numbers \(a_n = n\) are strictly increasing, since \(n < n+1\) for every \(n\).
The reciprocals \(a_n = \dfrac{1}{n}\) for \(n \geq 1\) are strictly decreasing: for each \(n \geq 1\) we have \(\dfrac{1}{n+1} < \dfrac{1}{n}\).
The constant sequence \(a_n = 7\) is both non-decreasing and non-increasing, since \(a_n = a_{n+1}\) for every \(n\). It is not strictly monotone.
The alternating sequence \(a_n = (-1)^n\), giving \(1, -1, 1, -1, \ldots\), is not monotone: it neither only goes up nor only goes down.
Strict and weak monotonicity
The distinction between strict and weak monotonicity is small but consequential. A strictly increasing sequence takes a different value at every index — no term ever repeats. A non-decreasing sequence may pause: a perfectly valid non-decreasing sequence is \(1, 1, 2, 2, 3, 3, \ldots\)
In practice, weak monotonicity is the more common assumption, because it is closed under more operations (the sum of two non-decreasing sequences is non-decreasing; the sum of two strictly increasing sequences need not be strictly increasing if the increments cancel). Statements about convergence and limits, which we will meet later, also tend to be stated in the weak form.
Bounded sequences
Let \((a_n)_{n \in \mathbb{N}}\) be a sequence of real numbers. We say that \((a_n)\) is:
bounded above if there exists a real number \(M\) such that \(a_n \leq M\) for every \(n \in \mathbb{N}\). Any such \(M\) is called an upper bound for the sequence.
bounded below if there exists a real number \(m\) such that \(a_n \geq m\) for every \(n \in \mathbb{N}\). Any such \(m\) is called a lower bound for the sequence.
bounded if it is both bounded above and bounded below — equivalently, if there exists a real number \(K \geq 0\) such that \(|a_n| \leq K\) for every \(n \in \mathbb{N}\).
A sequence that is not bounded is called unbounded.
Examples of bounded and unbounded sequences
The natural numbers \(a_n = n\) are bounded below (by \(0\)) but not bounded above. They are therefore unbounded.
The reciprocals \(a_n = \dfrac{1}{n}\) for \(n \geq 1\) are bounded: every term lies in the interval \((0, 1]\). So \(0\) is a lower bound and \(1\) is an upper bound; \(|a_n| \leq 1\) for all \(n\).
The alternating sequence \(a_n = (-1)^n\) is bounded: \(|a_n| = 1\) for every \(n\). It is not monotone, which shows that boundedness and monotonicity are independent properties — a sequence may have one, both, or neither.
The sequence \(a_n = (-1)^n \cdot n\), giving \(0, -1, 2, -3, 4, -5, \ldots\), is neither bounded above nor bounded below.
Monotonicity propagates
If \((a_n)_{n \in \mathbb{N}}\) is non-decreasing, then for all natural numbers \(m\) and \(n\) with \(m \leq n\),
\[a_m \leq a_n.\]
The analogous statement holds for the other three forms of monotonicity, with the appropriate inequality.
Fix \(m \in \mathbb{N}\). We prove by induction on \(k \in \mathbb{N}\) that \(a_m \leq a_{m+k}\). Setting \(n = m + k\) then gives the statement of the theorem.
Base case. When \(k = 0\), the claim is \(a_m \leq a_m\), which holds by reflexivity of \(\leq\).
Inductive step. Suppose \(a_m \leq a_{m+k}\) for some \(k \in \mathbb{N}\). By the definition of non-decreasing applied at index \(m+k\), we have \(a_{m+k} \leq a_{m+k+1}\). Combining the two inequalities by transitivity,
\[a_m \leq a_{m+k} \leq a_{m+k+1},\]
so \(a_m \leq a_{m+k+1}\). This completes the induction.
By the Principle of Mathematical Induction, \(a_m \leq a_{m+k}\) for every \(k \in \mathbb{N}\), and the theorem follows.
Connection to Computer Science
Monotonicity and boundedness are everywhere in the analysis of algorithms. A loop counter that only increases, a buffer whose size only grows, an estimate that only improves — each is a monotone sequence in disguise, and reasoning about correctness often comes down to recognising this. A monotone quantity bounded above by some target value is the standard way of showing that a procedure must eventually terminate.
Boundedness shows up in a different role: as a guarantee that values do not exceed what their representation allows. A counter known to stay between \(0\) and \(2^{32}\) fits in a 32-bit integer; one that may grow without bound does not. The distinction between bounded and unbounded growth is the difference between a program that works on any input and a program that works only on small ones.
Does boundedness imply settling down?
The sequence \(a_n = (-1)^n\) is bounded — every term has absolute value \(1\) — yet it never settles into one value. It alternates between \(1\) and \(-1\) forever. So boundedness alone does not force a sequence to converge, in any informal sense of the word.
The sequence \(a_n = 1/n\), by contrast, is bounded and monotone (decreasing), and its terms do appear to settle: they get arbitrarily close to \(0\). It is a real and important fact that the combination of monotonicity and boundedness is enough to force this kind of settling. This is the content of the monotone convergence theorem, which we will state and prove once we have the language of limits. For now, we simply note that both properties together do something neither one does alone.
Exercises
Exercise 1
For each sequence, decide whether it is monotone (in any of the four senses: non-decreasing, strictly increasing, non-increasing, or strictly decreasing).
Exercise 2
For each sequence, decide whether it is bounded.
Exercise 3
Consider the sequence \(a_n = \dfrac{1}{n+1}\) for \(n \geq 0\). Fill in the requested bounds and terms.
Exercise 4
Decide whether each statement is true or false.
Summary
A sequence is monotone if its terms move in a single direction: non-decreasing, strictly increasing, non-increasing, or strictly decreasing.
A sequence is bounded if there exists \(K \geq 0\) with \(|a_n| \leq K\) for every \(n\). It is bounded above or below when only one of the two inequalities is required.
Monotonicity and boundedness are independent: a sequence may have one, both, or neither.
If a sequence is non-decreasing, then \(a_m \leq a_n\) whenever \(m \leq n\) — the relation between adjacent terms propagates to all pairs.
These two properties together — monotonicity and boundedness — will turn out to force a sequence to converge. Establishing this will require the language of limits.