Putnam 1990

Let $$T_0 = 2, T_1 = 3, T_2 = 6,$$ and for $n \geq 3$, $$T_n = (n+4)T_{n-1} - 4n T_{n-2} + (4n-8) T_{n-3}.$$ The first few terms are $$2, 3, 6, 14, 40, 152, 784, 5168, 40576.$$ Find, with proof, a formula for $T_n$ of the form $T_n = A_n + B_n$, where $\{A_n\}$ and $\{B_n\}$ are well-known sequences.

Is $\sqrt{2}$ the limit of a sequence of numbers of the form $\sqrt[3]{n} - \sqrt[3]{m}$ ($n,m = 0, 1, 2, \dots$)?

Prove that any convex pentagon whose vertices (no three of which are collinear) have integer coordinates must have area greater than or equal to 5/2.

Consider a paper punch that can be centered at any point of the plane and that, when operated, removes from the plane precisely those points whose distance from the center is irrational. How many punches are needed to remove every point?

If $\mathbf{A}$ and $\mathbf{B}$ are square matrices of the same size such that $\mathbf{ABAB = 0}$, does it follow that $\mathbf{BABA = 0}$?

If $X$ is a finite set, let $X$ denote the number of elements in $X$. Call an ordered pair $(S, T)$ of subsets of $\{1, 2, \dots, n\}$ admissible if $s > |T|$ for each $s \in S$, and $t > |S|$ for each $t \in T$. How many admissible ordered pairs of subsets of $\{1, 2, \dots, 10\}$ are there? Prove your answer.

Find all real-valued continuously differentiable functions $f$ on the real line such that for all $x$, $$(f(x))^2 = \int_0^x [(f(t))^2 + (f'(t))^2] dt + 1990.$$

Prove that for $|x| < 1$, $|z| > 1$, $$1 + \sum_{j=1}^\infty (1 + x^j)P_j = 0,$$ where $P_j$ is $$\frac{(1 - z)(1 - zx)(1 - zx^2) \cdots (1 - zx^{j-1})} {(z - x)(z - x^2)(z - x^3) \cdots (z - x^j)}.$$

Let $S$ be a set of $2 \times 2$ integer matrices whose entries $a_{ij}$ (1) are all squares of integers and, (2) satisfy $a_{ij} \leq 200$. Show that if $S$ has more than 50387 ($= 15^4 - 15^2 - 15 + 2$) elements, then it has two elements that commute.

Let $G$ be a finite group of order $n$ generated by $a$ and $b$. Prove or disprove: there is a sequence $$g_1, g_2, g_3, \dots, g_{2n}$$ such that

(1) every element of $G$ occurs exactly twice, and

(2) $g_{i+1}$ equals $g_i a$ or $g_i b$ for $i = 1, 2, \dots, 2n$. (Interpret $g_{2n+1}$ as $g_1$.)

Is there an infinite sequence $a_0, a_1, a_2, \dots$ of nonzero real numbers such that for $n = 1, 2, 3, \dots$ the polynomial $$p_n(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$$ has exactly $n$ distinct real roots?

Let $S$ be a nonempty closed bounded convex set in the plane. Let $K$ be a line and $t$ a positive number. Let $L_1$ and $L_2$ be support lines for $S$ parallel to $K_1$, and let $\overline{L}$ be the line parallel to $K$ and midway between $L_1$ and $L_2$. Let $B_S(K, t)$ be the band of points whose distance from $\overline{L}$ is at most $(t/2)w$, where $w$ is the distance between $L_1$ and $L_2$. What is the smallest $t$ such that $$S \cap \bigcap_K B_S(K, t) \neq \emptyset$$ for all $S$? ($K$ runs over all lines in the plane.)