Olympiad Algebra III: Jensen, Rearrangement, Polynomials & Sequences

Jensen is the master inequality behind AM–GM ($f = -\ln$), power means ($f = x^p$), and most "symmetric sum of a function of the variables" problems. The technique: identify the function being summed, check its second derivative on the relevant interval, apply Jensen at the mean. When $f$ changes convexity (an inflection point), use the tangent line trick — compare $f(x)$ to its tangent at the mean — or smoothing.

Rearrangement is the inequality of "large with large". It proves Nesbitt, $\frac{a}{b + c} + \frac{b}{c + a} + \frac{c}{a + b} \ge \frac32$, in three lines: WLOG $a \ge b \ge c$, so $\frac{1}{b + c} \ge \frac{1}{c + a} \ge \frac{1}{a + b}$ — the two sequences are similarly sorted. By rearrangement the sum $S$ is at least each of the two cyclic pairings: $S \ge \frac{a}{c + a} + \frac{b}{a + b} + \frac{c}{b + c}$ and $S \ge \frac{a}{a + b} + \frac{b}{b + c} + \frac{c}{c + a}$. Adding, $2S \ge \frac{a + c}{c + a} + \frac{a + b}{a + b} + \frac{b + c}{b + c} = 3$. Rearrangement needs no convexity — only ordering — which makes it the tool when the terms are not nice functions.

The divisibility $a - b \mid P(a) - P(b)$ is the workhorse. It shows $P(P(x)) = x$ has few integer solutions and that no nonconstant polynomial takes prime values at every integer. Combine with size: a polynomial of degree $d$ grows like $x^d$, so equations like $P(x) = 2^x$ or $P(n) =$ (a $d$-th power) can be squeezed.

The USAMO sequence problem usually asks to prove all terms are integers, or to find all $n$ with some property. Both reduce to finding the right invariant of the recurrence: for $a_{n+1} = \frac{a_n^2 + c}{a_{n-1}}$, the quantity $\frac{a_{n+1} + a_{n-1}}{a_n}$ is constant, turning a nonlinear recurrence into a linear one and proving integrality at once.

The tangent line trick is Jensen's inequality with the convexity replaced by a single checkable inequality: the tangent at the equality point lies below $f$ on the relevant range, and that is all Jensen ever used. Checking it is a polynomial inequality with a double root at $m$, so after clearing denominators it factors as $(x-m)^2$ times something whose sign you verify. Karamata is summation by parts. Put $c_i=\tfrac{f(x_i)-f(y_i)}{x_i-y_i}$ (or $f'(x_i)$ if they are equal); convexity makes the slopes $c_i$ decrease with $i$. With $X_k,Y_k$ the partial sums, $\sum(f(x_i)-f(y_i))=\sum c_i(x_i-y_i)=\sum_{k<n}(c_k-c_{k+1})(X_k-Y_k)+c_n(X_n-Y_n)$, and every term is $\ge0$. Majorization says "more spread out": for convex $f$, spreading increases the sum.

Step 1 — the inequality is homogeneous, so assume $a+b+c=3$. The first term becomes a function of $a$ alone:

Step 2 — equality should be at $a=b=c=1$, where $f(1)=\tfrac{16}6=\tfrac83$. The tangent line there has slope $f'(1)=\tfrac43$, so it is $\tfrac83+\tfrac43(a-1)=\tfrac{4a+4}3$.

Step 3 — check $f(a)\le\tfrac{4a+4}{3}$: after clearing the positive denominator $3(3a^2-6a+9)$ the difference is

Step 4 — summing the three bounds: $\sum f\le\tfrac{4(a+b+c)+12}{3}=\tfrac{24}{3}=8$, with equality at $a=b=c$.

How to find it. After normalizing, each term depends on one variable, but $f$ is neither convex nor concave on $(0,3)$ — so Jensen fails and the tangent at the equality point is the natural substitute. The double root at $a=1$ is guaranteed, so the cubic factors on sight.

Step 1 — sort $x\ge y\ge z$. Then $\left(\tfrac12,\tfrac12,0\right)$ majorizes $(x,y,z)$: $\tfrac12\ge x$ by hypothesis, $\tfrac12+\tfrac12=1\ge x+y$ since $z\ge0$, and both totals are $1$.

Step 2 — and $(x,y,z)$ majorizes $\left(\tfrac13,\tfrac13,\tfrac13\right)$: $x\ge\tfrac13$ because $x$ is the largest of three numbers summing to $1$, and $x+y\ge\tfrac23$ because $z\le\tfrac13$.

Step 3 — $t\mapsto t^3$ is convex on $[0,\infty)$, so by Karamata

The minimum is $\tfrac19$ at $x=y=z=\tfrac13$ and the maximum $\tfrac14$ at $\left(\tfrac12,\tfrac12,0\right)$ and its permutations.

How to find it. A convex symmetric sum under box constraints and a fixed total is extremal at the most spread-out and the most balanced admissible points; majorization identifies both without calculus. Without the cap $\tfrac12$ the maximum would be at $(1,0,0)$.

