Polynomials

So $\sum r_i^2 = e_1^2 - 2e_2$ always ($= 4$ for $x^4 - 2x^2 + 3$, whose roots are complex), and any symmetric expression in the roots is a polynomial in the coefficients. The reverse direction — given $p_1, p_2, p_3$, recover $e_1, e_2, e_3$ and hence the roots — solves systems like $x + y + z = 6$, $x^2 + y^2 + z^2 = 14$, $x^3 + y^3 + z^3 = 36$.

The filter extracts every $n$th coefficient of a polynomial (or generating function): the number of subsets of $\{1..N\}$ with size divisible by $3$, the sum of $\binom{n}{3k}$, the coefficient sums of $(1 + x + x^2)^n$ at spacing $3$. Also $x^n - 1 = \prod(x - \omega^k)$ gives $\prod_{k=1}^{n-1}(1 - \omega^k) = n$ and the trig products $\prod\sin\tfrac{k\pi}{n} = \tfrac{n}{2^{n-1}}$.

The divisibility fact kills "find an integer polynomial with $P(1) = 2$, $P(4) = 7$" ($3 \nmid 5$). Interpolation with consecutive integer nodes is fastest by finite differences ($P(0), P(1), P(2) = 1, 2, 5$ gives second difference $2$, so $P(3) = 10$). Chebyshev polynomials $T_n(\cos\theta) = \cos n\theta$ handle "polynomial bounded by $1$ on $[-1,1]$" extremal problems.

$x^3 + y^3 = (x+y)^3 - 3xy(x+y)$: $35 = 125 - 15xy$, so $xy = 6$ — and indeed $\{x, y\} = \{2, 3\}$.

$e_1^2 = (\sum r_i)^2 = \sum r_i^2 + 2\sum_{i<j}r_ir_j = p_2 + 2e_2$ — rearrange. For the general identity, expand $\prod_i(1 - r_it) = \sum(-1)^ke_kt^k$, take the logarithmic derivative, and compare coefficients of $t^{k-1}$ with $-\sum_i\tfrac{r_i}{1 - r_it} = -\sum_kp_kt^{k-1}$. $\blacksquare$ Significance: the generating-function proof is a template — many Putnam identities are "compare coefficients after a log-derivative."

$\tfrac1n\sum_jP(\omega^j) = \sum_ka_k\cdot\tfrac1n\sum_j\omega^{jk}$, and the inner average is $1$ when $n \mid k$ (every term is $1$) and $0$ otherwise (a geometric series with ratio $\omega^k \ne 1$ summing to $\tfrac{\omega^{kn} - 1}{\omega^k - 1} = 0$). $\blacksquare$ Significance: this is the discrete Fourier transform in its simplest form; shifting by $\omega^{-jr}$ picks out the residue class $r$. It is how one counts subsets by size mod $n$ — a Putnam favorite.

Step 1 — the answer is $\sum_{3\mid k}\binom{10}{k}$, the filter applied to $P(x) = (1 + x)^{10}$.

Step 2 — $\tfrac13\left[P(1) + P(\omega) + P(\omega^2)\right]$ with $\omega = e^{2\pi i/3}$: $P(1) = 1024$; $1 + \omega = -\omega^2 = e^{i\pi/3}$, so $P(\omega) = e^{10i\pi/3} = e^{-2i\pi/3}$; similarly $P(\omega^2) = e^{2i\pi/3}$.

Step 3 — $P(\omega) + P(\omega^2) = 2\cos\tfrac{2\pi}{3} = -1$.

Step 4 — total $\tfrac{1024 - 1}{3} = 341$. Check: $\binom{10}{0} + \binom{10}{3} + \binom{10}{6} + \binom{10}{9} = 1 + 120 + 210 + 10 = 341$ ✓.

Step 1 — consider $Q(x) = (x + 1)P(x) - x$, degree $n + 1$, vanishing at $x = 0, 1, \ldots, n$: so $Q(x) = c\,x(x-1)\cdots(x-n)$.

Step 2 — evaluate at $x = -1$: $Q(-1) = 0\cdot P(-1) + 1 = 1 = c(-1)(-2)\cdots(-n-1) = c(-1)^{n+1}(n+1)!$, giving $c = \tfrac{(-1)^{n+1}}{(n+1)!}$.

Step 3 — at $x = n + 1$: $Q(n+1) = c(n+1)! = (-1)^{n+1}$, so $(n+2)P(n+1) - (n+1) = (-1)^{n+1}$ and $P(n+1) = \dfrac{n + 1 + (-1)^{n+1}}{n + 2}$ — equal to $1$ for odd $n$ and $\tfrac{n}{n+2}$ for even $n$. The auxiliary polynomial with known roots is THE technique for "values at consecutive integers."