Telescoping & Recursion

Why it works. If every term has the form $u_k - u_{k+1}$, then in the sum each intermediate $u_k$ appears once with a plus sign (from term $k$) and once with a minus sign (from term $k - 1$), so only the first and last survive. Partial fractions is the tool that FINDS the form $u_k - u_{k+1}$ when a term is a rational function.

Why it works. A recursion says the count for size $n$ is built from counts for smaller sizes, so computing upward from the base cases is an exact method, not an approximation. On the AIME, where $n$ is usually below $20$, a table of values is often faster and safer than a closed form.

Spotting it. Condition on the last stride: it covered $1$, $2$ or $3$ steps, leaving a staircase of $n - 1$, $n - 2$ or $n - 3$.

Step 1. $c_n = c_{n-1} + c_{n-2} + c_{n-3}$ with $c_0 = 1$, $c_1 = 1$, $c_2 = 2$.

Step 2. $c_3, \dots, c_{10} = 4, 7, 13, 24, 44, 81, 149, 274$. The answer is $274$.

With a gap of $2$, two terms survive at each end instead of one: $\sum_{k=1}^{n}\dfrac{1}{k(k+2)} = \tfrac12\left(1 + \tfrac12 - \tfrac1{n+1} - \tfrac1{n+2}\right)$. Counting the survivors correctly is where the points are; writing out the first three and last three terms explicitly makes it visible.

Factorial-heavy products usually hide such a ratio: $\prod\left(1 - \tfrac1{k^2}\right) = \prod\dfrac{(k-1)(k+1)}{k^2}$ splits into two telescoping products and leaves $\dfrac{n+1}{2n}$. Writing each factor as (something at $k+1$)/(something at $k$) is the deciding step.

Step 1 — $\dfrac{1}{k(k+2)} = \tfrac12\left(\dfrac1k - \dfrac1{k+2}\right)$.

Step 2 — the surviving terms are $\tfrac12\left(1 + \tfrac12 - \tfrac1{99} - \tfrac1{100}\right)$.

Step 3 — $= \tfrac12\left(\tfrac32 - \tfrac{199}{9900}\right) = \tfrac{14651}{19800}$.

Spotting it. Factor: $k^3 - 1 = (k - 1)(k^2 + k + 1)$ and $k^3 + 1 = (k + 1)(k^2 - k + 1)$. The key observation is $k^2 + k + 1 = (k + 1)^2 - (k + 1) + 1$: the quadratic factor on top at $k$ is the one on the bottom at $k + 1$.

Step 1. The product splits as $\displaystyle\prod_{k=2}^{10}\frac{k - 1}{k + 1} \cdot \prod_{k=2}^{10}\frac{k^2 + k + 1}{k^2 - k + 1}$.

Step 2. The first is $\dfrac{1 \cdot 2}{10 \cdot 11} = \dfrac{1}{55}$ (a gap-two telescope: $1, 2$ survive on top, $10, 11$ below). The second telescopes to $\dfrac{10^2 + 10 + 1}{2^2 - 2 + 1} = \dfrac{111}{3} = 37$.

Step 3. The product is $\dfrac{37}{55}$, so $m + n = 92$.

Why it works. If every term is $F(k + 1) - F(k)$, the sum from $k = 1$ to $n$ is $F(n + 1) - F(1)$, because each intermediate $F$ appears once with each sign. The skill is guessing $F$ from the shape of the term: factorials suggest factorials, square roots suggest conjugates, a product of consecutive factors suggests a product with one factor fewer. Always test the guess at $k = 1$.

Spotting it. $k \cdot k! = (k + 1 - 1)k! = (k + 1)! - k!$.

Step 1. The sum telescopes to $21! - 1! = 21! - 1$.

Step 2. $21!$ is divisible by $1000$ (it contains $2^3$ and $5^3$), so $21! - 1 \equiv -1 \equiv 999 \pmod{1000}$.

Spotting it. A product of three consecutive factors: compare it with products of two. $\tfrac{1}{k(k + 1)} - \tfrac{1}{(k + 1)(k + 2)} = \tfrac{(k + 2) - k}{k(k + 1)(k + 2)} = \tfrac{2}{k(k + 1)(k + 2)}$.

Step 1. So the sum is $\tfrac12\left[\tfrac{1}{1 \cdot 2} - \tfrac{1}{9 \cdot 10}\right] = \tfrac12 \cdot \tfrac{45 - 1}{90} = \tfrac{22}{90} = \tfrac{11}{45}$.

Step 2. $m + n = 56$.

Spotting it. Factor $\sqrt k\sqrt{k + 1}$ out of the denominator: $(k + 1)\sqrt k + k\sqrt{k + 1} = \sqrt k\sqrt{k + 1}\left(\sqrt{k + 1} + \sqrt k\right)$. Then rationalise.

Step 1. $\dfrac{1}{\sqrt k\sqrt{k + 1}(\sqrt{k + 1} + \sqrt k)} = \dfrac{\sqrt{k + 1} - \sqrt k}{\sqrt k\sqrt{k + 1}} = \dfrac{1}{\sqrt k} - \dfrac{1}{\sqrt{k + 1}}$.

Step 2. The sum telescopes to $1 - \dfrac{1}{\sqrt{144}} = \dfrac{11}{12}$, so $m + n = 23$.