The bound $\tfrac1{x^2+1}\ge1-\tfrac x2$ is equivalent to $x(x-1)^2\ge0$, which holds for $x\ge0$ and fails for every $x<0$: there the tangent rises above the curve (see the figure on the tangent line example above). With positive variables the trick works; allow one negative value and the inequality itself is false. The tangent line trick needs the one-variable inequality on the whole range the constraint permits — check the sign of the factor multiplying $(x-m)^2$ on that range.

Write the relation at two consecutive indices, $a_{n+1}a_{n-1}-a_n^2=c=a_na_{n-2}-a_{n-1}^2$, and move terms: $a_{n-1}(a_{n+1}+a_{n-1})=a_n(a_n+a_{n-2})$. Dividing by $a_{n-1}a_n$ gives $\tfrac{a_{n+1}+a_{n-1}}{a_n}=\tfrac{a_n+a_{n-2}}{a_{n-1}}$, so the ratio does not change with $n$ and equals its first value $\tfrac{a_2+a_0}{a_1}$. The division in the original recurrence is what threatens integrality; the linear form has no division at all. The same subtraction trick works for other "product equals polynomial" recurrences, sometimes giving a ratio that is periodic rather than constant.

Step 1 — the terms are $1,2,\tfrac32,\tfrac53,\tfrac85,\dots$, ratios of consecutive Fibonacci numbers. By induction $a_n\ge1$: true for $n=1$, and $a_{n+1}=1+\tfrac1{a_n}>1$.

Step 2 — a limit $L$ would satisfy $L=1+\tfrac1L$, so $L=\varphi=\tfrac{1+\sqrt5}2$ (the positive root).

Step 3 — contraction: using $\varphi=1+\tfrac1\varphi$,

So the distance to $\varphi$ shrinks by a factor at least $\varphi>1$ at each step, and $a_n\to\varphi$.

Step 4 — the terms alternate around $\varphi$, because $x\mapsto1+\tfrac1x$ is decreasing: the cobweb spirals in.

How to find it. For $a_{n+1}=g(a_n)$, find the fixed point, then bound $|g(x)-g(L)|$ by a constant times $|x-L|$ on the region the sequence lives in. The cobweb (up to the curve, across to the diagonal) shows at once whether the iteration converges and whether it overshoots.

Step 1 — first terms: $a_2=4$, $a_3=\tfrac{16+3}1=19$, $a_4=\tfrac{361+3}{4}=91$.

Step 2 — all terms are positive (induction: a positive numerator over a positive denominator), so the lemma applies with $c=3$: $\tfrac{a_{n+1}+a_{n-1}}{a_n}$ is constant, equal to $\tfrac{a_2+a_0}{a_1}=5$.

Step 3 — hence $a_{n+1}=5a_n-a_{n-1}$ for all $n\ge1$, and since $a_0,a_1$ are integers, induction makes every term an integer: $1,1,4,19,91,436,\dots$ (and indeed $\tfrac{91^2+3}{19}=436$).

How to find it. Compute a few terms, notice they are integers against the odds, and look for a linear relation among consecutive terms ($91=5\cdot19-4$). Then prove the relation from the recurrence by the subtraction trick.

Step 1 — first terms: $1,1,1,2,3,7,11,26,41,\dots$, all positive by induction.

Step 2 — the recurrence says $a_{n+1}a_{n-2}-a_na_{n-1}=1$ for $n\ge3$. Subtract the same identity one index earlier, $a_na_{n-3}-a_{n-1}a_{n-2}=1$ (valid for $n\ge4$): $a_{n-2}(a_{n+1}+a_{n-1})=a_n(a_{n-1}+a_{n-3})$.

Step 3 — so $r_n=\tfrac{a_{n+1}+a_{n-1}}{a_n}$ satisfies $r_n=r_{n-2}$: it is periodic with period $2$, not constant. Its starting values are $r_2=\tfrac{a_3+a_1}{a_2}=2$ and $r_3=\tfrac{a_4+a_2}{a_3}=3$.

Step 4 — hence $a_{n+1}=2a_n-a_{n-1}$ for even $n$ and $a_{n+1}=3a_n-a_{n-1}$ for odd $n$, both with integer coefficients, and induction gives integrality. Check: $a_8=3\cdot11-7=26$ and $a_9=2\cdot26-11=41$.

How to find it. The same subtraction trick as for $a_{n+1}a_{n-1}=a_n^2+c$, but here the identity links indices two apart, so the invariant alternates. Computing $r_n$ for the first few $n$ shows the period before you prove it.

$x_{43}$ is not an integer. No amount of computed evidence proves integrality; forty-two confirmations are as consistent with failure at step forty-three as with success forever. The recurrences in this section are proved integral by an identity that removes the division; Göbel's sequence has no such identity, and its denominators $n$ eventually fail to divide. Treat a computed pattern as a conjecture to prove, and look for the linear relation that would prove it.