Algebra · Chapter 17

Special Sequences

Closed forms for sums of integers, odd numbers, squares and cubes, plus telescoping sums and products and sequences that repeat.

What's this chapter about?

17.0 Sums of Powers
17.1 Telescoping
17.2 Practice Problems

You'll need

open on YouTube

17.00%

Sums of Powers

In this section you will be able to add up 1 + 2 + ⋯ + n, the odd numbers, the even numbers, the squares and the cubes in one step each.

Seven cubes with sides 1 to 7 are stacked into a tower. Its surface area is a sum of squares in disguise, and one formula adds them all at once.

Each formula in this section turns a long sum into a short product. The pictures show why: the pieces of the sum fit together into a square or a rectangle, and the area of that shape is the closed form.

Look: the odd numbers are the L-shapes that grow a square, so $1 + 3 + \cdots + (2n - 1) = n^2$ . The cubes are bigger L-shapes that grow a square of side $1 + 2 + \cdots + n$ .

Exploreplay first, formulas later

Try this: Odd numbers: press Add one more. Which L-shape did you add, and what square do you get now?
Try this: Switch to Even numbers. Why is 2 + 4 + ⋯ + 2n a rectangle n by n + 1, not a square?
Try this: Squares with n = 4: add the copies one at a time. How wide and how tall is the final rectangle?
Try this: Cubes with n = 3: compare 1 + 8 + 27 with (1 + 2 + 3)². Why does each L-shaped layer hold k³ cells?

Name it

Theorem 17.0.1 · Sum of numbers formula

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

Theorem 17.0.2 · Sum of odd numbers formula

1 + 3 + 5 + \cdots + (2n - 1) = n^2

In simple terms, the sum of the first $n$ odd numbers is $n^2$ .

Theorem 17.0.3 · Sum of even numbers formula

2 + 4 + 6 + \cdots + 2n = n(n+1)

To think about it intuitively, just take $2$ out of each term:

2(1 + 2 + 3 + \cdots + n) = 2 \cdot \frac{n(n+1)}{2} = n(n+1).

Theorem 17.0.4 · Sum of squares formula

1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}

Theorem 17.0.5 · Sum of cubes formula

1^3 + 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2

Try it

Problem 17.2.15(additional)

AMC 10Challenge

The sum of the first $m$ positive odd integers is $212$ more than the sum of the first $n$ positive even integers. What is the sum of all possible values of $n$ ?

Problem 17.2.3

AMC 10

Seven cubes, whose volumes are $1$ , $8$ , $27$ , $64$ , $125$ , $216$ , and $343$ cubic units, are stacked vertically to form a tower in which the volumes of the cubes decrease from bottom to top. Except for the bottom cube, the bottom face of each cube lies completely on top of the cube below it. What is the total surface area of the tower (including the bottom) in square units?

copies3

Three copies of the sum fill a 28 × 15 rectangle, so the sum is a third of it.

1² + 2² + 3² + 4² + 5² + 6² + 7² = 140

1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} \;\Rightarrow\; \frac{7 \cdot 8 \cdot 15}{6} = 140

Contest cornerreal contest problems

Problem 17.2.4

AMC 12

Rows $1$ , $2$ , $3$ , $4$ , and $5$ of a triangular array of integers are shown below:

\begin{array}{ccccccccc} &&&& 1 &&&& \\ &&& 1 && 1 &&& \\ && 1 && 3 && 1 && \\ & 1 && 5 && 5 && 1 & \\ 1 && 7 && 11 && 7 && 1 \end{array}

Each row after the first row is formed by placing a $1$ at each end of the row, and each interior entry is $1$ greater than the sum of the two numbers diagonally above it in the previous row. What is the units digit of the sum of the $2023$ numbers in the $2023$ rd row?

Checkpoint for section 17.0

Get 2 of 3 right to master this section. One try each, no hints.

17.10%

Telescoping

In this section you will be able to collapse long sums and products by cancelling neighbors, and spot sequences that repeat.

The fraction $\frac{1}{k^2 + k}$ splits into $\frac1k - \frac1{k+1}$ . Add a block of them and almost everything cancels.

A telescoping sum is a chain where each term’s back half cancels the next term’s front half, like the sections of a collapsing telescope. Write the first few and last few terms, cross out the matching pieces, and keep what is left.

