Geometric Series

Q: What happens when $r$ is greater than 1?

The formula still works. For $r = 2$ and 10 terms it gives $\frac{1 - 2^{10}}{1 - 2} = 1023$. That equals $1 + 2 + \cdots + 512$, and the last term, 512, is about half of the total.

Q: Why does the sum settle when $r$ is between 0 and 1?

Each power $r^{n}$ shrinks toward 0 as $n$ grows. For example, $(\frac{1}{2})^{10} = \frac{1}{1024}$, which is almost 0. The top of the formula then goes to 1, and the sum goes to $\frac{1}{1 - r}$. For $r = \frac{1}{2}$, that limit is 2.

Q: Why is $r = 1$ a special case?

The formula divides by $1 - r$, which is zero when $r = 1$. In that case each term is 1, so the sum is $n$. For example, four terms of 1 add up to $1 + 1 + 1 + 1 = 4$.

In one sentence: A geometric series adds up a list where each term is the one before it times a fixed number, and this formula finds the whole sum in one step.

$\sum_{k=0}^{n-1} r^{k} = \frac{1 - r^{n}}{1 - r} \quad (r \neq 1)$

Read it out loud: “The sum, written with the Greek capital letter sigma, for k from 0 up to n minus 1, of r to the power k, equals one minus r to the power n, divided by one minus r. This works when r is not equal to 1. The letter k is a counter, r is the common ratio that each term is multiplied by, and n is the number of terms.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

The sum sign $\sum$: The capital Greek letter sigma, written $\sum$ , means add up. Below it, $k = 0$ says where the counter starts, and the letter on top, $n - 1$ , says where it stops. So $\sum_{k=0}^{2} 2^{k}$ means $2^{0} + 2^{1} + 2^{2} = 1 + 2 + 4 = 7$ . The sum has $n$ terms when $k$ runs from 0 to $n - 1$ .
Powers, like $r^{k}$: A small raised number is an exponent. $r^{k}$ means $r$ multiplied by itself $k$ times, so $2^{3} = 2 \times 2 \times 2 = 8$ . Any number to the power 0 equals 1, so $r^{0} = 1$ . A negative exponent means divide: $2^{-1} = \frac{1}{2}$ , which is one half.
The common ratio $r$: In a geometric series, each term is the one before it times the same number $r$ , which is called the common ratio. With $r = 2$ the terms are 1, 2, 4, 8, 16. With $r = \frac{1}{2}$ the terms are 1, one half, one quarter, and so on. The list grows or shrinks by a fixed factor each time, not by a fixed amount.
Limits and getting close to a value: A limit is the value that a quantity gets closer and closer to as a counter keeps growing. The terms $\frac{1}{2}$ , $\frac{1}{4}$ , $\frac{1}{8}$ get closer and closer to 0. The sum $1 + \frac{1}{2} + \frac{1}{4} + \cdots$ gets closer and closer to 2, and it never goes past 2.
The not-equal sign $\neq$ and the dots $\cdots$: $r \neq 1$ means that $r$ is not equal to 1. The three dots $\cdots$ mean that the list continues in the same pattern, so $1 + 2 + 4 + \cdots + 512$ keeps doubling until the last term, 512. The dots are a shorthand for ‘and so on’.
Dynamic array (background): A dynamic array is a list stored in computer memory in one block with a fixed amount of room. When the block is full and a new item arrives, the program builds a new block twice as big and copies every old item across. Copying takes time, so the total copying work matters for how fast adding items is.
Reward discount factor $\gamma$ (background): In reinforcement learning, a method where a computer learns from rewards, a reward received later is worth less. The factor $\gamma$ (gamma, a Greek letter) is a number between 0 and 1, and a reward received $k$ steps later is multiplied by $\gamma^{k}$ . Adding these discounted rewards gives a geometric series.

What each symbol means

