Sum of the first n terms
Learning Objectives
- Derive and apply the closed-form formula for the sum of the first \(n\) terms of a geometric progression.
- Handle the special case \(q = 1\) separately.
- Apply the formula to numerical and real-world problems, including the chessboard-wheat calculation.
- Recognise the qualitatively different behaviour of partial sums when \(|q| < 1\) versus \(|q| > 1\).
Motivation
The chessboard legend ended at the moment we recognised the doubling pattern. The next, harder question is: how many grains in total? A single addition is easy; sixty-four additions, each producing a number twice as large as the last, are not. We need a closed-form expression analogous to the one Gauss found for arithmetic progressions — a formula that, given the first term, the common ratio, and the number of terms, returns the sum in a single step.
Such a formula exists, and it has been known in essentially its modern form since antiquity. Euclid, in Book IX of the Elements, gives a version (Proposition 35) for the case of integer ratios greater than one. The argument we present here uses a small algebraic trick — multiplying the sum by the common ratio and subtracting — that makes the calculation transparent.
Partial sum
Let \((b_n)_{n \geq 1}\) be a geometric progression. For every \(n \geq 1\), the \(n\)-th partial sum of the progression is
\[S_n = b_1 + b_2 + b_3 + \cdots + b_n = \sum_{k=1}^{n} b_k.\]
As with arithmetic progressions, the sequence \((S_n)_{n \geq 1}\) of partial sums is itself a sequence of real numbers, accumulating the first \(n\) terms of the underlying progression.
Sum of a geometric progression
Let \((b_n)_{n \geq 1}\) be a geometric progression with first term \(b_1\) and common ratio \(q\). For every \(n \geq 1\):
If \(q = 1\), then every term equals \(b_1\) and \(S_n = n \cdot b_1\).
If \(q \neq 1\), then
\[S_n = b_1 \cdot \frac{q^{\,n} - 1}{q - 1} = b_1 \cdot \frac{1 - q^{\,n}}{1 - q}.\]
The two expressions on the right of the second case are equal (multiply numerator and denominator by \(-1\)); the first form is usually preferred when \(q > 1\), the second when \(0 < q < 1\), so that numerator and denominator have matching signs.
Proof — multiplication and subtraction
The case \(q = 1\) is immediate: every term equals \(b_1\), so the sum of \(n\) copies of \(b_1\) is \(n \cdot b_1\). Suppose now that \(q \neq 1\). Write the partial sum and the partial sum multiplied by \(q\):
\[\begin{aligned} S_n &= b_1 + b_1 q + b_1 q^{2} + \cdots + b_1 q^{\,n-1}, \\ q\, S_n &= \phantom{b_1 +\ } b_1 q + b_1 q^{2} + \cdots + b_1 q^{\,n-1} + b_1 q^{\,n}. \end{aligned}\]
Subtracting the first line from the second, every term in the middle cancels — \(b_1 q\) cancels with itself, as does \(b_1 q^2\), and so on through \(b_1 q^{n-1}\). What remains is just the first term of one line and the last term of the other:
\[q\, S_n - S_n = b_1 q^{\,n} - b_1.\]
Factoring both sides, \((q - 1)\, S_n = b_1 (q^{\,n} - 1)\). Since \(q \neq 1\), we may divide by \(q - 1\), giving
\[S_n = b_1 \cdot \frac{q^{\,n} - 1}{q - 1}.\]
Proof — by induction
We give a second proof of the identity \(S_n = b_1 \cdot \dfrac{q^{\,n} - 1}{q - 1}\) (for \(q \neq 1\)) by induction on \(n\).
Base case. When \(n = 1\), the formula reads \(S_1 = b_1 \cdot \dfrac{q - 1}{q - 1} = b_1\), which matches the definition \(S_1 = b_1\).
Inductive step. Suppose \(S_n = b_1 \cdot \dfrac{q^{\,n} - 1}{q - 1}\) for some \(n \geq 1\). Then
\[S_{n+1} = S_n + b_{n+1} = b_1 \cdot \frac{q^{\,n} - 1}{q - 1} + b_1 q^{\,n}.\]
Putting the two terms over the common denominator \(q - 1\),
\[S_{n+1} = \frac{b_1 (q^{\,n} - 1) + b_1 q^{\,n} (q - 1)}{q - 1} = \frac{b_1 \bigl( q^{\,n} - 1 + q^{\,n+1} - q^{\,n} \bigr)}{q - 1} = b_1 \cdot \frac{q^{\,n+1} - 1}{q - 1},\]
which is the formula at index \(n + 1\). By the Principle of Mathematical Induction, the formula holds for every \(n \geq 1\).
Why the special case for \(q = 1\)
The closed-form expression \(S_n = b_1 \cdot \dfrac{q^{\,n} - 1}{q - 1}\) has a denominator that vanishes precisely when \(q = 1\), so the formula simply does not apply in that case. The progression itself is perfectly meaningful — it is the constant sequence \(b_1, b_1, b_1, \ldots\) — but the closed form is the wrong tool, and we must compute the sum directly as \(n \cdot b_1\).
If we attempt to recover the \(q = 1\) case as a limit of the formula, we find (after some calculation) that \(\dfrac{q^{\,n} - 1}{q - 1} \to n\) as \(q \to 1\), so the limit agrees with the direct computation. But the formula itself is undefined at \(q = 1\), and the special case must be handled separately in any calculation or algorithm.
Three computations
The chessboard. The grains on the chessboard form the geometric progression \(1, 2, 4, 8, \ldots, 2^{63}\), with \(b_1 = 1\), \(q = 2\), \(n = 64\). The formula gives
\[S_{64} = 1 \cdot \frac{2^{64} - 1}{2 - 1} = 2^{64} - 1 = 18\,446\,744\,073\,709\,551\,615.\]
This is about eighteen quintillion grains — many times the total wheat ever produced by humans. The doubling is patient: it takes the first thirty squares to reach the cost of a small house, and the last few squares to overwhelm the global supply.
A sum with \(|q| < 1\). Consider \(1 + \dfrac{1}{2} + \dfrac{1}{4} + \cdots + \dfrac{1}{2^{9}}\), a geometric progression with \(b_1 = 1\), \(q = 1/2\), \(n = 10\). Using the second form of the formula,
\[S_{10} = 1 \cdot \frac{1 - (1/2)^{10}}{1 - 1/2} = \frac{1 - 1/1024}{1/2} = 2 - \frac{1}{512} = \frac{1023}{512}.\]
The sum stays just below \(2\), no matter how many terms we add. We will explain this stability in the critical examination below.
The first ten terms of \(3 + 6 + 12 + 24 + \cdots\). Here \(b_1 = 3\), \(q = 2\), \(n = 10\), giving
\[S_{10} = 3 \cdot \frac{2^{10} - 1}{2 - 1} = 3 \cdot 1023 = 3069.\]
Connection to Computer Science
Geometric series appear throughout the analysis of algorithms. The total number of nodes in a complete binary tree of depth \(n\) is \(1 + 2 + 4 + \cdots + 2^{n} = 2^{n+1} - 1\) — an immediate application of the sum formula with \(q = 2\). A recursive procedure that does a unit of work and then makes two calls each handling half the input does total work \(1 + 2 + 4 + \cdots\) at successive levels, until the input shrinks to a base case; the total is again a geometric sum.
The case \(|q| < 1\) is just as important. The amortised analysis of a dynamic array, for instance, relies on the fact that the total cost of all resizing operations after \(n\) insertions is \(n + n/2 + n/4 + \cdots\) — a geometric series whose sum is bounded by \(2n\), even though it has unboundedly many terms. This is the mathematical content behind the everyday claim that "doubling the array size on overflow gives amortised constant-time insertion."
What happens to \(S_n\) as \(n\) grows?
The qualitative behaviour of the partial sums splits into two regimes, governed by the magnitude of the common ratio.
If \(|q| > 1\), then \(|q^{\,n}|\) grows without bound, and so do the partial sums. The chessboard sum \(2^{64} - 1\) is a finite number, but its size is an artefact of stopping at \(n = 64\); if we asked for the sum of the first thousand terms, the answer would be unimaginably larger.
If \(|q| < 1\), then \(q^{\,n}\) shrinks toward zero as \(n\) grows, and the formula becomes
\[S_n = b_1 \cdot \frac{1 - q^{\,n}}{1 - q} \;\approx\; b_1 \cdot \frac{1}{1 - q} \quad \text{for large } n.\]
The partial sums therefore stay close to the value \(\dfrac{b_1}{1 - q}\), no matter how many terms are added. The second computation above is a special case: \(\dfrac{1}{1 - 1/2} = 2\), and the partial sums approach but never exceed \(2\).
The statement that "infinitely many terms add up to a finite total" requires a precise definition of an infinite sum, which we will develop in a later course alongside the theory of limits. For now, the calculation above is enough to make the phenomenon plausible: geometric progressions with \(|q| < 1\) accumulate slowly enough that their total remains under control, while those with \(|q| > 1\) accumulate quickly enough that no bound holds.
Exercises
Exercise 1
A geometric progression has \(b_1 = 2\) and common ratio \(q = 3\). Compute the partial sums.
Exercise 2
Compute each geometric sum.
Exercise 3
A geometric progression has first term \(b_1 = 4\) and common ratio \(q = 2\). Find the smallest \(n\) for which the partial sum exceeds 1000.
Exercise 4
Decide whether each statement is true or false.
Summary
The \(n\)-th partial sum of a geometric progression is \(S_n = \displaystyle\sum_{k=1}^{n} b_k\).
For a geometric progression with first term \(b_1\) and common ratio \(q\):
If \(q = 1\), then \(S_n = n \cdot b_1\).
If \(q \neq 1\), then \(S_n = b_1 \cdot \dfrac{q^{\,n} - 1}{q - 1} = b_1 \cdot \dfrac{1 - q^{\,n}}{1 - q}\).
The closed-form is proved by multiplying \(S_n\) by \(q\) and subtracting: the middle terms cancel, and what remains gives \((q - 1) S_n = b_1 (q^{\,n} - 1)\).
The behaviour of the partial sums depends qualitatively on \(|q|\): they grow without bound when \(|q| > 1\), and stay close to \(\dfrac{b_1}{1 - q}\) when \(|q| < 1\).
The same formula governs the chessboard-wheat sum, the node-count of a complete binary tree, and the amortised cost of dynamic-array resizing — three faces of the same mathematics.