Sequences, Series & Recursion

Study Sheet

Sequences, Series & Recursion

Sums, telescoping, and recurrences

Standard Sums

Tip
Arithmetic and geometric series

Arithmetic: Sn=n2(a1+an)S_n = \tfrac n2(a_1+a_n). Geometric: Sn=a11−rn1−rS_n = a_1\dfrac{1-r^n}{1-r}, and if ∣r∣<1|r|<1, S∞=a11−rS_\infty = \dfrac{a_1}{1-r}.

In plain terms. For a steadily-growing list use the arithmetic sum; for one that multiplies each step use the geometric sum.

Example. 1+12+14+⋯=11−1/2=21 + \tfrac12 + \tfrac14 + \cdots = \dfrac{1}{1 - 1/2} = 2.

Concept
Telescoping

If each term is f(k)−f(k+1)f(k) - f(k+1), the sum collapses to f(1)−f(n+1)f(1) - f(n+1).

In plain terms. Write each piece as a difference so neighboring pieces cancel, leaving only the first and last.

Example. ∑k=1n1k(k+1)=∑(1k−1k+1)=1−1n+1\sum_{k=1}^{n}\tfrac1{k(k+1)} = \sum\left(\tfrac1k - \tfrac1{k+1}\right) = 1 - \tfrac1{n+1}.