Products telescope too: in $\frac21 \cdot \frac32 \cdot \frac43$ , each numerator cancels the next denominator.

A recurrence can also fold back on itself. When the terms start repeating, a huge index like $x_{975}$ is just a small one in disguise. Find the cycle length and reduce the index.

Exploreplay first, formulas later

Try this: Press Cancel next until you can't. Which two pieces survive?
Try this: Change the last k. Which surviving piece moves, and which one stays put?
Try this: Press Show me on the Telescoping card. What does the product head towards as the last k grows?

Name it

Concept 17.1.1 · Telescoping

Expand the first few and last few terms, and cancel out any terms you see.

Watch itpredict, then reveal

Example 17.1

AIME

Consider the sequence defined by $a_k = \dfrac{1}{k^2 + k}$ for $k \ge 1$ . Given that $a_m + a_{m+1} + \cdots + a_{n-1} = \dfrac{1}{29}$ , for positive integers $m$ and $n$ with $m < n$ , find $m + n$ .

1
Factor the denominator: $k^2 + k = k(k+1)$ . Which difference of two simple fractions equals $\frac{1}{k(k+1)}$ ?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Example 17.2

Omega Learn

Let the sequence $a_n$ be defined as $a_n = 3^{1+2+3+\cdots+n}$ for all positive integers $n$ . Sohil is trying to evaluate the following sequence: $\frac{1}{2} \times \frac{2}{3} \times \frac{3}{4} \times \cdots$ . Because of his bad handwriting, he accidentally writes a plus sign instead of the multiplication sign before all fractions of the form $\frac{a_n}{a_n + 1}$ (for example, $\frac{3^1}{3^1 + 1}, \frac{3^{(1+2)}}{3^{(1+2)} + 1}, \ldots$ ). What is the value of the new expression?

1
Find the first few terms: $a_1 = 3^1$ , $a_2 = 3^{1+2}$ , $a_3 = 3^{1+2+3}$ . What is $a_3$ ?

Predict first:
Your prediction

open on YouTube

Example 17.3

AIME

Given that

\begin{aligned} x_1 &= 211, \\ x_2 &= 375, \\ x_3 &= 420, \\ x_4 &= 523, \text{ and} \\ x_n &= x_{n-1} - x_{n-2} + x_{n-3} - x_{n-4} \text{ when } n \ge 5, \end{aligned}

find the value of $x_{531} + x_{753} + x_{975}$ .

1
Compute the next term, $x_5 = x_4 - x_3 + x_2 - x_1$ .

Predict first:
Your prediction

open on YouTube

Try it

Problem 17.2.1

AMC 8

What is the value of the product

\left(\frac{1 \cdot 3}{2 \cdot 2}\right)\left(\frac{2 \cdot 4}{3 \cdot 3}\right)\left(\frac{3 \cdot 5}{4 \cdot 4}\right) \cdots \left(\frac{97 \cdot 99}{98 \cdot 98}\right)\left(\frac{98 \cdot 100}{99 \cdot 99}\right)?

Problem 17.2.8(additional)

AHSME

Find the sum $\dfrac{1}{1(3)} + \dfrac{1}{3(5)} + \cdots + \dfrac{1}{(2n-1)(2n+1)} + \cdots + \dfrac{1}{255(257)}$ .

Problem 17.2.12(additional)

Evaluate

\left(1 - \left(\frac13\right)^2\right)\left(1 - \left(\frac14\right)^2\right)\left(1 - \left(\frac15\right)^2\right) \cdots

Contest cornerreal contest problems

Problem 17.2.2

AMC 10

Let $f(x) = x^2(1 - x)^2$ . What is the value of the sum

f\left(\frac{1}{2019}\right) - f\left(\frac{2}{2019}\right) + f\left(\frac{3}{2019}\right) - f\left(\frac{4}{2019}\right) + \cdots + f\left(\frac{2017}{2019}\right) - f\left(\frac{2018}{2019}\right)?

Problem 17.2.6(additional)

AHSME

If $T_n = 1 + 2 + 3 + \cdots + n$ and

