Sequences and Summations

definitions
discrete-math
sequences

Standard notation for sequences and summations, and the manipulations — change of variable, splitting off the last term — that every induction proof over a sum relies on. See mathematical-induction for the proofs those manipulations feed into.

Notation

A sequence is an ordered list of terms, written in any of these ways:

\[a_1, a_2, a_3, \dots \qquad (a_n)_{n \geq 0} \qquad \{a_n\}_{n=1}^{\infty}\]

These are notations for the same kind of object, not for the same sequence — note that the middle one starts at \(n = 0\) and the other two at \(n = 1\). Always read the bound.

The course uses all of these interchangeably and does not privilege one. A recursively defined sequence may be written \(\{b_n\}_{n \geq 0}\), and the braces may be dropped entirely for a bare \(a_0, a_1, a_2, \dots\). Read whichever form is in front of you; do not expect a house standard.

The subscript is the index; the bound on the index says where the sequence starts (and, if finite, where it stops). A sum over a range of the index is written

\[\sum_{n=1}^{m} a_n\]

Three ways to define a sequence

By an explicit formula that lets you calculate the value of any particular term directly.

\(a_1, a_2, a_3, \dots\) where \(a_n = 2^n - 1\), giving \(1, 3, 7, 15, 31, \dots\)

Recursively, by a rule that calculates a term from the value of one or more preceding terms.

\(\{b_n\}_{n \geq 0}\) where \(b_0 = 3\) and \(b_n = 2 \cdot b_{n-1}\) for \(n \geq 1\), giving \(3, 6, 12, 24, 48, \dots\)

The “or more” matters: the Fibonacci numbers are the standard example of a sequence whose rule reaches back two terms rather than one. A recursive definition needs both a recurrence relation and initial conditions — see recursive-definitions for what each part contributes and how to move between a recursive and an explicit definition.

In words.

For all positive integers \(n\), the sequence in which the \(n^{\text{th}}\) term is the sum of the digits of \(n^2\), giving \(1, 4, 9, 7, 7, 9, \dots\)

(Check: \(1^2 = 1\), \(2^2 = 4\), \(3^2 = 9\), \(4^2 = 16 \to 7\), \(5^2 = 25 \to 7\), \(6^2 = 36 \to 9\).)

A sequence cannot be defined by listing its first few terms

Unless you can list all of them. Initial terms never pin down a sequence — infinitely many sequences agree on any finite prefix.

What is the next term in the sequence with initial terms \(1, 4, 9, 16\)?

Definition Sequence
\(a_n = n^2\) \(1, 4, 9, 16, 25, 36, \dots\)
\(a_n = n^2 \bmod 20\) \(1, 4, 9, 16, 5, 16, 9, \dots\)

Both are legitimate, and they disagree from the fifth term on. The Online Encyclopedia of Integer Sequences (https://oeis.org) returns 397 sequences for a search on \(1, 4, 9, 16\).

Working with sums

Sums over the same index range add and scale termwise:

\[\sum_{i=m}^{n} a_i \pm \sum_{i=m}^{n} b_i = \sum_{i=m}^{n} (a_i \pm b_i) \qquad\qquad \sum_{i=m}^{n} c\,a_i = c \sum_{i=m}^{n} a_i\]

The second is just factoring out the common \(c\) once the sum is written out. The general statement is on the left below and the \(c = 2\) case on the right:

\[c\,a_m + c\,a_{m+1} + \cdots + c\,a_n = c\,(a_m + \cdots + a_n) \qquad\qquad 2a_m + 2a_{m+1} + \cdots + 2a_n = 2(a_m + \cdots + a_n)\]

Note the precondition on the first identity: the two index ranges must match before the terms can be combined. Making them match is what the change of variable below is for.

Change of variable

Substituting a new index shifts the limits and rewrites the general term. To apply \(j = i + 1\) (equivalently \(i = j - 1\)) to \(\displaystyle\sum_{i=0}^{n-1} (2i + 5)\), do three things:

  • lower limit: \(j = 0 + 1 = 1\)
  • upper limit: \(j = (n-1) + 1 = n\)
  • general term: \(2i + 5 = 2(j-1) + 5 = 2j + 3\)

\[\sum_{i=0}^{n-1} (2i+5) = \sum_{j=1}^{n} (2j+3)\]

The sum is unchanged — only its description moved. Figure 1 lays the two descriptions over the terms they describe, which is what makes that claim checkable rather than a rule to trust.

Figure 1: A change of variable relabels, it does not recompute. The boxed row is the list of numbers being added — \(5, 7, 9, \dots, 2n+3\) — and it is identical under both descriptions; only the index written above and below it changes. The three red checks are the three things the substitution has to fix, each attached to the part of the picture it governs.

Splitting off the last term

Writing a sum out and peeling the final term off is the manoeuvre used in almost every induction proof of a summation property, since it is what turns the \(P(k+1)\) side into “the \(P(k)\) side, plus one more term”:

\[\sum_{i=1}^{n+1} (3i+2) = \underbrace{(3 \cdot 1 + 2) + (3 \cdot 2 + 2) + \cdots + (3n + 2)}_{i \;=\; 1 \,\dots\, n} + \underbrace{(3(n+1) + 2)}_{i \;=\; n+1}\]

\[= \sum_{i=1}^{n} (3i+2) \; + \; (3(n+1)+2)\]

The same sum can also be split further back — peeling off the last two terms, or shifting the whole index — which is why a single sum has many equal-looking rewrites.

See also