Strategy & Writing a 10

A-1/B-1 and A-2/B-2 are designed to be solvable with the material in this course; the median competitor still scores $0$ on them by starting problem $3$ first or by leaving a correct idea unwritten. Forty minutes of clean work on an accessible problem is worth more than three hours of near-misses. If a problem asks for a value, find it numerically or by small cases FIRST, then prove it — knowing the answer transforms the search.

Name the theorems you use ("by the mean value theorem on $[1, 1+x]$…"). State hypotheses when you invoke them (continuity for IVT, absolute convergence for rearranging, a dominating function for swapping limit and integral). Handle the equality case of every inequality and the base case of every induction. Write in complete sentences; a solution that reads like a proof is graded like one.

Most Putnam problems hide a clean answer ($\tfrac{\pi}{4}$, $n + 1$, $\tfrac{1}{e}$, $\binom{2n}{n}$); small cases reveal it, and knowing the target usually reveals the method. Symmetry, extremal choices, and generating functions are the three most common "second ideas" after the pattern is found.

Putnam answers are almost always clean ($\tfrac23$, $n + 1$, "only $n = 1$"), so a few exact values usually pin the answer down. Once the target is known, the proof is a search with a destination: to prove a partial product equals $\tfrac{2(n^2 + n + 1)}{3n(n+1)}$, one looks for factors that cancel to leave exactly that expression. Keeping values as exact fractions matters — $\tfrac{13}{18}$ suggests a formula, $0.7222$ does not.

Step 1 — small cases: $n = 1, 2, 3, 4$ give $1$, $1 + 4 = 5$, $5 + 18 = 23$, $23 + 96 = 119$.

Step 2 — each is one less than a factorial: $2! - 1$, $3! - 1$, $4! - 1$, $5! - 1$. Conjecture: $\sum_{k=1}^n k\cdot k! = (n + 1)! - 1$.

Step 3 — the conjecture is a difference, so look for a telescoping term: $k\cdot k! = (k + 1)\cdot k! - k! = (k + 1)! - k!$. Summing from $1$ to $n$ leaves $(n + 1)! - 1!$. $\blacksquare$

How to find it. "One less than" a familiar sequence is the fingerprint of a telescoping sum whose first term is $1$. Rewrite the summand as a difference of consecutive terms of the familiar sequence.

Step 1 — small cases, exactly: $P_2 = \tfrac79$, $P_3 = \tfrac79\cdot\tfrac{26}{28} = \tfrac{13}{18}$, $P_4 = \tfrac{13}{18}\cdot\tfrac{63}{65} = \tfrac{7}{10}$.

Step 2 — the numerators $7, 13, 21$ (after writing $\tfrac7{10} = \tfrac{21}{30}$) are $n^2 + n + 1$, and the denominators $9, 18, 30$ are $\tfrac32n(n+1)$. Conjecture $P_n = \tfrac{2(n^2 + n + 1)}{3n(n+1)}$, which tends to $\tfrac23$.

Step 3 — prove it by factoring: $\dfrac{k^3 - 1}{k^3 + 1} = \dfrac{k - 1}{k + 1}\cdot\dfrac{k^2 + k + 1}{k^2 - k + 1}$. The first factors multiply to $\dfrac{1\cdot2}{n(n+1)}$ (each numerator reappears two places later as a denominator). For the second, note $k^2 - k + 1 = (k - 1)^2 + (k - 1) + 1$: the denominator at $k$ is the numerator at $k - 1$, so the product telescopes to $\dfrac{n^2 + n + 1}{3}$.

Step 4 — $P_n = \dfrac{2}{n(n+1)}\cdot\dfrac{n^2 + n + 1}{3}$, exactly the conjecture, and $P_n \to \tfrac23$. $\blacksquare$

How to find it. The small cases produced $n^2 + n + 1$, which is the factor of $n^3 - 1$; knowing the answer's shape told us which factorization to use and that it must telescope.

Step 1 — small cases: $n = 1$ works; $n = 2, \ldots, 30$ all fail (even $n$ fail because $2^n - 1$ is odd; $3 \nmid 7$, $5 \nmid 31$, $7 \nmid 127$, $9 \nmid 511$, …). Conjecture: only $n = 1$.