Symbol	Meaning
$\sum_{k=0}^{n-1}$	Add up the terms for every $k$ from 0 up to $n - 1$ . That is $n$ terms in all, because the counter starts at 0. The sum has no unit when the terms count things, such as copies or dollars.
$k$	The step counter, a whole number that starts at 0 and goes up by 1. The first term is at $k = 0$ , which is $r^{0} = 1$ . It counts positions in the list, so it has no unit.
$r^{k}$	The term at step $k$ : the number $r$ multiplied by itself $k$ times. For $r = 2$ and $k = 3$ , the term is $2 \times 2 \times 2 = 8$ . Its unit is the same unit as the terms of the list, such as copies.
$r$	The common ratio, the number each term is multiplied by to get the next term. For doubling, $r = 2$ . The formula needs $r \neq 1$ , because the division by $1 - r$ would be zero. The ratio has no unit.
$n$	The number of terms in the series, a whole number such as 4 or 10. It counts the terms that are added, so it has no unit. It is not the same thing as the size of the list being built in the example.
$\frac{1 - r^{n}}{1 - r}$	The closed form, a quick way to find the total. The top, $1 - r^{n}$ , is what is left after cancellation, and the bottom, $1 - r$ , is the factor that remains. The division by $1 - r$ is why the formula excludes $r = 1$ .

The formula piece by piece

$r^{k}$: The term at step $k$ , which is $r$ multiplied by itself $k$ times. When $k = 0$ the term is 1, when $k = 1$ it is $r$ , and when $k = 2$ it is $r \times r$ . The whole series is these terms added together.
$\sum_{k=0}^{n-1} r^{k}$: The total of all $n$ terms, from the first term at $k = 0$ to the last term at $k = n - 1$ . This is the total we want to find. The rest of the formula gives a faster way to find it than adding every term.
$r^{n}$: The term one step past the end of the list. It is the next term after $r^{n-1}$ , because $r^{n-1} \times r = r^{n}$ . Multiplying the whole sum by $r$ shifts every term one place along, so $r^{n}$ appears when the shifted list is lined up against the original.
$1 - r^{n}$: The leftover after the cancellation. When the shifted sum is subtracted from the original sum, almost every term cancels, and only the first term 1 and the last term $-r^{n}$ remain. Dividing by $1 - r$ turns that leftover into the total.
$\sum_{k=0}^{n-1} r^{k} = \frac{1 - r^{n}}{1 - r} \quad (r \neq 1)$: In one plain sentence: adding the first $n$ powers of $r$ , starting from $r^{0} = 1$ , gives 1 minus $r^{n}$ , divided by 1 minus $r$ , as long as $r$ is not equal to 1.

What the formula is doing, and why

What goes in and what comes out. You give the formula a ratio $r$ and a number of terms $n$ . You get the sum of the terms $r^{0}, r^{1}, \ldots, r^{n-1}$ . The ratio decides almost everything, because each term is the last one times $r$ . The formula gives the total directly, without adding each term one by one.

Why does the trick work? Call the sum $S$ . Multiply the whole list by $r$ , and every term moves one place along. Now subtract the shifted list from the original. Almost every term cancels, and $S - rS = 1 - r^{n}$ is what remains. Dividing by $1 - r$ gives $S = \frac{1 - r^{n}}{1 - r}$ . The division needs $r \neq 1$ , because $1 - r$ would then be zero. If $r = 1$ , every term is 1, and the sum is $n$ .

Why does the answer depend on whether $r$ is bigger than 1? If $r > 1$ , the terms grow, the last term is the biggest, and for large $n$ the sum is close to $\frac{r^{n}}{r - 1}$ . If $0 < r < 1$ , the terms shrink, and the sum settles toward $\frac{1}{1 - r}$ as $n$ grows. For $r = \frac{1}{2}$ , the sum $1 + \frac{1}{2} + \frac{1}{4} + \cdots$ gets close to 2.

Why is doubling cheap on average? The early steps are small, so the total is less than twice the final size. In the example below, the copies made while a list doubles add up to less than twice the number of items. The last copy alone is about half of all the copying, so the work is concentrated at the end.

An everyday picture

Think of a savings plan that doubles each week. You save 1 dollar in week 1, 2 dollars in week 2, 4 dollars in week 3, and so on. After 3 weeks your total is 1 + 2 + 4 = 7 dollars, which is one less than twice the 4 dollars you saved in week 3. In general, after $n$ weeks your total is one less than twice what you saved in the last week.

Worked example: Copies in a doubling array