P_n = \frac{T_2}{T_2 - 1} \cdot \frac{T_3}{T_3 - 1} \cdot \frac{T_4}{T_4 - 1} \cdot \cdots \cdot \frac{T_n}{T_n - 1}

for $n = 2, 3, 4, \ldots$ , then $P_{1991}$ is closest to which of the following numbers?

Problem 17.2.10(additional)

AMC 10

The Fibonacci sequence $1, 1, 2, 3, 5, 8, 13, 21, \ldots$ starts with two $1$ s, and each term afterwards is the sum of its two predecessors. Which one of the ten digits is the last to appear in the units position of a number in the Fibonacci sequence?

Problem 17.2.13(additional)

AIME

A sequence of integers $a_1, a_2, a_3, \ldots$ is chosen so that $a_n = a_{n-1} - a_{n-2}$ for each $n \ge 3$ . What is the sum of the first $2001$ terms of this sequence if the sum of the first $1492$ terms is $1985$ , and the sum of the first $1985$ terms is $1492$ ?

Problem 17.2.14(additional)

AMC 12

Set $u_0 = \frac14$ , and for $k \ge 0$ let $u_{k+1}$ be determined by the recurrence

u_{k+1} = 2u_k - 2u_k^2.

This sequence tends to a limit; call it $L$ . What is the least value of $k$ such that

|u_k - L| \le \frac{1}{2^{1000}}?

Problem 17.2.5

AMC 10Challenge

Hiram's algebra notes are $50$ pages long and are printed on $25$ sheets of paper; the first sheet contains pages $1$ and $2$ , the second sheet contains pages $3$ and $4$ , and so on. One day he leaves his notes on the table before leaving for lunch, and his roommate decides to borrow some pages from the middle of the notes. When Hiram comes back, he discovers that his roommate has taken a consecutive set of sheets from the notes and that the average (mean) of the page numbers on all remaining sheets is exactly $19$ . How many sheets were borrowed?

Checkpoint for section 17.1

Get 2 of 3 right to master this section. One try each, no hints.

17.2

Practice Problems

In this section you will be able to mix sums of powers, telescoping and repeating sequences on harder contest problems.

These five problems need a sum formula, a telescoping product or a pattern you have to prove. Every problem has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Contest cornerreal contest problems

Problem 17.2.7(additional)

AMC 12

Let $A$ be the set of positive integers that have no prime factors other than $2$ , $3$ , or $5$ . The infinite sum

\frac11 + \frac12 + \frac13 + \frac14 + \frac15 + \frac16 + \frac18 + \frac19 + \frac1{10} + \frac1{12} + \frac1{15} + \frac1{16} + \frac1{18} + \frac1{20} + \cdots

of the reciprocals of the elements of $A$ can be expressed as $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. What is $m + n$ ?

Problem 17.2.9(additional)

AMC 12B

Consider a decreasing sequence of $n$ positive integers $x_1 > x_2 > \cdots > x_n$ that satisfies the following conditions: The average of the first $3$ terms in the sequence is $2025$ . For all $4 < k < n$ , the average of the first $k$ terms is $1$ less than the average of the first $k - 1$ terms. What is the greatest possible value of $n$ ?

Problem 17.2.11(additional)

AIME

Call a three-term strictly increasing arithmetic sequence of integers special if the sum of the squares of the three terms equals the product of the middle term and the square of the common difference. Find the sum of the third terms of all special sequences.

Problem 17.2.16(additional)

AIMEChallenge

The sequence $\{a_n\}$ is defined by

a_0 = 1, \quad a_1 = 1, \quad \text{and} \quad a_n = a_{n-1} + \frac{a_{n-1}^2}{a_{n-2}} \text{ for } n \ge 2.

The sequence $\{b_n\}$ is defined by

b_0 = 1, \quad b_1 = 3, \quad \text{and} \quad b_n = b_{n-1} + \frac{b_{n-1}^2}{b_{n-2}} \text{ for } n \ge 2.

Find $\dfrac{b_{32}}{a_{32}}$ .

Problem 17.2.17(additional)

AIMEChallenge

The terms of the sequence $(a_i)$ defined by $a_{n+2} = \dfrac{a_n + 2009}{1 + a_{n+1}}$ for $n \ge 1$ are positive integers. Find the minimum possible value of $a_1 + a_2$ .