Math Core

A sequence defined by a rule like $a_{n+1} = f(a_n)$ can look impossible to push out to the $2026$ th term, and a sum of $1000$ fractions can look impossible to add. On the AIME they never are. Either the sequence has a closed form, it repeats, or the sum telescopes: almost every term cancels and only the ends survive.

Telescoping sums

A sum telescopes when each term can be written as a difference $b_k - b_{k+1}$ of consecutive values of some sequence:

\sum_{k=1}^{n}(b_k - b_{k+1}) = (b_1 - b_2) + (b_2 - b_3) + \dots + (b_n - b_{n+1}) = b_1 - b_{n+1}.

The work is in finding $b_k$ . The standard tools:

Partial fractions. $\dfrac{1}{k(k+1)} = \dfrac1k - \dfrac{1}{k+1}$ , and more generally $\dfrac{1}{k(k+d)} = \dfrac1d\left(\dfrac1k - \dfrac{1}{k+d}\right)$ .
Rationalizing. $\dfrac{1}{\sqrt k + \sqrt{k+1}} = \sqrt{k+1} - \sqrt k$ .
Spotting a difference of squares or products. For example, $\dfrac{2k+1}{k^2(k+1)^2} = \dfrac{1}{k^2} - \dfrac{1}{(k+1)^2}$ because $(k+1)^2 - k^2 = 2k + 1$ .

Common mistake

With a gap of $d$ , as in $\dfrac1k - \dfrac1{k+2}$ , $d$ terms survive at each end, not one. Write out the first few and last few terms to see exactly which ones remain:

\sum_{k=1}^{n}\left(\frac1k - \frac1{k+2}\right) = 1 + \frac12 - \frac1{n+1} - \frac1{n+2}.

Telescoping products

The same idea works with ratios: $\displaystyle\prod_{k=1}^{n}\frac{b_{k+1}}{b_k} = \frac{b_{n+1}}{b_1}$ . Factor each term, then look for factors that reappear shifted by one. For instance

1 - \frac1{k^2} = \frac{(k-1)(k+1)}{k \cdot k} = \frac{k-1}{k} \cdot \frac{k+1}{k},

and each of the two pieces telescopes separately.

Linear recursions

Characteristic equation

If $a_n = pa_{n-1} + qa_{n-2}$ , look for solutions of the form $a_n = r^n$ . Dividing by $r^{n-2}$ gives the characteristic equation

r^2 = pr + q.

If it has distinct roots $r_1, r_2$ , then every solution is $a_n = Ar_1^n + Br_2^n$ , where $A$ and $B$ are fixed by the first two terms.

Why it works: if two sequences both satisfy the recursion, so does any combination $A(\cdot) + B(\cdot)$ , and two free constants are exactly enough to match any two starting values. This is the same recursion you saw in Newton's sums: the power sums $r_1^n + r_2^n$ satisfy it automatically.

Periodic sequences

For a nonlinear rule, compute the first several terms exactly (as fractions). Often the sequence returns to its starting pair, and from then on it cycles. If the period is $T$ , then $a_n = a_{n \bmod T}$ (adjusting for a remainder of $0$ ), and a sum or product over many terms splits into full periods plus a leftover piece.

Worked examples

Worked example: Partial fractions

Compute $\dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \dots + \dfrac{1}{99 \cdot 100}$ .

Each term is $\dfrac1k - \dfrac1{k+1}$ , so the sum is $1 - \dfrac1{100} = \dfrac{99}{100}$ .

Worked example: A product of cubes

Compute $\displaystyle\prod_{k=2}^{10}\frac{k^3 - 1}{k^3 + 1}$ .

Factor: $\dfrac{k^3 - 1}{k^3 + 1} = \dfrac{k - 1}{k + 1} \cdot \dfrac{k^2 + k + 1}{k^2 - k + 1}$ .

The first factors give $\dfrac13 \cdot \dfrac24 \cdot \dfrac35 \cdots \dfrac{9}{11} = \dfrac{1 \cdot 2}{10 \cdot 11} = \dfrac{1}{55}$ .

For the second factors, notice $k^2 - k + 1 = (k-1)^2 + (k-1) + 1$ . So with $c_k = k^2 + k + 1$ , the factor is $\dfrac{c_k}{c_{k-1}}$ , and the product is $\dfrac{c_{10}}{c_1} = \dfrac{111}{3} = 37$ .

The answer is $\dfrac{37}{55}$ .

Worked example: A linear recursion

A sequence has $a_0 = 0$ , $a_1 = 5$ and $a_n = a_{n-1} + 6a_{n-2}$ for $n \ge 2$ . Find $a_5$ .

The characteristic equation $r^2 = r + 6$ has roots $3$ and $-2$ , so $a_n = A \cdot 3^n + B(-2)^n$ . From $a_0 = 0$ : $B = -A$ . From $a_1 = 5$ : $3A + 2A = 5$ , so $A = 1$ . Thus $a_n = 3^n - (-2)^n$ and $a_5 = 243 + 32 = 275$ .

Check by direct computation: $a_2 = 5$ , $a_3 = 35$ , $a_4 = 65$ , $a_5 = 65 + 210 = 275$ .

Worked example: A periodic sequence

A sequence satisfies $a_{n+2} = a_{n+1} - a_n$ with $a_1 = 4$ and $a_2 = 7$ . Find $a_1 + a_2 + \dots + a_{100}$ .

The terms are $4, 7, 3, -4, -7, -3, 4, 7, \dots$ . The sequence has period $6$ , and each full period sums to $0$ . Since $100 = 6 \cdot 16 + 4$ , the sum equals $a_1 + a_2 + a_3 + a_4 = 4 + 7 + 3 - 4 = 10$ .

Tip

To find the right telescoping form for a nonlinear recursion, try rewriting it in terms of $\dfrac{1}{a_n}$ or $a_n - c$ for a well-chosen constant $c$ . A good substitution often turns the recursion into $b_{n+1} = b_n + (\text{something simple})$ .