Number Series

It helps to know how to read different number series and find their sums. This matters in general, and for big O calculations.

Keep in mind that the value at each position comes from the previous ones. This is why the sum is often shown using just the last elements.

It's all about finding the area in geometry

In all the sum series, the goal is to find the area from the series. The sum is the total area from each position.

meaning of N in the series

Here N isn't the value at the position. N is the position itself. Use this for all N's in the table below.

For example, in the sum of odd numbers, the N in $N^2$ is the last position.

Number series / pattern	Formula / closed form	Why it appears in interviews
Arithmetic series	$S = N(\frac{first + last}{2})$	Iteratively adding a constant to each position.
Sum of first N numbers	$1 + 2 + ... + N = \frac{N(N+1)}{2}$	Counting loop iterations, triangular loops. Same as above. But adding 1 to each position.
Sum of 1 through N−1	$1 + 2 + 3 + ... + (N−1) = \frac{N(N−1)}{2}$	Pair comparisons, nested loops. Same rectangle mental model. Just one layer less.
Sum of odd numbers	$1 + 3 + ... + (2N−1) = {N^2}$	Explains quadratic growth. Here 2N-1 is the value at each position. Eg., 2×1-1, 2×2-1.
Sum of even numbers	$2 + 4 + 8 + ... + 2N = N(N+1)$	Loops skipping by 2. Here 2N is the value at each position. Eg., 2×1, 2×2.
Sum of powers of two	$1 + 2 + 4 + ... + 2ⁿ = {2^{n+1}−1}$	Trees, recursion trees, BFS/DFS
Geometric series	$1 + r + r² + ... + rⁿ = \frac{r^{n+1}−1}{r−1}$	Divide-and-conquer analysis
Harmonic series	$1 + 1/2 + 1/3 + ... + 1/N ≈ log N$	Amortized analysis (hashing, resizing)
Average of 1 to N	$\frac{N + 1}{2}$ ≈ $\frac{N}{2}$	Expected value, amortized cost. Here we take sum of first value and the last value and take its average.
Powers of two	$2^0, 2^1, 2^2, … , 2^n$	Binary structures, divide-and-conquer
Number of pairs	$_n C_2 = \frac{N(N−1)}{2}$	Comparing all pairs. This is just the regular combinations formula.
Number of subsets	$2^n$	Power set, bitmask problems
Number of permutations	$N!$	Backtracking, ordering problems

geometric versus arithmetic series

In a geometric series, each element is multiplied by a constant. The shape and proportions stay the same.

In an arithmetic series, a constant is only added to each element.

Meaning of terms

• power set - Explained in detail in the combinatorics doc.
• Harmonic series - The name comes from music. Different string lengths make different sounds.
• Bit mask - Explained in detail in the algorithms learnings.
• Number of pairs - This is also used for same use cases where there are nested for loops. Similar to Sum of 1 through N−1.

Mental models for remembering formulae

The list of formulas above is long. We need mental models that stick forever.

Geometry is the origin of everything

Using geometry as the mental model will help us to remember the number series formulae.

Arithmetic Series

Geometric Series

Here each position is proportional to the previous one. The base of the exponent is the variable. The size at each step depends on both the base and the exponent.

$$\begin{aligned} r = \frac{\text{next term}}{\text{current term}} \\ \text{Value at next position can be expressed in two ways:} \\ next = r×current \\ next = current+(r−1)×current \\ \text{this is where the extra (r-1) in the sum formula comes from.} x &= \frac{6}{9} = \frac{2}{3} \end{aligned}$$

mental model for geometric series

It looks confusing. We mostly use $r^{n+1}$ to get the sum of all numbers up to $r^n$. This is because each term is multiplied by $r$. The next term is much bigger than the last.

Another way to see it: each next term already holds all the parts of the previous series.