Commonly Used Progression / Sums

Table of contents
  1. Arithmetic Progression
    1. N-th Arithmetic Term
    2. N-th Arithmetic Sum
    3. Frequently Used Arithmetic Sums
  2. Geometric Progression
    1. N-th Geometric Term
    2. N-th Geometric Sum
    3. Infinite Geometric Sum
    4. Frequently Used Geometric Sums
  3. Harmonic Progression
    1. N-th Harmonic Term
    2. Frequently Used Harmonic Sums
  4. Sum of Squares of Natural Numbers

Arithmetic Progression

Arithmetic progression is where the difference between consecutive terms is constant.

  • Let $a$ be the first term.
  • Let $d$ be the common difference.
  • Let $l$ be the last term.
  • Let $a_n$ be the $n^{th}$ term.
  • Let $S_n$ be the sum of the first $n$ terms.

N-th Arithmetic Term

The $n^{th}$ term of an arithmetic progression is denoted $a_n$ and is given by:

$$ a_n = a + (n - 1)d $$

Which is intuitive.

N-th Arithmetic Sum

The sum of the first $n$ terms of an arithmetic progression is denoted $S_n$ and is given by:

$$ \begin{align*} S_n &= n \cdot \frac{2a + (n - 1)d}{2} \\[0.5em] &= \frac{n(a + l)}{2} \end{align*} $$

Essentially, the number of terms multiplied by the average of the first and last term.

Frequently Used Arithmetic Sums

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

Geometric Progression

Geometric progression is where the ratio between consecutive terms is constant.

  • Let $a$ be the first term.
  • Let $r$ be the common ratio.
  • Let $l$ be the last term.
  • Let $a_n$ be the $n^{th}$ term.
  • Let $S_n$ be the sum of the first $n$ terms.

N-th Geometric Term

The $n^{th}$ term of a geometric progression is denoted $a_n$ and is given by:

$$ a_n = a \cdot r^{n - 1} $$

N-th Geometric Sum

The sum of the first $n$ terms of a geometric progression is denoted $S_n$ and is given by:

$$ \begin{align*} S_n &= \frac{a(r^n - 1)}{r - 1} \\[0.5em] &= \frac{l \cdot r - a}{r - 1} \end{align*} $$

Division by Zero?

Obviously, the above only applies when $r \neq 1$.

When $r = 1$, the sum collapses to an obvious $n \cdot a$, which can also be derived from the arithmetic sum formula where $d = 0$.

Infinite Geometric Sum

When $n \to \infty$,

If $|r| < 1$, the sum converges to:

$$ S_{\infty} = \frac{a}{1 - r} \quad \text{if} \quad |r| < 1 $$

If $|r| \geq 1$, the sum diverges.

Frequently Used Geometric Sums

\[\sum_{i=0}^{n-1} 2^i = 2^n - 1\]

Check out intuition using binary representation.

Harmonic Progression

Harmonic progression is the reciprocal progression of an arithmetic progression.

So if the terms of an arithmetic progression are $a, a + d, a + 2d, \ldots$, the harmonic progression would be:

\[\frac{1}{a}, \frac{1}{a + d}, \frac{1}{a + 2d}, \ldots\]

N-th Harmonic Term

It is the reciprocal of the $n^{th}$ term of an arithmetic progression:

$$ a_n = \frac{1}{a + (n - 1)d} $$

Frequently Used Harmonic Sums

  • Upper bound of the sum of the first $n$ terms:

    \[\sum_{i=1}^{n} \frac{1}{i} < \log_2(n) + 1 = O(\log(n))\]

Sum of Squares of Natural Numbers

For the sum of squares of the first $n$ natural numbers:

$$ \sum_{i=1}^{n} i^2 = \frac{n(n + 1)(2n + 1)}{6} $$

There is also a formula for even and odd numbers, also $O(n^3)$.