A dynamic array starts with room for 1 item. When it is full and a new item arrives, it builds a new block with twice the room and copies every item across. We add 10 items and count the copies. The copies form a geometric series with ratio $r = 2$ . Its number of terms is the number $n$ in the formula, which is 4 here, not 10.

Find when the block is full. The block starts with room for 1 item. Adding item 2 finds the block full, so it copies 1 item into a new block with room for 2. Adding item 3 finds that block full, so it copies 2 items into a new block with room for 4.
Continue the pattern. Adding item 5 finds the room of 4 full, so it copies 4 items into room for 8. Adding item 9 finds the room of 8 full, so it copies 8 items into room for 16. Items 10 and beyond fit in that block, so no more copies happen while we add 10 items.
Write the copies as a series. The copies are 1, 2, 4 and 8. Each one is the one before times 2, so this is a geometric series with ratio $r = 2$ . It has 4 terms, so the formula’s $n$ is 4 here.
Add the terms. Adding the copies gives $1 + 2 + 4 + 8 = 15$ copies in total. This matches the pattern, because each term doubles the one before.
Apply the formula. With $r = 2$ and $n = 4$ , the formula gives $\frac{1 - 2^{4}}{1 - 2} = \frac{1 - 16}{-1} = \frac{-15}{-1} = 15$ . The two minus signs cancel, so the answer is 15 copies. Both methods agree.
Compare with the list size. The list holds 10 items, so twice the list size is $2 \cdot 10 = 20$ . Since 15 is less than 20, the total copying is less than twice the number of items. On average that is $\frac{15}{10} = 1.5$ copies per item.

Answer: Inserting 10 items causes 15 copies in total, which is less than $2 \cdot 10 = 20$ . In general, doubling keeps the total copying below twice the number of items, so each item costs about 2 copies or fewer on average.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Using the formula with $r = 1$ . The denominator $1 - r$ becomes zero, and division by zero is not allowed. When $r = 1$ , every term is 1, so the sum is $n$ .
Miscounting the terms. The sum from $k = 0$ to $n - 1$ has $n$ terms. The sum from $k = 1$ to $n$ also has $n$ terms, but it is different: it equals $r \cdot \frac{1 - r^{n}}{1 - r}$ , because every term is one step along.
Flipping the sign. The correct form is $\frac{1 - r^{n}}{1 - r}$ , not $\frac{r^{n} - 1}{1 - r}$ , which is the negative of the sum.
Mixing up $r$ and $n$ . The ratio $r$ says how much each term multiplies, and $n$ says how many terms there are. Swapping them gives a different sum.

Where you will meet it

Dynamic arrays that double in size, where the total copying stays below twice the final size.
Compound growth, such as an amount of money that is multiplied by the same factor each year.
Discounted rewards in reinforcement learning, where a reward received $k$ steps later is multiplied by $\gamma^{k}$ , so the total reward is a geometric series. The number $\gamma$ is between 0 and 1.
Full binary trees, which are trees where each node has two children. Level $k$ holds $2^{k}$ nodes, so the total node count is a geometric series.

Questions people ask

What happens when $r$ is greater than 1?

The formula still works. For $r = 2$ and 10 terms it gives $\frac{1 - 2^{10}}{1 - 2} = 1023$ . That equals $1 + 2 + \cdots + 512$ , and the last term, 512, is about half of the total.

Why does the sum settle when $r$ is between 0 and 1?

Each power $r^{n}$ shrinks toward 0 as $n$ grows. For example, $(\frac{1}{2})^{10} = \frac{1}{1024}$ , which is almost 0. The top of the formula then goes to 1, and the sum goes to $\frac{1}{1 - r}$ . For $r = \frac{1}{2}$ , that limit is 2.

Why is $r = 1$ a special case?

The formula divides by $1 - r$ , which is zero when $r = 1$ . In that case each term is 1, so the sum is $n$ . For example, four terms of 1 add up to $1 + 1 + 1 + 1 = 4$ .

Sum of the First n Integers: This formula gives the total of the numbers 1, 2, 3 and so on up to $n$ in one quick calculation, with no adding one number at a time.
Big O Notation: Big O notation is a way to say that one function never grows faster than another, once the input is big enough.
Binary Number Value: Binary uses only the digits 0 and 1, and this formula turns a row of those digits into the ordinary number they stand for.