Skip to content

Arithmetic and Geometric Sequences and Series

Pillar: CHAIN — "Each term depends on the previous — find the transition."

What Is a Sequence?

A sequence is an ordered list of numbers following a rule. Each number is called a term, and we label them \(a_1, a_2, a_3, \ldots\)

A series is the sum of terms of a sequence. If the sequence is \(a_1, a_2, \ldots, a_n\), the series is \(S_n = a_1 + a_2 + \cdots + a_n\).

The distinction matters: a sequence is a list, a series is a sum. In competitive programming, you encounter both — sequences when modeling processes that evolve step by step, series when computing totals.

Arithmetic Sequences

An arithmetic sequence has a constant difference between consecutive terms.

\[a_1, \; a_1 + d, \; a_1 + 2d, \; a_1 + 3d, \; \ldots\]

The number \(d\) is the common difference. It can be positive (increasing), negative (decreasing), or zero (constant).

The \(n\)-th Term Formula

\[a_n = a_1 + (n-1)d\]

This says: start at \(a_1\) and add \(d\) exactly \((n-1)\) times to reach the \(n\)-th term.

Example. In the sequence \(3, 7, 11, 15, \ldots\), we have \(a_1 = 3\) and \(d = 4\).

\[a_{50} = 3 + 49 \cdot 4 = 3 + 196 = 199\]

Example. If \(a_3 = 14\) and \(a_7 = 30\), find \(a_1\) and \(d\).

From the formula: \(a_7 - a_3 = (a_1 + 6d) - (a_1 + 2d) = 4d = 30 - 14 = 16\), so \(d = 4\).

Then \(a_3 = a_1 + 2(4) = 14\), so \(a_1 = 6\).

Identifying Arithmetic Sequences

Given a list of numbers, check if consecutive differences are constant:

Term \(a_1\) \(a_2\) \(a_3\) \(a_4\) \(a_5\)
Value \(5\) \(8\) \(11\) \(14\) \(17\)
Difference — \(3\) \(3\) \(3\) \(3\)

Constant differences confirm it is arithmetic with \(d = 3\).

Arithmetic Series

The sum of the first \(n\) terms of an arithmetic sequence:

\[S_n = \frac{n(a_1 + a_n)}{2}\]

