Telescoping, Recursion, and Advanced Series

Pillar: CHAIN — "Telescoping collapses a chain; recurrences define one."

Telescoping: When Sums Self-Destruct

A telescoping sum is a sum where most terms cancel with adjacent terms, leaving only a few survivors. The technique is simple but extraordinarily powerful — it turns sums with thousands of terms into expressions with just two or three.

The Core Pattern

\[\sum_{k=1}^{n} \big(f(k) - f(k+1)\big) = f(1) - f(n+1)\]

Write out the terms to see why:

\[\underbrace{f(1)}\_{\text{survives}} - \cancel{f(2)} + \cancel{f(2)} - \cancel{f(3)} + \cancel{f(3)} - \cdots - \cancel{f(n)} + \cancel{f(n)} - \underbrace{f(n+1)}\_{\text{survives}}\]

Every intermediate value appears once positive and once negative. Only the very first and very last terms remain.

Partial Fractions: Manufacturing Telescopes

The challenge is recognizing that a sum can telescope. Partial fraction decomposition is the most common way to rewrite a term as a difference.

Pattern 1: \(\frac{1}{k(k+1)}\)

\[\frac{1}{k(k+1)} = \frac{A}{k} + \frac{B}{k+1}\]

Multiply both sides by \(k(k+1)\): \(1 = A(k+1) + Bk\).

Set \(k = 0\): \(1 = A\). Set \(k = -1\): \(1 = -B\), so \(B = -1\).

\[\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}\]

Application. \(\displaystyle\sum_{k=1}^{n} \frac{1}{k(k+1)} = 1 - \frac{1}{n+1} = \frac{n}{n+1}\).

Pattern 2: \(\frac{1}{k(k+d)}\)

More generally, for a gap of \(d\):

\[\frac{1}{k(k+d)} = \frac{1}{d}\left(\frac{1}{k} - \frac{1}{k+d}\right)\]

This telescopes with a "delay" — terms cancel \(d\) positions apart instead of adjacent ones.

Example. \(\displaystyle\sum_{k=1}^{n} \frac{1}{k(k+2)} = \frac{1}{2}\sum_{k=1}^{n}\left(\frac{1}{k} - \frac{1}{k+2}\right)\)

Writing out terms:

\[= \frac{1}{2}\left[\left(\frac{1}{1} - \frac{1}{3}\right) + \left(\frac{1}{2} - \frac{1}{4}\right) + \left(\frac{1}{3} - \frac{1}{5}\right) + \cdots\right]\]

The survivors are the first two terms (\(\frac{1}{1}, \frac{1}{2}\)) and the last two (\(-\frac{1}{n+1}, -\frac{1}{n+2}\)):

\[= \frac{1}{2}\left(\frac{3}{2} - \frac{1}{n+1} - \frac{1}{n+2}\right)\]

Pattern 3: Higher-Order Products

\[\frac{1}{k(k+1)(k+2)} = \frac{1}{2}\left(\frac{1}{k(k+1)} - \frac{1}{(k+1)(k+2)}\right)\]

Each pattern builds on the one before it.

Telescoping Products

Products can telescope when consecutive factors share numerators and denominators.

Example. Compute \(\displaystyle\prod_{k=1}^{n} \frac{k}{k+1}\).

\[= \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{3}{4} \cdots \frac{n}{n+1} = \frac{1}{n+1}\]

Example. Compute \(\displaystyle\prod_{k=2}^{n} \frac{k^2 - 1}{k^2}\).

Factor: \(\frac{k^2-1}{k^2} = \frac{(k-1)(k+1)}{k \cdot k}\).

\[= \frac{1 \cdot 3}{2 \cdot 2} \cdot \frac{2 \cdot 4}{3 \cdot 3} \cdot \frac{3 \cdot 5}{4 \cdot 4} \cdots \frac{(n-1)(n+1)}{n \cdot n} = \frac{n+1}{2n}\]

Recursively Defined Sequences

A recurrence relation defines each term of a sequence using previous terms. You have seen this before — the Fibonacci sequence is the most famous example.

Notation and Setup

A recurrence has three parts:

Initial conditions: the starting values (e.g., \(a_0 = 0\), \(a_1 = 1\))
Recurrence relation: the rule (e.g., \(a_n = a_{n-1} + a_{n-2}\))
Domain: which \(n\) the rule applies to (e.g., \(n \ge 2\))

Common Examples

Name	Recurrence	Initial Conditions
Fibonacci	\(F_n = F_{n-1} + F_{n-2}\)	\(F_0 = 0, F_1 = 1\)
Powers of 2	\(a_n = 2a_{n-1}\)	\(a_0 = 1\)
Factorial	\(n! = n \cdot (n-1)!\)	\(0! = 1\)
Tower of Hanoi	\(T_n = 2T_{n-1} + 1\)	\(T_1 = 1\)

Computing Terms

For small values, just iterate:

\(n\)	0	1	2	3	4	5	6	7	8	9	10
\(F_n\)	0	1	1	2	3	5	8	13	21	34	55

In code, always use iteration (a loop), not naive recursion. Naive recursion recomputes the same values exponentially many times.

Solving Linear Recurrences

A linear recurrence with constant coefficients has the form:

