Sum of the first n terms
Learning Objectives
- Define the \(n\)-th partial sum of a sequence.
- Prove and apply the closed-form formula \(S_n = \dfrac{n(a_1 + a_n)}{2}\) for an arithmetic progression.
- Convert between the two standard forms of the sum formula.
- Recognise that the partial sum of an arithmetic progression is a quadratic in \(n\) with no constant term.
Motivation
An often-told story has the young Carl Friedrich Gauss, set the task by his schoolmaster of adding the integers from \(1\) to \(100\), producing the answer \(5050\) almost at once. He had noticed that the numbers could be paired off from the outside in: \(1 + 100\), \(2 + 99\), \(3 + 98\), and so on — fifty pairs, each summing to \(101\). The total is therefore \(50 \times 101 = 5050\), and a sum of a hundred numbers reduces to a single multiplication.
The trick is not particular to the numbers \(1\) through \(100\). It works for any arithmetic progression, because the constant common difference is exactly what makes the pairing balance out. In this lesson we make the argument precise and obtain a closed-form expression for the sum of the first \(n\) terms.
Partial sum
Let \((a_n)_{n \geq 1}\) be a sequence of real numbers. For every \(n \geq 1\), the \(n\)-th partial sum of the sequence is
\[S_n = a_1 + a_2 + a_3 + \cdots + a_n = \sum_{k=1}^{n} a_k.\]
The sequence \((S_n)_{n \geq 1}\) is itself a sequence of real numbers, called the sequence of partial sums. Each term \(S_n\) accumulates the first \(n\) values of the original sequence.
Sum of an arithmetic progression
Let \((a_n)_{n \geq 1}\) be an arithmetic progression with first term \(a_1\) and common difference \(d\). For every \(n \geq 1\),
\[S_n = \frac{n\,(a_1 + a_n)}{2} = \frac{n\,\bigl(2a_1 + (n-1)\,d\bigr)}{2}.\]
The two expressions on the right are equal, since \(a_n = a_1 + (n-1)\,d\) by the general-term formula.
Proof — the pairing argument
Write the sum forwards and backwards on two lines:
\[\begin{aligned} S_n &= a_1\ +\ a_2\ +\ a_3\ +\ \cdots\ +\ a_{n-1}\ +\ a_n, \\ S_n &= a_n\ +\ a_{n-1}\ +\ a_{n-2}\ +\ \cdots\ +\ a_2\ +\ a_1. \end{aligned}\]
Adding the two lines term by term, the \(k\)-th column of the first line pairs with the \(k\)-th column of the second, contributing \(a_k + a_{n-k+1}\) for \(k = 1, 2, \ldots, n\). We now compute this pair-sum and show it is independent of \(k\). By the general-term formula,
\[a_k + a_{n-k+1} = \bigl(a_1 + (k-1)\,d\bigr) + \bigl(a_1 + (n-k)\,d\bigr) = 2a_1 + (n-1)\,d = a_1 + a_n.\]
So every one of the \(n\) pairs contributes the same value \(a_1 + a_n\). Therefore,
\[2 S_n = n\,(a_1 + a_n),\]
and dividing by \(2\) gives \(S_n = \dfrac{n\,(a_1 + a_n)}{2}\). Substituting \(a_n = a_1 + (n-1)\,d\) yields the second form.
Proof — by induction
We give a second proof of the same identity, this time by induction on \(n\). We establish the second form,
\[S_n = \frac{n\,(2a_1 + (n-1)\,d)}{2};\]
the first form \(S_n = \dfrac{n(a_1 + a_n)}{2}\) follows by substituting \(a_n = a_1 + (n-1)\,d\), exactly as in the pairing proof.
Base case. When \(n = 1\), the formula reads
\[S_1 = \frac{1 \cdot (2 a_1 + 0)}{2} = a_1,\]
which matches the definition \(S_1 = a_1\).
Inductive step. Suppose \(S_n = \dfrac{n\,(2a_1 + (n-1)\,d)}{2}\) for some \(n \geq 1\). By the definition of the partial sums, \(S_{n+1} = S_n + a_{n+1}\). Using the inductive hypothesis and the general-term formula \(a_{n+1} = a_1 + n\,d\):
\[S_{n+1} = \frac{n\,(2a_1 + (n-1)\,d)}{2} + (a_1 + n\,d) = \frac{n\,(2a_1 + (n-1)\,d) + 2(a_1 + n\,d)}{2}.\]
Expanding the numerator,
\[n\,(2a_1 + (n-1)\,d) + 2(a_1 + n\,d) = 2n a_1 + n(n-1)\,d + 2 a_1 + 2n\,d = 2(n+1)\,a_1 + n(n+1)\,d.\]
Therefore
\[S_{n+1} = \frac{2(n+1)\,a_1 + n(n+1)\,d}{2} = \frac{(n+1)\,(2 a_1 + n\,d)}{2},\]
which is exactly the formula at index \(n + 1\), since \((n+1) - 1 = n\).
By the Principle of Mathematical Induction, the formula holds for every \(n \geq 1\).
Which form to use
The two forms of the sum formula are equivalent, but each is convenient in a different situation.
Use \(S_n = \dfrac{n\,(a_1 + a_n)}{2}\) when both endpoints \(a_1\) and \(a_n\) are known. The arithmetic is straightforward and the formula has an immediate geometric interpretation: it is \(n\) times the average of the first and last terms.
Use \(S_n = \dfrac{n\,(2a_1 + (n-1)\,d)}{2}\) when only \(a_1\), \(d\), and \(n\) are known. This form avoids first computing \(a_n\) separately.
In practice, the choice is dictated by which quantities are given. Either way, the calculation reduces what would otherwise be \(n - 1\) additions to a constant amount of arithmetic.
Three computations
The integers from \(1\) to \(100\). This is the arithmetic progression \(1, 2, 3, \ldots, 100\) with \(a_1 = 1\), \(a_{100} = 100\), and \(n = 100\). Applying the first form,
\[S_{100} = \frac{100 \cdot (1 + 100)}{2} = 50 \cdot 101 = 5050.\]
The first twenty terms of \(5, 8, 11, 14, \ldots\). This progression has \(a_1 = 5\) and \(d = 3\), so
\[S_{20} = \frac{20 \cdot (2 \cdot 5 + 19 \cdot 3)}{2} = \frac{20 \cdot 67}{2} = 670.\]
The odd integers from \(1\) to \(99\). The odd integers form an arithmetic progression \(1, 3, 5, \ldots, 99\) with \(a_1 = 1\), \(d = 2\). To find \(n\), use the general term: \(99 = 1 + (n-1) \cdot 2\) gives \(n = 50\). Then
\[S_{50} = \frac{50 \cdot (1 + 99)}{2} = 50 \cdot 50 = 2500.\]
Connection to Computer Science
A straightforward way to compute a partial sum is to loop: start with an accumulator at zero and add each term in turn. Such a loop performs \(n\) additions and runs in time proportional to \(n\). The closed-form formula replaces this loop with three multiplications and one division, regardless of how large \(n\) is. The cost no longer depends on the length of the sum — a constant amount of work suffices.
This is the simplest example of a recurring theme in algorithm analysis: an iterative procedure that visits each term, replaced by a closed-form expression that does not. The sum \(1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}\) is also the running-time of a doubly-nested loop where the inner one shortens by one each pass — a quadratic-time pattern that appears everywhere from sorting to graph traversal.
The partial sum is a quadratic in \(n\)
Expanding the second form of the sum formula,
\[S_n = \frac{n\,(2a_1 + (n-1)\,d)}{2} = \frac{d}{2}\,n^2 + \left(a_1 - \frac{d}{2}\right) n.\]
This is a quadratic in \(n\) of the form \(A n^2 + B n\), with \(A = d/2\) and \(B = a_1 - d/2\). The constant term is zero — which it must be, since \(S_n = 0\) when \(n = 0\) (an empty sum). The leading coefficient is half the common difference, so the partial sums of a non-constant arithmetic progression grow quadratically in \(n\), even though the original terms grow only linearly.
The converse is also true and worth noting: if a sequence \((S_n)\) is given by \(S_n = A n^2 + B n\) for constants \(A, B \in \mathbb{R}\), then the differences \(a_n = S_n - S_{n-1}\) (for \(n \geq 2\), with \(a_1 = S_1\)) form an arithmetic progression with common difference \(d = 2A\). The two notions — "arithmetic progression" and "quadratic partial sum with no constant term" — therefore describe the same phenomenon from two angles.
Exercises
Exercise 1
An arithmetic progression has \(a_1 = 4\) and common difference \(d = 5\). Compute the partial sums.
Exercise 2
Compute each sum using the formula for an arithmetic progression.
Exercise 3
An arithmetic progression has first term \(a_1 = 3\) and \(S_{10} = 165\). Find the common difference \(d\) and the tenth term \(a_{10}\).
Exercise 4
Decide whether each statement is true or false.
Summary
The \(n\)-th partial sum of a sequence is \(S_n = \displaystyle\sum_{k=1}^{n} a_k\).
For an arithmetic progression with first term \(a_1\) and common difference \(d\),
\[S_n = \frac{n\,(a_1 + a_n)}{2} = \frac{n\,(2a_1 + (n-1)\,d)}{2}.\]
The proof is by pairing: writing the sum forwards and backwards, the \(n\) column pairs each sum to \(a_1 + a_n\), giving \(2 S_n = n(a_1 + a_n)\).
The partial sum is a quadratic in \(n\) with no constant term: \(S_n = \dfrac{d}{2}\,n^2 + \left(a_1 - \dfrac{d}{2}\right) n\). Conversely, any quadratic of the form \(A n^2 + B n\) arises as the partial sum of some arithmetic progression.
The closed-form formula reduces the \(n - 1\) additions of a direct loop to a constant number of arithmetic operations.