9. Linear Recurrences

If a sequence is defined by $x_n = A x_{n-1} + B x_{n-2}$, assume a geometric solution $x_n = r^n$. Substituting yields the Characteristic Equation:

If this quadratic has distinct roots $r_1, r_2$, the formula is $x_n = C_1(r_1)^n + C_2(r_2)^n$.

• Repeated Roots: If $(r-1)^2 = 0$, the roots repeat, and the solution takes the form $a_n = C_1 + C_2n$.
• Complex Roots: Equations like $r^2 - 2r + 2 = 0$ yield $1 \pm i$. This indicates the sequence will oscillate.

10. AMC Tricks

When you see these expressions on a contest, bypass standard algebra and use these direct rewrites:

Expression	Rewrite	Technique
$\frac{k}{k+1}$	$1 - \frac{1}{k+1}$	Telescoping
$\frac{k+1}{k}$	$1 + \frac{1}{k}$	Telescoping
$\frac{1}{\sqrt{k+1} + \sqrt{k}}$	$\sqrt{k+1} - \sqrt{k}$	Rationalize Conjugate
$\frac{1}{k(k+1)}$	$\frac{1}{k} - \frac{1}{k+1}$	Partial Fractions
$\frac{1}{k^2-1}$	$\frac{1}{2}(\frac{1}{k-1} - \frac{1}{k+1})$	Non-Adjacent Partial Fractions
$a_{n+1} = pa_n + q$	$b_{n+1} = p b_n$	Shift by fixed point
$a_{n+1} = f(a_n)$	$L = f(L)$	Find fixed point limit

Worked Examples

Example 1: Finite Differences

Problem: Find the $n$th term formula for the sequence $2, 7, 16, 29, 46, \dots$

Solution: Take the first differences between consecutive terms: $5, 9, 13, 17 \dots$ Take the second differences: $4, 4, 4 \dots$ Because the second difference is a constant $4$, the sequence is governed by a quadratic formula $a_n = An^2 + Bn + C$. Using the first three terms ($n=1, 2, 3$):

1. $A + B + C = 2$
2. $4A + 2B + C = 7$
3. $9A + 3B + C = 16$

Subtracting (1) from (2) gives $3A + B = 5$. Subtracting (2) from (3) gives $5A + B = 9$. Subtracting those results yields $2A = 4 \implies A = 2$. Substituting back: $3(2) + B = 5 \implies B = -1$. Finally: $2 - 1 + C = 2 \implies C = 1$. Formula: $a_n = 2n^2 - n + 1$.

Example 2: Polynomial Summation

Problem: Evaluate the sum $\sum_{k=1}^{40} k(k+2)$.

Solution: Expand the expression inside the sum: $\sum_{k=1}^{40} (k^2 + 2k)$. Use the linearity of summation: $\sum_{k=1}^{40} k^2 + 2\sum_{k=1}^{40} k$. Apply the known power sum formulas with $n=40$:

Example 3: Hidden Multiple Geometric Series

Problem: Evaluate $\sum_{k=1}^{\infty} \frac{2^k + 3^k}{5^k}$.

Solution: Split the fraction into two separate infinite geometric series:

For the first series: $a = \frac{2}{5}, r = \frac{2}{5} \implies S_1 = \frac{2/5}{1 - 2/5} = \frac{2}{3}$. For the second series: $a = \frac{3}{5}, r = \frac{3}{5} \implies S_2 = \frac{3/5}{1 - 3/5} = \frac{3}{2}$. Total sum: $\frac{2}{3} + \frac{3}{2} = \frac{13}{6}$.

Example 4: Non-Adjacent Partial Fractions

Problem: Evaluate $\sum_{k=1}^{99} \frac{1}{k^2 + 2k}$.

Solution: Set up partial fractions: $\frac{1}{k(k+2)} = \frac{1}{2} \left(\frac{1}{k} - \frac{1}{k+2}\right)$. Because the gap between denominators is $2$, two positive terms survive at the start and two negative terms survive at the end.