\[a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}\]

There is a systematic method to find a closed-form solution (no recursion needed).

Step 1: Write the Characteristic Equation

Replace \(a_n\) with \(r^n\). The recurrence \(a_n = c_1 a_{n-1} + c_2 a_{n-2}\) becomes:

\[r^n = c_1 r^{n-1} + c_2 r^{n-2}\]

Divide by \(r^{n-2}\):

\[r^2 = c_1 r + c_2\]

\[r^2 - c_1 r - c_2 = 0\]

This is the characteristic equation.

Step 2: Find the Roots

Solve the quadratic. There are two cases:

Case 1: Two distinct roots \(r_1 \ne r_2\). The general solution is:

\[a_n = A \cdot r_1^n + B \cdot r_2^n\]

Case 2: Repeated root \(r_1 = r_2 = r\). The general solution is:

\[a_n = (A + Bn) \cdot r^n\]

Step 3: Use Initial Conditions

Plug in \(a_0\) and \(a_1\) to find \(A\) and \(B\).

Worked Example

Recurrence: \(a_n = 5a_{n-1} - 6a_{n-2}\), with \(a_0 = 1\), \(a_1 = 4\).

Characteristic equation: \(r^2 - 5r + 6 = 0\), which factors as \((r-2)(r-3) = 0\).

Roots: \(r_1 = 2\), \(r_2 = 3\) (distinct).

General solution: \(a_n = A \cdot 2^n + B \cdot 3^n\).

Apply initial conditions: - \(a_0 = 1\): \(A + B = 1\) - \(a_1 = 4\): \(2A + 3B = 4\)

From the first equation, \(A = 1 - B\). Substitute: \(2(1-B) + 3B = 4 \Rightarrow B = 2\), \(A = -1\).

Closed form: \(a_n = -2^n + 2 \cdot 3^n\).

Verify: \(a_0 = -1 + 2 = 1\) ✓, \(a_1 = -2 + 6 = 4\) ✓, \(a_2 = -4 + 18 = 14\). Check: \(5(4) - 6(1) = 14\) ✓.

Fibonacci: A Famous Recurrence

Applying the characteristic method to Fibonacci (\(F_n = F_{n-1} + F_{n-2}\), \(F_0 = 0\), \(F_1 = 1\)):

Characteristic equation: \(r^2 - r - 1 = 0\).

Roots: \(r = \frac{1 \pm \sqrt{5}}{2}\). Let \(\phi = \frac{1 + \sqrt{5}}{2} \approx 1.618\) (the golden ratio) and \(\hat\phi = \frac{1 - \sqrt{5}}{2} \approx -0.618\).

Closed form (Binet's formula):

\[F_n = \frac{\phi^n - \hat\phi^n}{\sqrt{5}}\]

Since \(|\hat\phi| < 1\), for large \(n\) the second term is negligible, so \(F_n \approx \frac{\phi^n}{\sqrt{5}}\).

This tells us Fibonacci numbers grow exponentially with base \(\phi\).

Generating Functions: A Teaser

A generating function encodes an entire sequence as the coefficients of a power series:

\[G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots\]

For the sequence \(1, 1, 1, \ldots\), the generating function is the geometric series:

\[G(x) = \frac{1}{1 - x}\]

For Fibonacci, the generating function is:

\[G(x) = \frac{x}{1 - x - x^2}\]

Generating functions turn recurrences into algebraic equations, making them a powerful tool for counting problems. You will see them again in the combinatorics chapters of this course.

Practice Problems

Problem 1. Compute \(\displaystyle\sum_{k=1}^{200} \frac{1}{k(k+1)}\).

Solution

\(\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}\). Telescopes to \(1 - \frac{1}{201} = \frac{200}{201}\).

Problem 2. Compute \(\displaystyle\sum_{k=1}^{n} \frac{1}{(2k-1)(2k+1)}\).

Solution

\(\frac{1}{(2k-1)(2k+1)} = \frac{1}{2}\left(\frac{1}{2k-1} - \frac{1}{2k+1}\right)\).

Telescopes to \(\frac{1}{2}\left(1 - \frac{1}{2n+1}\right) = \frac{n}{2n+1}\).

Problem 3. Find the closed form for \(a_n = 4a_{n-1} - 4a_{n-2}\), with \(a_0 = 1\), \(a_1 = 3\).

Solution

Characteristic equation: \(r^2 - 4r + 4 = 0 \Rightarrow (r-2)^2 = 0\). Repeated root \(r = 2\).

General solution: \(a_n = (A + Bn) \cdot 2^n\).

\(a_0 = 1\): \(A = 1\). \(a_1 = 3\): \((1 + B) \cdot 2 = 3 \Rightarrow B = \frac{1}{2}\).

\(a_n = \left(1 + \frac{n}{2}\right) \cdot 2^n = (2 + n) \cdot 2^{n-1}\).

Problem 4. Compute \(F_{10}\) using iteration.

Solution

\(F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, F_7=13, F_8=21, F_9=34, F_{10}=55\).

Problem 5. Compute \(\displaystyle\prod_{k=2}^{20} \frac{k^2 - 1}{k^2}\).

Solution

Using the formula: \(\frac{n+1}{2n} = \frac{21}{40}\).