Telescoping & Recursion

Study Sheet

Telescoping & Recursion

Sums that collapse and sequences that build

Making Long Computations Short

Tip
Telescoping sums

Partial fractions turn 1k(k+1)\dfrac{1}{k(k+1)} into 1k−1k+1\dfrac1k - \dfrac{1}{k+1}, so the sum telescopes: ∑k=1n1k(k+1)=1−1n+1\sum_{k=1}^{n} \dfrac{1}{k(k+1)} = 1 - \dfrac{1}{n+1}.

In plain terms. Write each term as a difference; everything in the middle cancels.

Example. ∑k=191k(k+1)=1−110=910\sum_{k=1}^{9} \dfrac{1}{k(k+1)} = 1 - \dfrac{1}{10} = \dfrac{9}{10}.

Concept
Linear recursions

When each state comes from the previous ones — like an=an−1+an−2a_n = a_{n-1} + a_{n-2} — compute forward from the base cases rather than hunting for a formula.

In plain terms. Build the answer step by step; ten steps of arithmetic beat an hour of algebra.

Example. Climbing 5 stairs taking 1 or 2 at a time: 1,2,3,5,81, 2, 3, 5, 8 — there are 88 ways (a Fibonacci-type recursion).

Tip
Circle power tools together
chords of a circle

Ptolemy's theorem (AC⋅BD=AB⋅CD+AD⋅BCAC \cdot BD = AB \cdot CD + AD \cdot BC in a cyclic quadrilateral) and the Power of a Point (AP⋅PB=CP⋅PDAP \cdot PB = CP \cdot PD for chords through PP) often chain together in one problem.

In plain terms. In circle problems, name the theorem each length fact comes from and the algebra falls out.

Example. Cyclic ABCDABCD with diameter AC=25AC = 25, AB=7AB = 7, BC=24BC = 24, CD=20CD = 20, DA=15DA = 15: Ptolemy gives BD=7⋅20+15⋅2425=20BD = \dfrac{7 \cdot 20 + 15 \cdot 24}{25} = 20.