Proof Techniques for the Putnam

The Putnam grades exposition. A correct idea written as "clearly the maximum is at $x = 1$" earns $1$ or $2$ out of $10$; the same idea with the derivative computed, the sign checked on each side, and the endpoints compared earns $10$. Write the hypothesis of every theorem you use, in the sentence where you use it. The graders are looking for exactly that sentence.

Minimal-counterexample proofs are induction in a different costume, and they are the natural form when the "smaller case" is not $n - 1$ but something you construct — a polynomial of lower degree, a subset with fewer elements, a fraction with a smaller denominator. State explicitly which well-ordered quantity you are minimizing.

A frequent Putnam pattern: prove a recurrence-defined sequence has a closed form (strong induction on $n$), or that a polynomial identity holds for all degrees (induction on degree, using the case of one lower degree after differentiating or dividing by $x - r$). Write the inductive hypothesis with an explicit letter — "assume the statement for all $k \le n$" — and point to the exact place it is used.

The inductive step can only use what the hypothesis hands it. A bound like "$S_n < 2$" gives no room: adding the next term to something just under $2$ may push it over, and the hypothesis cannot rule that out. A bound like "$S_n \le 2 - g(n)$" carries a margin, and the step goes through exactly when the next term is at most $g(n) - g(n+1)$. So the recipe is to choose $g$ by telescoping: make $g(n) - g(n+1)$ at least the increment. Proving more is often the only way to prove anything, which is why this is called the inductive loading, or strengthening, principle.

Step 1 — the direct attempt fails. From $S_n < 2$ we only get $S_{n+1} < 2 + \tfrac{1}{(n+1)^2}$, which is useless.

Step 2 — strengthen to $S_n \le 2 - \tfrac1n$. Base case: $S_1 = 1 = 2 - \tfrac11$.

Step 3 — the step: $S_{n+1} \le 2 - \tfrac1n + \tfrac{1}{(n+1)^2}$, and we need this to be at most $2 - \tfrac{1}{n+1}$, i.e. $\tfrac{1}{(n+1)^2} \le \tfrac1n - \tfrac{1}{n+1} = \tfrac{1}{n(n+1)}$. That holds because $n(n+1) < (n+1)^2$.

Step 4 — so $S_n \le 2 - \tfrac1n < 2$ for every $n$. (The true limit is $\tfrac{\pi^2}{6} \approx 1.645$; the proof never needed it.)

How to find it. The target is a constant, and the increments $\tfrac{1}{(n+1)^2}$ are each smaller than the telescoping differences $\tfrac1n - \tfrac1{n+1}$ — so subtract the telescoping tail $\tfrac1n$ from the constant.

Step 1 — strong induction on $n$: assume every $m < n$ has such a representation. Base: $1 = 2^03^0$.

Step 2 — if $n$ is even, $n = 2m$ with $m < n$. Doubling every summand of $m$'s representation gives one for $n$, and doubling preserves the no-divisibility condition ($a \mid b \iff 2a \mid 2b$).

Step 3 — if $n$ is odd, let $3^s$ be the largest power of $3$ with $3^s \le n$. If $n = 3^s$ we are done. Otherwise $n - 3^s$ is even (odd minus odd) and positive, and $n < 3^{s+1}$ gives $n - 3^s < 2\cdot3^s$. So $m = \tfrac{n - 3^s}{2}$ satisfies $1 \le m < 3^s$.

Step 4 — represent $m$ by the hypothesis. Every summand $2^{r_i}3^{s_i}$ of $m$ is at most $m < 3^s$, so $s_i < s$. Then $n = 3^s + \sum 2^{r_i + 1}3^{s_i}$.

Step 5 — check the condition. The doubled summands do not divide each other (Step 2). $3^s$ does not divide $2^{r_i+1}3^{s_i}$ because $s_i < s$, and $2^{r_i+1}3^{s_i}$ does not divide $3^s$ because it is even. $\blacksquare$ For example $23 = 9 + 2\cdot7 = 9 + 2(4 + 3) = 9 + 8 + 6$.

How to find it. Small cases ($5 = 2 + 3$, $7 = 4 + 3$, $11 = 9 + 2$) show that an odd $n$ needs exactly one odd summand, a pure power of $3$; taking the largest one makes the rest small enough that its powers of $3$ are forced below $s$. The even case is free by doubling. The strengthening here is to strong induction: the step reaches back to $\tfrac n2$ or $\tfrac{n - 3^s}{2}$, not to $n - 1$.

