Hard Sequences: Closed Forms, Rates & Periodicity

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 $b_{n+1} - b_n \to L$ then $b_n/n \to L$. The Putnam then asks for $\lfloor a_{100}\rfloor$ or $\lim n a_n$ — questions that are hopeless by direct iteration and one line after the trick.

Because $(\alpha^k + \alpha^{-k})^2 - 2 = \alpha^{2k} + \alpha^{-2k}$, the map $x \mapsto x^2 - 2$ is the doubling map in disguise (compare $2\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 $\prod(1 + 1/a_k)$ or $a_n \bmod m$: a closed form makes them telescope or cycle. The trigonometric twin, $a_{n+1} = \sqrt{2 + a_n}$ with $a_0 = 0$, has closed form $2\cos\frac{\pi}{2^{n+1}}$ and limit $2$.

Möbius maps $x \mapsto \tfrac{ax+b}{cx+d}$ compose like the matrices $\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 $\tfrac{1+x}{1-x}$ (the matrix of a $45^\circ$ rotation) has order $4$. When a Putnam problem asks for $x_{2024}$, compute a few terms, spot the period, and PROVE it by composing the map with itself.

Fix $\varepsilon > 0$ and $N$ with $L - \varepsilon < \tfrac{a_{k+1} - a_k}{b_{k+1} - b_k} < L + \varepsilon$ for $k \ge N$. Multiply by the positive $b_{k+1} - b_k$ and sum from $N$ to $n - 1$: $(L - \varepsilon)(b_n - b_N) < a_n - a_N < (L + \varepsilon)(b_n - b_N)$. Divide by $b_n$ and let $n \to \infty$: since $b_N/b_n \to 0$ and $a_N/b_n \to 0$, every limit point of $a_n/b_n$ lies in $[L - \varepsilon, L + \varepsilon]$. $\blacksquare$ Significance: it turns "the increments tend to $L$" into "the average tends to $L$" — Cesàro means, the rate of $a_{n+1} = a_n - a_n^2$, and every $\lim \tfrac{1}{n^{p+1}}\sum k^p$ are one application each.

Step 1 — square: $a_{n+1}^2 = a_n^2 + 2 + a_n^{-2}$, so $a_{100}^2 = 199 + \sum_{k=1}^{99}a_k^{-2}$.

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

Step 3 — upper bound: from Step 1, $a_k^2 \ge 2k - 1$, so the correction is at most $1 + \sum_{k=2}^{99}\tfrac{1}{2k-1} < 1 + \tfrac12\ln 197 + \tfrac12 < 5$.

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

Step 1 — convergence: $0 < \sin x < x$ for $0 < x \le 1$, so by induction $0 < a_{n+1} < a_n$; a decreasing sequence bounded below has a limit $L \in [0, 1)$, and continuity gives $\sin L = L$, whose only solution in $[0, 1)$ is $L = 0$.

Step 2 — the rate: the recurrence subtracts roughly a cube ($\sin x \approx x - \tfrac{x^3}{6}$), so take reciprocal SQUARES. From $\sin x = x - \tfrac{x^3}{6} + O(x^5)$, $\dfrac{1}{\sin^2x} = \dfrac{1}{x^2}\left(1 - \tfrac{x^2}{6} + O(x^4)\right)^{-2} = \dfrac{1}{x^2} + \dfrac13 + O(x^2)$.

Step 3 — so $\dfrac{1}{a_{n+1}^2} - \dfrac{1}{a_n^2} \to \dfrac13$, and Stolz–Cesàro with $b_n = n$ gives $\dfrac{1}{na_n^2} \to \dfrac13$, i.e. $na_n^2 \to 3$.

Step 4 — $\sqrt n\,a_n \to \sqrt3$. (Numerically $na_n^2 \approx 2.88$ at $n = 100$ and $2.98$ at $n = 1000$: the convergence is slow, with a $\tfrac{\ln n}{n}$ correction.)

How to find it. A recurrence $a_{n+1} = a_n - ca_n^{k+1} + \cdots$ is tamed by the power $a^{-k}$: it turns the increment into a constant, $a_{n+1}^{-k} - a_n^{-k} \to kc$. For $a_n - a_n^2$ that was reciprocals ($k = 1$); for the sine, $c = \tfrac16$ and $k = 2$ give reciprocal squares and the constant $\tfrac13$.