Analysis: Sequences + Algebra: Polynomials I + LA: Vector Spaces + Comb: Counting Intro

The Monotone Convergence Theorem — a bounded increasing sequence converges — is completeness from Week 1 in its most usable outfit: the limit is exactly $\sup\{a_n\}$. On the exam it converts 'find the limit' into a two-move routine: prove monotone, prove bounded, THEN name the limit by passing to the limit in the recurrence. The order matters; naming the limit first proves nothing.

For recursively defined sequences $a_{n+1} = f(a_n)$, the candidate limits are the fixed points $L = f(L)$ — solve that equation before anything else, because knowing the destination tells you what to prove. If $a_1 = 1$ and $a_{n+1} = \sqrt{2 + a_n}$, the fixed-point equation $L = \sqrt{2+L}$ gives $L = 2$, and now 'show $a_n < 2$' and 'show increasing' are concrete targets, both falling to induction from Week 1.

Two subsequential tricks earn their place early: a sequence converges iff its even and odd subsequences converge to the SAME limit (alternating recurrences live here), and every sequence has a monotone subsequence — which with boundedness gives Bolzano–Weierstrass and, in Week 4, compactness.

Pitfall. Passing to the limit in the recurrence BEFORE proving convergence exists. The equation $L = f(L)$ identifies candidates only; without MCT (or another convergence proof) the manipulation is circular.

The factor theorem — $P(a) = 0$ iff $(x-a) \mid P(x)$ — has a corollary that solves problems by itself: a nonzero polynomial of degree $n$ has at most $n$ roots. Contest form: if a degree-$\le n$ polynomial vanishes at $n+1$ points, it is identically zero; if two degree-$\le n$ polynomials agree at $n+1$ points, they are the SAME polynomial. Half of all 'show this identity' problems are the sentence 'both sides are polynomials of degree $n$ agreeing at $n+1$ points'.

Vieta's formulas are the dictionary between roots and coefficients: for monic $x^n + c_{n-1}x^{n-1} + \cdots + c_0$ with roots $r_1, \dots, r_n$, the elementary symmetric functions satisfy $e_1 = -c_{n-1}$, $e_2 = c_{n-2}$, alternating signs down to $e_n = (-1)^n c_0$. The exam move is almost never to FIND the roots — it is to compute symmetric expressions in them ($\sum r_i^2 = e_1^2 - 2e_2$) straight from coefficients.

Keep one structural fact loaded: real polynomials factor over $\mathbb{R}$ into linear and irreducible quadratic factors, because complex roots of real polynomials come in conjugate pairs. This is why odd-degree real polynomials always have a real root — a fact you will re-derive via IVT in Week 4 and should recognize from both directions.

Pitfall. Sign errors in Vieta. For monic $P$, $e_k = (-1)^k c_{n-k}$ — write the general rule once at the top of your scratch work instead of re-deriving signs mid-problem.

Linear algebra on the Putnam is rarely about matrices as grids of numbers — it is about dimension as a counting weapon. The core fact: in a space of dimension $n$, any $n+1$ vectors are linearly dependent. That single sentence kills problems that look combinatorial: to show some clever combination of objects exists, encode the objects as vectors in a small-dimensional space and let the pigeonhole of dimension produce the dependence for you.

The rank–nullity theorem, $\dim \ker T + \operatorname{rank} T = \dim V$, is the conservation law of the subject. Its contest voice: a linear map from a bigger space to a smaller one has nontrivial kernel — something nonzero maps to zero, and that something is usually the object the problem asked you to find. Learn to hear 'more unknowns than equations' as 'nontrivial kernel exists'.

When asked whether specific functions or sequences are independent, the working test is: write $c_1 v_1 + \cdots + c_k v_k = 0$ and EVALUATE at well-chosen points, or differentiate, or compare growth rates as $x \to \infty$ — anything that turns one vector equation into enough scalar equations to force every $c_i = 0$.

Pitfall. Getting the two directions backwards. Finitely many well-chosen evaluations CAN prove independence — if the resulting scalar system forces every $c_i = 0$ (a nonsingular evaluation matrix), you are done. What finitely many points can NEVER prove is dependence: a claimed relation must vanish identically, for ALL $x$, not just at your three favorite points.

Every counting argument on this exam is one of two moves. Either you exhibit a bijection — the sets have equal size because here is an explicit invertible map — or you count one set two ways and set the answers equal. Ninety percent of lost combinatorics points come from doing one of these implicitly and sloppily rather than explicitly and simply. Name your move in the first line of the solution.

The binomial coefficient identities you will use forever all have one-line double counts. Pascal: $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ — does the committee include person $n$ or not? Committee-chair: $k\binom{n}{k} = n\binom{n-1}{k-1}$ — count (committee, chair) pairs by choosing the committee first or the chair first. Vandermonde: $\binom{m+n}{k} = \sum_j \binom{m}{j}\binom{n}{k-j}$ — split the pool. The identities are forgettable; the stories are not. Store the stories.

Stars and bars closes the week: the number of solutions to $x_1 + \cdots + x_k = n$ in nonnegative integers is $\binom{n+k-1}{k-1}$, via the bijection with arrangements of $n$ stars and $k-1$ bars. It is the prototype 'encode, then count the encodings' argument — the shape of half the distribution problems in the archive.

Pitfall. A 'bijection' with no inverse exhibited. If you cannot say in one sentence how to recover the input from the output, you have a surjection and a hope — and the grader knows the difference.