total = 0
# k = 1, 2, ..., 100:
# range stops before 101
for k in range(1, 101):
total = total + k
n = 100
print("loop:", total)
print("formula:", n * (n + 1) // 2)loop: 5050
formula: 5050Arithmetic and geometric sums
Add 1 + 2 + … + n by pairing the first term with the last, any arithmetic sum as n times the average of its ends, and a geometric sum by multiplying by the ratio and subtracting. With a ratio between -1 and 1 the total levels off, which is why a discounted reward stays finite.
M01.7.3L0 Foundation25 minIn review
Before this lesson
M01.7.2 Sigma notation M01.6.4 Contradiction and induction
After this lesson you can
- Derive 1 + 2 + … + n = n(n + 1)/2 by pairing the first term with the last, and confirm it by induction.
- Add any arithmetic sum as the number of terms times the average of its first and last terms.
- Derive the sum of a geometric sequence by multiplying by the ratio and subtracting, and use it to add 1 + 2 + 4 + … + 1024.
- Explain with a table of totals why a geometric sum whose ratio lies between -1 and 1 levels off at a/(1 - r), and why other ratios do not.
- Check each formula against a running total in Python, with a loop, itertools.accumulate and numpy.cumsum.
In review. The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.
The question
An agent in reinforcement learning earns a reward of 1 at every step, but a reward one step away counts only 0.9 as much, one two steps away 0.81, and so on. Its total is 1 + 0.9 + 0.81 + 0.729 + …, for as long as it runs. Run it for a thousand steps, or a million: does the total grow without end? It never passes 10. Why 10, and how do you add a thousand terms without adding them one by one?
From the last lesson
1. Write \({1 + 4 + 9 + 16 + 25}\) with a sigma.
Show answer
\({\sum_{k=1}^{5} k^2}\), which is 55.
2. What is \({\sum_{i=1}^{10} 3}\)?
Show answer
\({10 \times 3 = 30}\): the term 3 is added once for each of the ten values of \(i\).
Intuition
Some long sums can be added without doing the adding. Two pictures show how.
Two sums as areas. Left: the numbers 1 to 5 stand as a staircase, and a second copy turned upside down fills it out to a rectangle, 5 columns of height 6. Right: halves, quarters, eighths and so on fill a square of area 1. Each piece fills half of the gap that is left, so the pieces never overflow, however many there are.
On the left, each column holds one number and its partner: 1 with 5, 2 with 4, 3 with 3. Each pair adds to 6. Two copies of the sum make \({5 \times 6 = 30}\), so one copy is 15.
On the right, the total \({\tfrac12 + \tfrac14 + \tfrac18 + \dots}\) keeps growing, but by less each time, and it can never pass the area of the square. It levels off at 1.
Build it up
Step 1. Pair the first with the last. To add \({1 + 2 + \dots + 100}\), write the sum forwards and then backwards, and add the two rows column by column:
\[ \begin{aligned} S &= 1 + 2 + \dots + 99 + 100 \\ S &= 100 + 99 + \dots + 2 + 1 \\ 2S &= 101 + 101 + \dots + 101 + 101 \end{aligned} \]
Every column adds to 101, and there are 100 columns, so \({2S = 100 \times 101 = 10{,}100}\) and \({S = 5050}\).
Step 2. Any arithmetic sum. The trick works whenever the terms go up by a fixed step. Going forwards the terms rise by \(d\) and going backwards they fall by \(d\), so every column has the same total: the first term plus the last.
The sum \({2 + 5 + 8 + 11 + 14}\) and the same sum back to front. Every column is the first term plus the last, 16.
Here \({2S = 5 \times 16 = 80}\), so \({S = 40}\). Put another way, \({S = 5 \times 8}\): the number of terms times the average of the first and the last.
Step 3. Multiply and subtract. Pairing fails for a geometric sum, because \({1 + 1024}\) is not \({2 + 512}\). Instead, multiply the whole sum by the ratio. Every term moves one place along, so the two rows share all but two terms.
Doubling \({1 + 2 + 4 + \dots + 1024}\) moves every term one place to the right. Subtract the top row from the bottom row: the grey terms cancel in pairs, and only \({2048 - 1}\) is left.
So \({2S - S = 2048 - 1}\), which says \({S = 2047}\). Adding the eleven terms one by one gives the same.
Step 4. Terms that fade. Now take the hook’s rewards, with ratio 0.9. Let \(S_n\) be the total of the first \(n\) of them. Multiply by 0.9 and subtract, exactly as in step 3:
\[ \begin{aligned} S_n &= 1 + 0.9 + \dots + 0.9^{\,n-1} \\ 0.9\,S_n &= 0.9 + \dots + 0.9^{\,n} \end{aligned} \]
Subtract the second line from the first. Every term cancels except the 1 at the front and the \(0.9^{\,n}\) at the end:
\[ S_n - 0.9\,S_n = 1 - 0.9^{\,n} . \]
The left side is \(0.1\,S_n\), so \({S_n = 10\,(1 - 0.9^{\,n})}\). A power of 0.9 is never negative, so \(S_n\) never passes 10. And the powers keep shrinking, so \(S_n\) creeps ever closer to 10:
| \(n\) | \(0.9^{\,n}\) | \(S_n\) |
|---|---|---|
| 1 | 0.9 | 1 |
| 10 | 0.3487 | 6.5132 |
| 50 | 0.0052 | 9.9485 |
| 100 | 0.0000266 | 9.9997 |
The formal statement
Here \(a\) is the first term and \(r\) the ratio of the geometric sum. Each line is derived below.
The first \(n\) whole numbers. Write the sum forwards and backwards as in step 1. Column \(k\) holds \(k\) from the first row and \({n + 1 - k}\) from the second, which add to \({n + 1}\). There are \(n\) columns, so \({2S = n(n + 1)}\) and \({S = n(n + 1)/2}\).
Confirmed by induction (M01.6.4). At \({n = 1}\) the formula gives \({1 \times 2 / 2 = 1}\), which is right. Now suppose it holds for some \(m\), so \({1 + \dots + m = m(m + 1)/2}\). Add the next number:
\[ \begin{aligned} &1 + \dots + m + (m + 1) \\ &\quad = \frac{m(m + 1)}{2} + (m + 1) \\ &\quad = (m + 1)\Big(\frac{m}{2} + 1\Big) \\ &\quad = \frac{(m + 1)(m + 2)}{2} . \end{aligned} \]
That is the formula with \({m + 1}\) in place of \(n\), so it holds for every \(n\).
Any arithmetic sum. Column \(k\) holds \({a_k = a_1 + (k - 1)d}\) and its partner \({a_{n+1-k}}\), which is \({a_1 + (n - k)d}\). Their sum
\[ \begin{aligned} &a_k + a_{n+1-k} \\ &\quad = 2a_1 + (k - 1 + n - k)\,d \\ &\quad = a_1 + \big(a_1 + (n - 1)\,d\big) \\ &\quad = a_1 + a_n \end{aligned} \]
does not depend on \(k\), so \({2S = n(a_1 + a_n)}\), and \(S\) is \(n\) times the average of the first and last terms. With \({a_1 = 1}\) and \({d = 1}\) this is the first result again.
Any geometric sum. Write the sum, multiply it by \(r\), and subtract:
\[ \begin{aligned} S &= a + a r + \dots + a r^{\,n-1} \\ r\,S &= a r + a r^2 + \dots + a r^{\,n} \\ S - r\,S &= a - a r^{\,n} \end{aligned} \]
The left side is \({S(1 - r)}\) and the right side is \({a(1 - r^{\,n})}\). Dividing by \({1 - r}\), which is allowed because \({r \neq 1}\), gives the formula. When \({r = 1}\) every term is \(a\) and the sum is \(n\,a\).
Levelling off. Split the formula into a part that does not change with \(n\) and a part that does:
\[ S_n = \frac{a}{1 - r} - \frac{a\, r^{\,n}}{1 - r} . \]
When \(r\) is between \({-1}\) and \(1\), \(r^{\,n}\) shrinks towards 0 as \(n\) grows. For \({r = 0.9}\), \({0.9^7 \approx 0.4783}\), less than a half, so every 7 terms at least halve the gap, and 70 terms cut it below \(\tfrac{1}{1024}\) of where it started. The total then comes as close to \({a / (1 - r)}\) as you like. For \(r\) between 0 and 1 (and \({a > 0}\)) the gap is positive, so the totals stay below that level, as the rewards stay below 10. For \(r\) between \({-1}\) and 0 the gap changes sign at every term, so the totals step above and below the level. “As close as you like” is a limit, which M04.8 makes exact; here the table is the evidence.
When \({r \ge 1}\) or \({r \le -1}\) the terms do not shrink, and the totals never level off.
Go deeper: 0.999... is exactly 1
The decimal \({0.999\ldots}\), with nines for ever, means the value that the totals \({0.9, 0.99, 0.999, \dots}\) level off at. Those totals are a geometric sum with \({a = 0.9}\) and \({r = 0.1}\), so they level off at
\[ \frac{a}{1 - r} = \frac{0.9}{1 - 0.1} = \frac{0.9}{0.9} = 1 . \]
The gap after \(n\) nines is \(0.1^{\,n}\), which can be made smaller than any number you name. No number fits between \({0.999\ldots}\) and 1, so they are the same number.
Worked example
The discounted rewards. A reward of 1 at every step, each counted 0.9 times the one before, is a geometric sum with \({a = 1}\) and \({r = 0.9}\). After \(n\) steps the total is
\[ \begin{aligned} S_n &= \frac{1 \times (1 - 0.9^{\,n})}{1 - 0.9} \\ &= 10\,(1 - 0.9^{\,n}) . \end{aligned} \]
After 10 steps, \({0.9^{10} \approx 0.3487}\), so \({S_{10} \approx 6.5132}\). After 20 steps, \({S_{20} \approx 8.7842}\), and after 40 steps, \({S_{40} \approx 9.8522}\).
The rewards shrink by a factor 0.9 at each step, so each climb of the total is smaller than the last. The total approaches 10 and never reaches it: after 40 terms it is still about 0.1478 short.
How many steps until the total is within 0.01 of 10? The gap is \({10 \times 0.9^{\,n}}\), and we want it below 0.01:
\[ \begin{aligned} 10 \times 0.9^{\,n} &< 0.01 \\ 0.9^{\,n} &< 0.001 . \end{aligned} \]
Take natural logarithms of both sides. The logarithm keeps the order of positive numbers, and it turns the power into a product (M01.4.3): \({n \ln 0.9 < \ln 0.001}\). The number \(\ln 0.9\) is negative, and dividing both sides by a negative number flips the sign (M01.1.3):
\[ n > \frac{\ln 0.001}{\ln 0.9} \approx 65.56 . \]
So 66 steps are needed. Check: \({10 \times 0.9^{65} \approx 0.0106}\), still too big, while \({10 \times 0.9^{66} \approx 0.0096}\).
The doubling sum. With \({a = 1}\), \({r = 2}\) and \({n = 11}\) terms, the formula gives
\[ \begin{aligned} \frac{1 \times (1 - 2^{11})}{1 - 2} &= \frac{1 - 2048}{-1} \\ &= 2047 , \end{aligned} \]
which matches step 3. With \({r = 2}\) there is no level to approach: each total is one less than the next power of 2.
Code
First the sum of the whole numbers to 100, by a loop and by the formula.
The // divides and keeps a whole number. Since \({n(n + 1)}\) is always even, nothing is lost. Now the geometric sum as a function, with the case \({r = 1}\) handled on its own.
def geometric_sum(a, r, n):
"""The total of a, a*r, ..., a*r**(n - 1)."""
if r == 1:
# every term equals a
return n * a
return a * (1 - r ** n) / (1 - r)
total = 0
# 2**0 up to 2**10
for k in range(11):
total = total + 2 ** k
print("loop:", total)
print("formula:", geometric_sum(1, 2, 11))
print("40 rewards:", round(geometric_sum(1, 0.9, 40), 4))loop: 2047
formula: 2047.0
40 rewards: 9.8522The formula prints 2047.0, not 2047: dividing with / always gives a decimal number in Python, even when the answer is whole. The library builds every running total at once. itertools.accumulate turns a list of terms into the list of totals \({S_1, S_2, S_3, \dots}\), and numpy.cumsum does the same to an array.
import itertools
import numpy as np
rewards = []
for k in range(40):
# 1, 0.9, 0.81, ...
rewards.append(0.9 ** k)
# running totals S_1 to S_40
totals = list(itertools.accumulate(rewards))
print("S_10:", round(totals[9], 4))
print("S_20:", round(totals[19], 4))
print("S_40:", round(totals[39], 4))
print("numpy.cumsum:", round(np.cumsum(rewards)[39], 4))S_10: 6.5132
S_20: 8.7842
S_40: 9.8522
numpy.cumsum: 9.8522Finally the hook’s claim. Add 200 rewards one at a time and watch for the total reaching 10.
total = 0.0
reached_ten = False
for k in range(200):
total = total + 0.9 ** k
if total >= 10:
reached_ten = True
print("total of 200 rewards:", round(total, 10))
print("ever reached 10:", reached_ten)total of 200 rewards: 9.9999999929
ever reached 10: FalseThe total gets within a hundred-millionth of 10 and stays below it. In reinforcement learning such a total of discounted rewards is called the return (RL01.5), and the discount rate, here 0.9, is written \(\gamma\). For a reward of 1 at every step it levels off at \({1/(1 - \gamma)}\).
Explore
M01.7-X1
Sum builder
Press Play to add the rewards 1, 0.9, 0.81 one at a time, and watch the total climb towards the dashed line without reaching it. Then try the ratio 2 with 11 terms (the doubling sum, 2047), the ratio −0.5 (the totals zigzag round \(\tfrac23\)), and the ratio 1, and switch to arithmetic to add \({1 + 2 + \dots + n}\).
The sigma, the written-out terms and the closed formula always agree. With a ratio between \({-1}\) and 1 the read-out also gives the level, \({a / (1 - r)}\), and the gap that is left.
Pitfalls
Wrong beside right. With \({r = 2}\) the level formula gives \({-1}\), a number the totals never come near. With \({r = 0.5}\) the totals do level off at \({a/(1 - r) = 2}\).
“Every geometric sum adds up to a/(1 − r) in the end.”
Only when \(r\) is between \({-1}\) and 1. For \({1 + 2 + 4 + \dots}\) the formula gives \({1/(1 - 2) = -1}\), a negative answer for a sum of positive numbers, while the totals 1, 3, 7, 15 run away. The sum of the first \(n\) terms, \({a(1 - r^{\,n})/(1 - r)}\), is right for every \(r\) except 1. The level \({a/(1 - r)}\) is not.
“Any arithmetic sum is n(n + 1)/2.”
That is only \({1 + 2 + \dots + n}\). For \({2 + 5 + 8 + 11 + 14}\) it would give 15, but the sum is 40. Use \(n\) times the average of the first and last terms.
“From 5 to 20 there are 15 terms.”
There are \({20 - 5 + 1 = 16}\). Count both ends, as in M01.7.2. The sum \({5 + 6 + \dots + 20}\) is \({16 \times (5 + 20)/2 = 200}\).
“The last term of the geometric sum is \(a r^{\,n}\).”
It is \({a r^{\,n-1}}\), because the first term is \(a r^0\). The \(r^{\,n}\) in the formula is the term after the last, the one that is left over when the rows are subtracted.
Check yourself
Recall
1. What is \({1 + 2 + \dots + 10}\)?
Show answer
\({10 \times 11 / 2 = 55}\).
2. How do you add an arithmetic sum without adding its terms one by one?
Show answer
Multiply the number of terms by the average of the first and last terms: \({n(a_1 + a_n)/2}\).
3. What is the sum of the \(n\) terms \({a, ar, \dots, ar^{\,n-1}}\), and when does the formula fail?
Show answer
\({a(1 - r^{\,n})/(1 - r)}\). It fails at \({r = 1}\), where it would divide by 0; there the sum is \(n\,a\).
4. What does \({1 + 0.5 + 0.25 + \dots}\) level off at?
Show answer
At 2. The level is \(a/(1 - r)\), and here \({1/(1 - 0.5) = 2}\).
5. A reward of 1 at every step is discounted by 0.9 per step. Why can the total never pass 10?
Show answer
After \(n\) steps the total is \({10(1 - 0.9^{\,n})}\), and \(0.9^{\,n}\) is always positive, so the total is always less than 10.
Exercises
1. ★ Find \({3 + 7 + 11 + \dots + 99}\).
Show solution
It is arithmetic with \({a_1 = 3}\) and \({d = 4}\). The last term is 99, so \({3 + (n - 1) \times 4 = 99}\), which gives \({n - 1 = 24}\) and \({n = 25}\) terms. The sum is
\[ \begin{aligned} 25 \times \frac{3 + 99}{2} &= 25 \times 51 \\ &= 1275 . \end{aligned} \]
2. ★★ Find \({\tfrac12 + \tfrac14 + \dots + \tfrac{1}{1024}}\) exactly, and say how far it is from 1.
Show solution
It is geometric with \({a = \tfrac12}\) and \({r = \tfrac12}\). Since \({1024 = 2^{10}}\), there are 10 terms. The formula gives
\[ \begin{aligned} \frac{\tfrac12\,(1 - \tfrac{1}{1024})}{1 - \tfrac12} &= 1 - \frac{1}{1024} \\ &= \frac{1023}{1024} . \end{aligned} \]
It is \(\tfrac{1}{1024}\) short of 1: the last empty corner of the square in the first figure.
3. ★★★ A reward of 2 at every step is discounted by 0.8 per step. Find the total of the first \(n\) rewards, the level it approaches, and the smallest \(n\) for which the total is within 0.01 of that level.
Show solution
It is geometric with \({a = 2}\) and \({r = 0.8}\), so the total of \(n\) rewards is
\[ \frac{2\,(1 - 0.8^{\,n})}{1 - 0.8} = 10\,(1 - 0.8^{\,n}) , \]
and the level is \({2/(1 - 0.8) = 10}\). The gap is \({10 \times 0.8^{\,n}}\), which must be below 0.01, so \({0.8^{\,n} < 0.001}\). Taking logarithms and dividing by the negative number \(\ln 0.8\):
\[ n > \frac{\ln 0.001}{\ln 0.8} \approx 30.96 . \]
So \({n = 31}\). Check: \({10 \times 0.8^{30} \approx 0.0124}\) and \({10 \times 0.8^{31} \approx 0.0099}\).
Summary card
Pair first with last; multiply and subtract; a ratio below 1 in size makes the total level off.
Two copies make a rectangle; halves fill a square.
- Whole numbers. \({1 + 2 + \dots + n}\) is \({n(n + 1)/2}\).
- Arithmetic. \(n\) times the average of the first and last terms.
- Geometric. \({a(1 - r^{\,n})/(1 - r)}\) for \({r \neq 1}\), so \({1 + 2 + \dots + 1024}\) is 2047.
- Levelling off. For \({-1 < r < 1}\) the totals approach \({a/(1 - r)}\); discounted rewards of 1 at 0.9 stay below 10.
Sources and next steps
Sources. Each was opened and checked against this lesson on 12 November 2026.
- Jay Abramson and others, Algebra and Trigonometry, 2nd edition (OpenStax), Section 13.4: the sum of the first \(n\) terms of an arithmetic series, \({n(a_1 + a_n)/2}\); of a geometric series, \({a_1(1 - r^{\,n})/(1 - r)}\) for \({r \neq 1}\); and the sum \({a_1/(1 - r)}\) of an infinite geometric series when \({-1 < r < 1}\).
- Eric Lehman, F. Thomson Leighton and Albert R. Meyer, Mathematics for Computer Science (MIT 6.042J, revised May 2015). Section 13.1.2, the perturbation method: multiply the sum by \(x\), subtract, and nearly every term cancels. Section 13.2: the sum written in two orders and added gives \({n(n + 1)/2}\).
- Richard Sutton and Andrew Barto, Reinforcement Learning: An Introduction, 2nd edition, Section 3.3: the discounted return (equation 3.8), and the return \({1/(1 - \gamma)}\) for a constant reward of \({+1}\) (equation 3.10).
- Richard Hammack, Book of Proof, third edition, Chapter 10, Exercise 1: prove by induction that \({1 + 2 + \dots + n = (n^2 + n)/2}\).
Next. M01.7.4 Products and double sums meets the product sign, the sums and products of nothing at all, and sums over a whole table.
This lesson unlocks
M01.7.4 Products and double sums M04.8 Sequences, series and Taylor approximation RL01.5 Returns, discounting and value functions (planned)
Your progress is saved in this browser only. No account, no tracking.