Step 2 — to prove non-existence, suppose $n > 1$ works and let $p$ be the SMALLEST prime factor of $n$. Then $2^n \equiv 1 \pmod p$, and $p$ is odd.

Step 3 — let $d$ be the order of $2$ mod $p$. Then $d \mid n$ (because $2^n \equiv 1$) and $d \mid p - 1$ (Fermat). Every prime factor of $d$ divides $n$ and is less than $p$ — impossible by the choice of $p$ — so $d = 1$.

Step 4 — $d = 1$ means $2 \equiv 1 \pmod p$, i.e. $p \mid 1$: contradiction. Answer: $n = 1$ only. $\blacksquare$

How to find it. When small cases say "nothing works", the proof is usually a contradiction built on an extreme choice. Orders are the tool for $a^n \equiv 1$, and the smallest prime factor is exactly the choice that makes $\gcd(n, p - 1) = 1$.

Putnam problems are graded $0$–$10$, but the scores cluster at $0$–$2$ and $8$–$10$: a solution is judged as a proof, and a proof with a gap is not a proof. The right idea with an unjustified step is worth about as much as the idea alone. The two write-ups below use the same idea; one scores about $2$, the other $10$, and the difference is three sentences.

What the grader marks. First, the pointwise claim is false at $x = 1$, where $x^nf(x) = f(1)$ for every $n$; the solution silently drops a point. That alone is harmless for an integral, but the solution never says so. Second, and fatally, "the integrand tends to $0$, hence the integral tends to $0$" is an interchange of limit and integral with no justification, and it is false in general: $f_n = n$ on $(0, \tfrac1n)$ and $0$ elsewhere tends to $0$ pointwise while $\int_0^1 f_n = 1$ for every $n$. The solution has not used that $f$ is continuous — the one hypothesis that makes the statement true. Score: about $2$ (the right idea, no proof).

Solution. Since $f$ is continuous on the closed bounded interval $[0, 1]$, it is bounded there by the extreme value theorem: $|f(x)| \le M$ for some $M$. Hence for every $n$,

The right side tends to $0$, so by the squeeze theorem $\int_0^1x^nf(x)\,dx \to 0$. $\blacksquare$

Why it scores $10$: the continuity hypothesis is used, and named with its theorem; the limit is taken of a NUMBER ($\tfrac{M}{n+1}$), so no interchange is needed; the conclusion is stated. It is also shorter than a repaired version of the first attempt would be — rigor often simplifies.

Step 1 — reduce to a statement about $f - f(1)$. Since $n\int_0^1x^n\,dx = \tfrac{n}{n+1} = 1 - \tfrac{1}{n+1}$,

The last term tends to $0$, so it suffices to show the integral term does.

Step 2 — let $\varepsilon > 0$. By continuity of $f$ at $1$ choose $\delta \in (0, 1)$ with $|f(x) - f(1)| < \varepsilon$ for $x \in [1 - \delta, 1]$, and let $M$ bound $|f|$ on $[0, 1]$ (extreme value theorem).

Step 3 — split the integral at $1 - \delta$. On $[1 - \delta, 1]$: at most $\varepsilon\,n\int_0^1x^n\,dx < \varepsilon$. On $[0, 1 - \delta]$: at most $2M\,n\int_0^{1-\delta}x^n\,dx = 2M\tfrac{n}{n+1}(1 - \delta)^{n+1} \le 2M(1 - \delta)^{n+1}$, which tends to $0$, so it is less than $\varepsilon$ for all large $n$.

Step 4 — hence for all large $n$ the integral term is less than $2\varepsilon$ in absolute value; $\varepsilon$ was arbitrary, so it tends to $0$, and $n\int_0^1x^nf(x)\,dx \to f(1)$. $\blacksquare$

How to find it. The weights $nx^n$ have total mass nearly $1$ and pile up at $x = 1$ (figure), so the integral should behave like $f(1)$. Turning "piles up" into a proof is the standard split: near the point, use continuity; away from it, use a bound and the decay of $(1 - \delta)^n$.