Step 1 — why the weaker bound cannot be proved directly. With $p_n$ the product, assuming $p_n < \tfrac{1}{\sqrt{3n}}$ gives $p_{n+1} < \tfrac{1}{\sqrt{3n}}\cdot\tfrac{2n+1}{2n+2}$, and this is at most $\tfrac{1}{\sqrt{3n+3}}$ only if $(2n+1)^2(3n+3) \le 3n(2n+2)^2$. Expanding, the left side is $12n^3 + 24n^2 + 15n + 3$ and the right side is $12n^3 + 24n^2 + 12n$: the step fails for every $n$.

Step 2 — the stronger claim. Base: $p_1 = \tfrac12 = \tfrac{1}{\sqrt4}$. Step: from $p_n \le \tfrac{1}{\sqrt{3n+1}}$ we need $\tfrac{1}{\sqrt{3n+1}}\cdot\tfrac{2n+1}{2n+2} \le \tfrac{1}{\sqrt{3n+4}}$, i.e. $(2n+1)^2(3n+4) \le (2n+2)^2(3n+1)$.

Step 3 — expand: $12n^3 + 28n^2 + 19n + 4 \le 12n^3 + 28n^2 + 20n + 4$, which is $0 \le n$. True.

Step 4 — so $p_n \le \tfrac{1}{\sqrt{3n+1}} < \tfrac{1}{\sqrt{3n}}$. $\blacksquare$ The strengthened statement is sharper AND easier: the extra $+1$ is exactly the slack the step consumes.

How to find it. Try $p_n \le \tfrac{1}{\sqrt{3n + c}}$ with $c$ unknown. The step needs $(2n+1)^2(3n + 3 + c) \le (2n+2)^2(3n + c)$; expanding, the $n^3$ and $n^2$ terms cancel and the difference of the two sides is $(4c - 3)n + 3(c - 1)$. This is $\ge 0$ for every $n \ge 1$ exactly when $c \ge \tfrac67$, while the base case $\tfrac12 \le \tfrac{1}{\sqrt{3 + c}}$ needs $c \le 1$. The strongest admissible bound is $c = 1$; the naive $c = 0$ gives the difference $-3n - 3$, the failure of Step 1.

Trapping arguments prove existence without saying where the object is. The IVT is the completeness of the real line in disguise: the supremum of the points where $g \le 0$ is a zero of $g$, because continuity forbids $g$ from being strictly positive or strictly negative there. Pigeonhole and averaging are counting: if every box held at most one object there would be at most $n$ objects; if every term were below the average their sum would be below the total. The Putnam accepts a trapped object as fully as a constructed one, provided the hypotheses (continuity on a closed interval, the number of boxes) are stated.

Step 1 — the midpoint of $(a, b)$ and $(c, d)$ is $\left(\tfrac{a+c}{2}, \tfrac{b+d}{2}\right)$, a lattice point exactly when $a \equiv c$ and $b \equiv d \pmod 2$.

Step 2 — so the boxes are the four parity classes $(\text{even}, \text{even})$, $(\text{even}, \text{odd})$, $(\text{odd}, \text{even})$, $(\text{odd}, \text{odd})$.

Step 3 — five points in four boxes: two share a class, and their midpoint is a lattice point.

Step 4 — four points are not enough: $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ occupy all four classes once, and no midpoint of two of them is a lattice point.

How to find it. "Some two of them" with a condition that depends only on residues is the signature of pigeonhole; the boxes are the residue classes, and the sharpness example is one point per box.

Step 1 — set $g(x) = f\!\left(x + \tfrac1n\right) - f(x)$, continuous on $\left[0, 1 - \tfrac1n\right]$. We need a zero of $g$.

Step 2 — evaluate at the $n$ points $0, \tfrac1n, \ldots, \tfrac{n-1}{n}$ and add: the sum telescopes, $\sum_{k=0}^{n-1}g\!\left(\tfrac kn\right) = f(1) - f(0) = 0$.

Step 3 — a sum of $n$ numbers equal to $0$ contains a term $\ge 0$ and a term $\le 0$ (averaging).