Derivation by Pairing (Gauss's Trick)

Write the sum forwards and backwards:

\[S_n = a_1 + (a_1+d) + (a_1+2d) + \cdots + a_n\]
\[S_n = a_n + (a_n-d) + (a_n-2d) + \cdots + a_1\]

Add the two rows term by term. Every pair sums to \(a_1 + a_n\):

\[2S_n = n(a_1 + a_n) \implies S_n = \frac{n(a_1 + a_n)}{2}\]

This pairing trick is clean and reusable. Whenever you have a sum with symmetric structure, try writing it both ways.

The Classic: Sum of First \(n\) Integers

\[1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\]

This is an arithmetic series with \(a_1 = 1\), \(d = 1\), \(a_n = n\).

You will use this formula hundreds of times. It appears in:

  • Counting pairs: \(\binom{n}{2} = \frac{n(n-1)}{2}\)
  • Nested loop analysis: two nested loops over \(n\) elements do \(\frac{n(n-1)}{2}\) iterations
  • Prefix sums: the sum of the first \(k\) positive integers

More Useful Formulas

\[1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\]
\[2 + 4 + 6 + \cdots + 2n = n(n+1)\]
\[1 + 3 + 5 + \cdots + (2n-1) = n^2\]

That last one is worth memorizing: the sum of the first \(n\) odd numbers is a perfect square.

Worked Example

Problem. Find the sum \(5 + 9 + 13 + \cdots + 101\).

First, identify: \(a_1 = 5\), \(d = 4\), \(a_n = 101\).

Find \(n\): \(101 = 5 + (n-1) \cdot 4 \implies n - 1 = 24 \implies n = 25\).

Sum: \(S_{25} = \frac{25(5 + 101)}{2} = \frac{25 \cdot 106}{2} = 1325\).

Geometric Sequences

A geometric sequence has a constant ratio between consecutive terms.

\[a_1, \; a_1 r, \; a_1 r^2, \; a_1 r^3, \; \ldots\]

The number \(r\) is the common ratio.

The \(n\)-th Term Formula

\[a_n = a_1 \cdot r^{n-1}\]

Example. In the sequence \(3, 6, 12, 24, \ldots\), we have \(a_1 = 3\) and \(r = 2\).

\[a_{10} = 3 \cdot 2^9 = 3 \cdot 512 = 1536\]

Example. If \(a_2 = 10\) and \(a_5 = 1250\), find \(r\).

\(a_5 / a_2 = r^3 = 1250 / 10 = 125\), so \(r = 5\).

Identifying Geometric Sequences

Check if consecutive ratios are constant:

Term \(a_1\) \(a_2\) \(a_3\) \(a_4\) \(a_5\)
Value \(2\) \(6\) \(18\) \(54\) \(162\)
Ratio — \(3\) \(3\) \(3\) \(3\)

Constant ratios confirm it is geometric with \(r = 3\).

Geometric Series

Finite Sum

\[S_n = a_1 \cdot \frac{r^n - 1}{r - 1} \qquad (r \neq 1)\]

Derivation (Multiply-and-Subtract)

\[S_n = a_1 + a_1 r + a_1 r^2 + \cdots + a_1 r^{n-1}\]

Multiply both sides by \(r\):

\[rS_n = a_1 r + a_1 r^2 + \cdots + a_1 r^n\]

Subtract \(S_n\) from \(rS_n\) — most terms cancel (this is a telescoping idea!):

\[rS_n - S_n = a_1 r^n - a_1 \implies S_n(r - 1) = a_1(r^n - 1) \implies S_n = a_1 \cdot \frac{r^n - 1}{r - 1}\]

Infinite Sum

When \(|r| < 1\), the terms get smaller and smaller, and the sum converges:

\[S_\infty = \frac{a_1}{1 - r} \qquad (|r| < 1)\]

Example. \(\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots = \frac{1/2}{1 - 1/2} = 1\).

Example. \(1 + \frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \cdots = \frac{1}{1 - 1/3} = \frac{3}{2}\).

When \(|r| \geq 1\), the infinite series diverges — the partial sums grow without bound.

Applications in Competitive Programming

Binary Counting: Powers of 2

The number of subsets of an \(n\)-element set is \(2^n\). This is a geometric sequence with \(r = 2\):

\[1, 2, 4, 8, 16, 32, \ldots\]

The sum \(1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1\). This is why a complete binary tree with \(n\) levels has \(2^n - 1\) nodes.

Doubling Problems

Any process that doubles at each step produces a geometric sequence. "If a population doubles every hour, when does it reach \(N\)?" is asking for \(\log_2(N/a_1)\) — connecting back to Lesson 2.

Nested Loop Complexity

Consider:

for (int i = 1; i <= n; i *= 2)
    for (int j = 0; j < i; j++)
        // O(1) work

The inner loop runs \(1, 2, 4, \ldots, n\) times. Total work:

\[1 + 2 + 4 + \cdots + n = 2n - 1 = O(n)\]

This is a geometric series with \(r = 2\). Without recognizing the geometric sum, you might wrongly guess \(O(n \log n)\).

Harmonic-Like Sums

While the harmonic series \(\sum 1/k\) is not geometric, comparing it to a geometric series gives bounds. This connection becomes important in Chapter 2 when analyzing sieve algorithms.

Identifying Sequence Type

Given data, how do you tell if a sequence is arithmetic or geometric?

Check Arithmetic Geometric
Consecutive differences constant? Yes, \(d = a_{n+1} - a_n\) No
Consecutive ratios constant? No Yes, \(r = a_{n+1}/a_n\)
General term Linear in \(n\): \(a_n = dn + c\) Exponential in \(n\): \(a_n = a_1 r^{n-1}\)
Growth Adds same amount each step Multiplies by same factor each step

Example. Classify: \(5, 10, 20, 40, 80\).

Differences: \(5, 10, 20, 40\) — not constant. Ratios: \(2, 2, 2, 2\) — constant. Geometric, \(r = 2\).

Example. Classify: \(100, 93, 86, 79, 72\).

Differences: \(-7, -7, -7, -7\) — constant. Arithmetic, \(d = -7\).

Sigma Notation

Sums are written compactly using \(\Sigma\):

\[\sum_{k=1}^{n} a_k = a_1 + a_2 + \cdots + a_n\]

Important properties:

\[\sum_{k=1}^{n} (a_k + b_k) = \sum_{k=1}^{n} a_k + \sum_{k=1}^{n} b_k\]
\[\sum_{k=1}^{n} c \cdot a_k = c \sum_{k=1}^{n} a_k\]
\[\sum_{k=1}^{n} c = cn\]

Example: Sum of Squares

\[\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\]

This formula appears when analyzing algorithms with quadratic inner loops. You do not need to derive it from scratch — just know it exists and can verify it by induction.

Example: Writing a Sum in Sigma Notation

\(3 + 7 + 11 + 15 + \cdots + 99\)

The \(k\)-th term is \(a_k = 3 + 4(k-1) = 4k - 1\). The last term: \(4k - 1 = 99 \implies k = 25\).

\[\sum_{k=1}^{25} (4k - 1) = 4\sum_{k=1}^{25} k - \sum_{k=1}^{25} 1 = 4 \cdot \frac{25 \cdot 26}{2} - 25 = 1300 - 25 = 1275\]

Practice Problems

Problem 1. Find the 30th term and the sum of the first 30 terms of the arithmetic sequence \(2, 9, 16, 23, \ldots\)

Solution

\(a_1 = 2\), \(d = 7\). \(a_{30} = 2 + 29 \cdot 7 = 205\). \(S_{30} = \frac{30(2 + 205)}{2} = 3105\).

Problem 2. Find the sum \(1 + 2 + 4 + 8 + \cdots + 2^{19}\).

Solution

Geometric series: \(a_1 = 1\), \(r = 2\), \(n = 20\) terms. \(S_{20} = \frac{2^{20} - 1}{2 - 1} = 1048575\).

Problem 3. A sequence satisfies \(a_1 = 5\) and \(a_n = a_{n-1} + 3\). Find \(a_{100}\) and \(S_{100}\).

Solution

Arithmetic with \(d = 3\). \(a_{100} = 5 + 99 \cdot 3 = 302\). \(S_{100} = \frac{100(5+302)}{2} = 15350\).

Problem 4. Find the infinite sum \(\frac{1}{4} + \frac{1}{16} + \frac{1}{64} + \cdots\)

Solution

Geometric: \(a_1 = 1/4\), \(r = 1/4\). \(S_\infty = \frac{1/4}{1 - 1/4} = \frac{1/4}{3/4} = \frac{1}{3}\).

Problem 5. A for-loop runs with i = 1, 3, 9, 27, ... up to \(n\). How many iterations?

Solution

The values form a geometric sequence with \(r = 3\). The loop runs while \(3^{k-1} \leq n\), so \(k \leq 1 + \log_3 n\). Number of iterations: \(\lfloor \log_3 n \rfloor + 1\).

Problem 6. Prove that \(1 + 3 + 5 + \cdots + (2n-1) = n^2\) using the arithmetic series formula.

Solution

This is an arithmetic series with \(a_1 = 1\), \(a_n = 2n - 1\), and \(n\) terms. \(S_n = \frac{n(1 + (2n-1))}{2} = \frac{n \cdot 2n}{2} = n^2\).

Problem 7. Evaluate \(\displaystyle\sum_{k=0}^{9} 3 \cdot 2^k\).

Solution

\(= 3 \sum_{k=0}^{9} 2^k = 3 \cdot (2^{10} - 1) = 3 \cdot 1023 = 3069\).