Example 5: The Recursive Fixed Point Limit

Problem: A sequence is defined by $a_1 = 3$ and $a_{n+1} = \frac{5a_n - 4}{a_n + 1}$. Assuming the sequence converges, find its limit.

Solution: At infinity, both $a_n$ and $a_{n+1}$ become indistinguishable from the limit $L$.

Example 6: The Arithmetico-Geometric Series (AGS)

Problem: Evaluate the infinite sum $S = \sum_{n=1}^\infty \frac{n}{2^n}$.

Solution: Write out the first few terms to see the structure:

Multiply the entire sum by the common geometric ratio $r = 1/2$:

Subtract the shifted sum from the original sum. Notice how aligning the denominators causes the arithmetic numerator to drop to a constant $1$:

The right side is now a pure geometric series summing to $1$.

Example 7: Radical Telescoping

Problem: Evaluate $\sum_{n=1}^{99} \frac{1}{\sqrt{n} + \sqrt{n+1}}$.

Solution: Rationalize the denominator by multiplying by the conjugate $\sqrt{n+1} - \sqrt{n}$:

Now write out the telescoped sum:

The middle collapses entirely, leaving only $\sqrt{100} - \sqrt{1} = 10 - 1 = 9$.

Example 8: Solving a Linear Recurrence

Problem: A sequence is defined by $a_0 = 0, a_1 = 1$, and $a_n = 5a_{n-1} - 6a_{n-2}$. Find an explicit formula for $a_n$.

Solution: Set up the characteristic equation:

Factoring yields $(r-2)(r-3) = 0$, so the roots are $r_1 = 2$ and $r_2 = 3$. General solution: $a_n = C_1(2)^n + C_2(3)^n$. Using initial conditions: $n=0 \implies 0 = C_1 + C_2 \implies C_1 = -C_2$ $n=1 \implies 1 = 2C_1 + 3C_2 \implies 1 = -2C_2 + 3C_2 \implies C_2 = 1, C_1 = -1$. Explicit formula: $a_n = 3^n - 2^n$.

Example 10: Where the Telescoping Method is NOT Obvious

Problem: Evaluate $\sum_{k=1}^{100} \frac{2k+1}{k^2(k+1)^2}$.

Solution: Unlike standard partial fractions, this numerator looks troublesome. However, look for the derivative or a difference of squares in the numerator. Notice that $(k+1)^2 - k^2 = (k^2+2k+1) - k^2 = 2k+1$. Rewrite the fraction:

The fraction telescopes perfectly!

The sum completely collapses to $1 - \frac{1}{101^2}$.

Example 11: Summation by Pairing

Problem: Evaluate $\sum_{k=1}^{100} k(101-k)$.

Solution: While you could expand this into $101\sum k - \sum k^2$ and use power formulas, you can also recognize pairing symmetry. Let the sum be $S = 1(100) + 2(99) + 3(98) + \dots + 99(2) + 100(1)$. Notice that term 1 equals term 100, term 2 equals term 99, etc. This symmetric behavior implies you only need to evaluate the first 50 terms and double it:

This reduces the computational load and minimizes arithmetic errors during contests.

Example 12: Sequence as a Polynomial Difference

Problem: If $a_n = n^3$, find the degree of the sequence $b_n = a_{n+1} - a_n$.

Solution: Evaluate the difference explicitly:

The sequence $b_n$ is a quadratic polynomial. Taking the difference of any polynomial sequence lowers its degree by exactly 1.

Example 13: The Synthesis

Problem: Evaluate $\sum_{k=1}^{100} \frac{k}{(k+1)!}$.

Solution: Generate a telescoping form by rewriting the numerator:

Simplify the left fraction by cancelling $(k+1)$:

We have successfully engineered a perfect telescoping series! Now write out the sum:

Every intermediate term cancels, leaving $1 - \frac{1}{101!}$.

Practice Problems