Step 4 — if either is $0$ we are done; otherwise $g$ takes both signs on the interval between those two points, and the intermediate value theorem gives a zero there. $\blacksquare$

How to find it. The condition $f(0) = f(1)$ is a statement about a difference over the whole interval; splitting that difference into $n$ equal steps is what makes a telescoping sum, and a sum of zero is exactly the input the IVT needs.

Step 1 — for any $a$ with $\tfrac1a$ not an integer, try $f(x) = \sin^2\!\frac{\pi x}{a} - x\sin^2\!\frac{\pi}{a}$. It is continuous, $f(0) = 0$, and $f(1) = \sin^2\!\frac{\pi}{a} - \sin^2\!\frac\pi a = 0$.

Step 2 — the first term has period $a$ (since $\sin^2$ has period $\pi$), so $f(x + a) - f(x) = -a\sin^2\!\frac{\pi}{a}$ for every $x$.

Step 3 — this constant is nonzero because $\tfrac\pi a$ is not a multiple of $\pi$. For $a = \tfrac25$: $f(x) = \sin^2\!\frac{5\pi x}{2} - x$ and $f(x + \tfrac25) - f(x) = -\tfrac25$. No horizontal chord of length $\tfrac25$ exists. $\blacksquare$ Together with the previous example: the guaranteed chord lengths are exactly $1, \tfrac12, \tfrac13, \ldots$

How to find it. If the trapping argument fails, ask what a counterexample must look like: $f(x + a) - f(x)$ never zero means (by the IVT) always of one sign, say always $-c$. A periodic function of period $a$ minus a linear function does exactly that, and the linear term's slope is chosen to restore $f(1) = f(0)$.

It works because every nonempty set of nonnegative integers has a least element, so "there is a counterexample" implies "there is a least one", and exhibiting a smaller one is impossible. The construction step is where the mathematics lives: dividing out a common factor, peeling off a root of a polynomial, removing one element. State the measure explicitly; the argument is only as valid as the claim that the new object is smaller in THAT measure.

Step 1 — suppose solutions exist and take one with $z$ as small as possible.

Step 2 — squares are $0$ or $1 \pmod 3$, so $x^2 + y^2 \equiv 0 \pmod 3$ forces $x^2 \equiv y^2 \equiv 0$, i.e. $3 \mid x$ and $3 \mid y$.

Step 3 — then $9 \mid x^2 + y^2 = 3z^2$, so $3 \mid z^2$ and $3 \mid z$.

Step 4 — $(x/3, y/3, z/3)$ is a solution in positive integers with a smaller $z$: contradiction. $\blacksquare$

How to find it. A homogeneous equation (every term of degree $2$) is unchanged by scaling, so any solution divided by a common factor is again a solution — which is what descent needs. The modulus is chosen so that the right side is $0$ and the left side can only be $0$ in the trivial way.

Step 1 — take a counterexample $P$ of least degree. It is not constant, since $c \ge 0$ equals $(\sqrt c)^2 + 0^2$.

Step 2 — a two-squares identity: $(a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2$ (expand both sides). So a product of sums of two squares is again one.

Step 3 — if $P$ has a real root $r$, its multiplicity is even: if $P = (x - r)^mS$ with $S(r) \ne 0$ and $m$ odd, then $P$ changes sign at $r$, contradicting $P \ge 0$. So $P = (x - r)^2Q$ with $Q = P/(x - r)^2 \ge 0$ (off $r$ directly, at $r$ by continuity) and $\deg Q < \deg P$. By minimality $Q = A^2 + B^2$, hence $P = \left((x - r)A\right)^2 + \left((x - r)B\right)^2$: contradiction.

Step 4 — if $P$ has no real root, it has a non-real root $a + bi$ ($b \ne 0$), and its conjugate, so $P = \left((x - a)^2 + b^2\right)Q$. The first factor is positive, so $Q \ge 0$, and $\deg Q < \deg P$ gives $Q = A^2 + B^2$. Step 2 now writes $P = \left((x - a)A - bB\right)^2 + \left((x - a)B + bA\right)^2$: contradiction. $\blacksquare$ Example: $x^4 + 1 = (x^2 - 1)^2 + (\sqrt2\,x)^2$.

How to find it. The hypothesis is about a polynomial, so the natural measure is its degree, and every polynomial of positive degree has a root to peel off. The two-squares identity is what lets the smaller case be multiplied back up.