Hard Sequences: Closed Forms, Rates & Periodicity

Study Sheet

Hard Sequences: Closed Forms, Rates & Periodicity

Squaring tricks, reciprocal tricks, Lucas closed forms, Stolz rates, and maps of finite order

Sequences the Putnam Actually Sets

Tip
The squaring and reciprocal tricks

For an+1=an+1ana_{n+1} = a_n + \tfrac{1}{a_n}, square: an+12=an2+2+an−2a_{n+1}^2 = a_n^2 + 2 + a_n^{-2}, so an2≈2na_n^2 \approx 2n. For an+1=an−an2a_{n+1} = a_n - a_n^2, take reciprocals: 1an+1−1an=11−an→1\tfrac{1}{a_{n+1}} - \tfrac{1}{a_n} = \tfrac{1}{1 - a_n} \to 1, so nan→1na_n \to 1.

Recurrences that are not linear usually become tame after a transformation chosen to make the increments simple: square when the recurrence adds a reciprocal, take reciprocals when it subtracts a square, take logarithms when it multiplies. After the transformation, Stolz–Cesàro (the discrete L'Hôpital) reads off the growth rate: if bn+1−bn→Lb_{n+1} - b_n \to L then bn/n→Lb_n/n \to L. The Putnam then asks for ⌊a100⌋\lfloor a_{100}\rfloor or lim⁡nan\lim n a_n — questions that are hopeless by direct iteration and one line after the trick.

Tip
Closed forms from α+α−1\alpha + \alpha^{-1}

If a0=α+α−1a_0 = \alpha + \alpha^{-1} and an+1=an2−2a_{n+1} = a_n^2 - 2, then an=α2n+α−2na_n = \alpha^{2^n} + \alpha^{-2^n}. With a0=3a_0 = 3 this is a Lucas number, L2n+1L_{2^{n+1}}: 3,7,47,2207,…3, 7, 47, 2207, \ldots

Because (αk+α−k)2−2=α2k+α−2k(\alpha^k + \alpha^{-k})^2 - 2 = \alpha^{2k} + \alpha^{-2k}, the map x↦x2−2x \mapsto x^2 - 2 is the doubling map in disguise (compare 2cos⁡2θ=(2cos⁡θ)2−22\cos 2\theta = (2\cos\theta)^2 - 2). This is the engine behind the Lucas–Lehmer primality test and behind Putnam problems that ask about ∏(1+1/ak)\prod(1 + 1/a_k) or an mod ma_n \bmod m: a closed form makes them telescope or cycle. The trigonometric twin, an+1=2+ana_{n+1} = \sqrt{2 + a_n}, has closed form 2cos⁡π2n+12\cos\frac{\pi}{2^{n+1}} and limit 22.

Tip
Maps of finite order and periodic sequences

x↦11−xx \mapsto \tfrac{1}{1-x} has order 33; x↦1+x1−xx \mapsto \tfrac{1+x}{1-x} has order 44; x↦x+1x−1x \mapsto \tfrac{x+1}{x-1} is an involution. A recurrence xn+1=g(xn)x_{n+1} = g(x_n) with gg of order kk is periodic with period dividing kk.

Möbius maps x↦ax+bcx+dx \mapsto \tfrac{ax+b}{cx+d} compose like the matrices (abcd)\begin{pmatrix}a&b\\c&d\end{pmatrix}, so the order of the map is the order of the matrix up to scalars — which is why 1+x1−x\tfrac{1+x}{1-x} (the matrix of a 45∘45^\circ rotation) has order 44. When a Putnam problem asks for x2024x_{2024}, compute a few terms, spot the period, and PROVE it by composing the map with itself.

Side note
Generating functions for linear recurrences

A linear recurrence an+2=pan+1+qana_{n+2} = pa_{n+1} + qa_n has generating function (polynomial)1−px−qx2\tfrac{\text{(polynomial)}}{1 - px - qx^2}; evaluating at a point inside the radius of convergence sums series like ∑Fn/2n=2\sum F_n/2^n = 2 instantly. The radius is 1/∣largest root∣1/|\text{largest root}| — for Fibonacci, 1/φ≈0.6181/\varphi \approx 0.618, so x=12x = \tfrac12 is safely inside.

Try it
Try it: a rate by Stolz

If a1=1a_1 = 1 and an+1=an+1an2a_{n+1} = a_n + \tfrac{1}{a_n^2}, find lim⁡an3/n\lim a_n^3/n.

Cube: an+13=an3+3+3an−3+an−6a_{n+1}^3 = a_n^3 + 3 + 3a_n^{-3} + a_n^{-6}, so an+13−an3→3a_{n+1}^3 - a_n^3 \to 3 and by Stolz an3/n→3a_n^3/n \to 3.

Proofs & Why It Matters

Tip
Proof: Stolz–Cesàro

If bnb_n is strictly increasing with bn→∞b_n \to \infty and an+1−anbn+1−bn→L\tfrac{a_{n+1} - a_n}{b_{n+1} - b_n} \to L, then anbn→L\tfrac{a_n}{b_n} \to L.

Fix ε>0\varepsilon > 0 and NN with L−ε<ak+1−akbk+1−bk<L+εL - \varepsilon < \tfrac{a_{k+1} - a_k}{b_{k+1} - b_k} < L + \varepsilon for k≥Nk \ge N. Multiply by the positive bk+1−bkb_{k+1} - b_k and sum from NN to n−1n - 1: (L−ε)(bn−bN)<an−aN<(L+ε)(bn−bN)(L - \varepsilon)(b_n - b_N) < a_n - a_N < (L + \varepsilon)(b_n - b_N). Divide by bnb_n and let n→∞n \to \infty: since bN/bn→0b_N/b_n \to 0 and aN/bn→0a_N/b_n \to 0, every limit point of an/bna_n/b_n lies in [L−ε,L+ε][L - \varepsilon, L + \varepsilon]. ■\blacksquare Significance: it turns "the increments tend to LL" into "the average tends to LL" — Cesàro means, the rate of an+1=an−an2a_{n+1} = a_n - a_n^2, and every lim⁡1np+1∑kp\lim \tfrac{1}{n^{p+1}}\sum k^p are one application each.

Going Deeper: Worked Problems

Example
Worked: ⌊a100⌋\lfloor a_{100}\rfloor for an+1=an+1/ana_{n+1} = a_n + 1/a_n

With a1=1a_1 = 1, find ⌊a100⌋\lfloor a_{100}\rfloor.

Step 1 — square: an+12=an2+2+an−2a_{n+1}^2 = a_n^2 + 2 + a_n^{-2}, so a1002=199+∑k=199ak−2a_{100}^2 = 199 + \sum_{k=1}^{99}a_k^{-2}.

Step 2 — lower bound a1002>199a_{100}^2 > 199.

Step 3 — upper bound: from Step 1, ak2≥2k−1a_k^2 \ge 2k - 1, so the correction is at most 1+∑k=29912k−1<1+12ln⁡197+12<51 + \sum_{k=2}^{99}\tfrac{1}{2k-1} < 1 + \tfrac12\ln 197 + \tfrac12 < 5.

Step 4 — 199<a1002<204199 < a_{100}^2 < 204, so 14.1<a100<14.314.1 < a_{100} < 14.3 and the floor is 1414. Every step is an inequality you can state precisely — that is what makes it a Putnam answer rather than a calculator answer.