The Art of Problem Solving

Combined rate: $\frac{1}{5} + \frac{1}{4} = \frac{9}{20}$ pools per hour, so $t = \frac{20}{9} \approx 2.22$ hours.

Minute hand: $6°$/min, hour hand: $0.5°$/min. At 4:00, the hour hand is at $120°$. The hands coincide when $6t = 120 + 0.5t$, i.e. $5.5t = 120$, so $t = \frac{240}{11} \approx 21.82$ minutes.

Unit digits of powers of 7 cycle with period 4: $7, 9, 3, 1, \ldots$ Since $42 \equiv 2 \pmod{4}$, the unit digit of $7^{42}$ is $9$.

Unit digits of powers of 2 cycle with period 4: $2, 4, 8, 6, \ldots$ Since $7 \equiv 3 \pmod{4}$, the unit digit of $42^7$ is $8$.

Therefore the unit digit of $7^{42} + 42^7$ is $9 + 8 = 17$, i.e. $\mathbf{7}$.

One person paints $\frac{5}{4 \times 3} = \frac{5}{12}$ houses per day. Two people paint $\frac{5}{6}$ houses per day, so 6 houses takes $\frac{6}{5/6} = \frac{36}{5} = 7.2$ days.

Since $P\!\left(\frac{p}{q}\right) = 0$, multiplying by $q^n$ gives $$a_n p^n + a_{n-1} p^{n-1} q + \cdots + a_1 p q^{n-1} + a_0 q^n = 0.$$

Isolating $a_0 q^n$: $$a_0 q^n = -p \left( a_n p^{n-1} + a_{n-1} p^{n-2} q + \cdots + a_1 q^{n-1} \right),$$ so $p \mid a_0 q^n$. Since $\gcd(p, q) = 1$, we have $\gcd(p, q^n) = 1$, hence $p \mid a_0$.

Isolating $a_n p^n$: $$a_n p^n = -q \left( a_{n-1} p^{n-1} + a_{n-2} p^{n-2} q + \cdots + a_0 q^{n-1} \right),$$ so $q \mid a_n p^n$. Since $\gcd(q, p^n) = 1$, we conclude $q \mid a_n$.

By the rational root theorem, any rational root $\frac{p}{q}$ (in lowest terms) satisfies $p \mid 1$ and $q \mid 2$, so the candidates are $\pm 1, \pm \frac{1}{2}$.

Testing $x = 1$: $2 - 5 + 4 - 1 = 0$, so $1$ is a root. Polynomial division yields $$2x^3 - 5x^2 + 4x - 1 = (x - 1)(2x^2 - 3x + 1) = (x - 1)^2 (2x - 1).$$

The roots are $x = 1$ (double) and $x = \frac{1}{2}$.

Since $P$ has roots $r_1, \ldots, r_n$ and leading coefficient $a_n$, we have $$P(x) = a_n \prod_{i=1}^{n} (x - r_i).$$

Expanding the product, the coefficient of $x^{n-k}$ is obtained by choosing $x$ from $n - k$ of the factors and $-r_i$ from the remaining $k$ factors, summed over all such choices: $$\prod_{i=1}^{n} (x - r_i) = \sum_{k=0}^{n} \left( \sum_{1 \leq i_1 < \cdots < i_k \leq n} \prod_{j=1}^{k} (-r_{i_j}) \right) x^{n-k} = \sum_{k=0}^{n} (-1)^k e_k \, x^{n-k},$$ with the convention $e_0 = 1$.

Therefore $$P(x) = \sum_{k=0}^{n} (-1)^k a_n e_k \, x^{n-k}.$$ Identifying with $P(x) = \sum_{k=0}^{n} a_{n-k} x^{n-k}$ gives $a_{n-k} = (-1)^k a_n e_k$, hence $$e_k = (-1)^k \frac{a_{n-k}}{a_n}.$$

Let $r$ be the fourth root. Since the coefficient of $x^3$ is $0$, Vieta's formulas give $e_1 = 0$: $$-1 + 2 + 3 + r = 0 \implies r = -4.$$

The polynomial factors as $$(x+1)(x-2)(x-3)(x+4) = (x^2 - x - 2)(x^2 + x - 12) = x^4 - 15 x^2 + 10 x + 24.$$ So $A = -15$, $B = 10$, $C = 24$.

Therefore $2C - AB = 48 - (-15)(10) = 48 + 150 = \mathbf{198}$.

For any $x \neq 0$, $$x^n P\!\left(\frac{1}{x}\right) = x^n \left( a_n x^{-n} + a_{n-1} x^{-(n-1)} + \cdots + a_0 \right) = a_n + a_{n-1} x + \cdots + a_0 x^n = Q(x).$$

Since $a_0 \neq 0$, no root of $P$ is $0$. If $r$ is a root of $P$, then $r \neq 0$ and $$Q(1/r) = (1/r)^n P(r) = 0,$$ so $1/r$ is a root of $Q$. Conversely, $a_0 \neq 0$ ensures $\deg Q = n$, so $Q$ has $n$ roots (with multiplicity) just like $P$. Hence the roots of $Q$ are exactly $\{1/r : r \text{ root of } P\}$.

If $r$ is a root of $P$, we want $kr$ to be a root of the new polynomial $Q$, i.e. $Q(kr) = 0$. This suggests $Q(x) = P(x/k)$: $$P(x/k) = a_n \frac{x^n}{k^n} + a_{n-1} \frac{x^{n-1}}{k^{n-1}} + \cdots + a_0.$$

Multiplying by $k^n$ to clear denominators gives the polynomial $$Q(x) = a_n x^n + a_{n-1} k \, x^{n-1} + a_{n-2} k^2 \, x^{n-2} + \cdots + a_0 k^n = \sum_{i=0}^{n} a_i k^{n-i} x^i.$$

By construction, $Q(kr) = k^n P(r) = 0$ for every root $r$ of $P$, and since $\deg Q = n$, these are all the roots.

Set $y = \frac{1}{x+3}$, so $x = \frac{1-3y}{y}$. The roots of $P$ in $x$ map to $\frac{1}{a+3}, \frac{1}{b+3}, \frac{1}{c+3}$ in $y$, which are the roots of $y^3 \cdot P\!\left(\frac{1-3y}{y}\right)$: $$(1-3y)^3 + (1-3y)^2 y - (1-3y) y^2 - 3 y^3 = -18 y^3 + 20 y^2 - 8 y + 1.$$

By Vieta's, the sum of roots is $\displaystyle -\frac{20}{-18} = \mathbf{\frac{10}{9}}$.

For each root $r_i$, $P(r_i) = 0$: $$a_n r_i^n + a_{n-1} r_i^{n-1} + \cdots + a_0 = 0.$$ Multiplying by $r_i^{k-n}$ (valid since $k \geq n$) gives $$a_n r_i^k + a_{n-1} r_i^{k-1} + \cdots + a_0 r_i^{k-n} = 0.$$

Summing over $i = 1, \ldots, n$: $$a_n s_k + a_{n-1} s_{k-1} + \cdots + a_0 s_{k-n} = 0.$$ (For $k = n$, the last term is $a_0 s_0 = a_0 n$.)

Apply Newton's sums with $k = n = 1000$: $$a_{1000} s_{1000} + a_{999} s_{999} + \cdots + a_1 s_1 + a_0 \cdot 1000 = 0.$$ Here $a_{1000} = 1$, $a_1 = -10$, $a_0 = 10$, and all other coefficients vanish, so $$s_{1000} - 10 s_1 + 10000 = 0.$$

By Vieta's, $s_1 = \sum r_i = -a_{999}/a_{1000} = 0$. Therefore $$s_{1000} = -10000.$$

Expanding the square of $s_1$: $$s_1^2 = \left( \sum_{i=1}^{n} r_i \right)^2 = \sum_{i=1}^{n} r_i^2 + 2 \sum_{i \lt j} r_i r_j = s_2 + 2 e_2,$$ where $e_2 = \sum_{i \lt j} r_i r_j$ is the second elementary symmetric sum. Hence $s_2 = s_1^2 - 2 e_2$.

By Vieta's, $s_1 = e_1 = -\frac{a_{n-1}}{a_n}$ and $e_2 = \frac{a_{n-2}}{a_n}$, so $$s_2 = \frac{a_{n-1}^2}{a_n^2} - \frac{2 a_{n-2}}{a_n}.$$ Multiplying by $a_n$ and rearranging: $$a_n s_2 = \frac{a_{n-1}^2}{a_n} - 2 a_{n-2} = -a_{n-1} s_1 - 2 a_{n-2},$$ i.e. $a_n s_2 + a_{n-1} s_1 + 2 a_{n-2} = 0$.

Reversing the coefficients gives the polynomial whose roots are $\frac{1}{r}, \frac{1}{s}, \frac{1}{t}$ (since $x^3 P(1/x) = -7 x^3 + 5 x^2 - 6 x + 1$ vanishes at $1/r$ whenever $P(r) = 0$): $$Q(x) = -7 x^3 + 5 x^2 - 6 x + 1.$$ We want $s_2$ for $Q$. Applying Newton's identity $a_n s_2 + a_{n-1} s_1 + 2 a_{n-2} = 0$ with $a_3 = -7$, $a_2 = 5$, $a_1 = -6$: $$-7 s_2 + 5 s_1 - 12 = 0.$$

By Vieta's on $Q$, $s_1 = -\frac{a_2}{a_3} = \frac{5}{7}$, so $$-7 s_2 = 12 - 5 \cdot \frac{5}{7} = \frac{59}{7} \implies s_2 = \mathbf{-\frac{59}{49}}.$$

Since $P$ has integer coefficients, $a \equiv b \pmod 2 \implies P(a) \equiv P(b) \pmod 2$.

Suppose $r \in \mathbb{Z}$ is a root of $P$. Then $P(r) = 0$ is even. But $r$ is either even or odd:

• if $r$ is even, $P(r) \equiv P(0) \equiv 1 \pmod 2$;
• if $r$ is odd, $P(r) \equiv P(1) \equiv 1 \pmod 2$.

The $n$-th roots of unity are the roots of $P(x) = x^n - 1$. By Vieta's, $$\prod_{k=0}^{n-1} \omega_k = (-1)^n \frac{a_0}{a_n} = (-1)^n \cdot (-1) = (-1)^{n+1}.$$

So the product is $1$ if $n$ is odd, and $-1$ if $n$ is even.

Let the roots be $r$, $-r$, $s$. By Vieta's, $r + (-r) + s = \frac{12}{4} = 3$, so $s = 3$.

Method 1 (more Vieta's): The other two Vieta relations give $$r(-r) + rs + (-r)s = -r^2 = \frac{c}{4}, \qquad r \cdot (-r) \cdot s = -3 r^2 = -\frac{d}{4}.$$ So $r^2 = -\frac{c}{4} = \frac{d}{12}$, hence $d = -3c$ and $\displaystyle \frac{d}{c} = \mathbf{-3}$.

Method 2 (plug in the known root): Since $s = 3$ is a root, $P(3) = 0$: $$4(27) - 12(9) + 3c + d = 108 - 108 + 3c + d = 3c + d = 0,$$ so $d = -3c$ and $\displaystyle \frac{d}{c} = \mathbf{-3}$.

Method 1 (remainder theorem): The remainder of $P(x)$ divided by $x - a$ is $P(a)$. Here $P(x) = x^{13} + 1$ and $a = 1$, so the remainder is $P(1) = 1 + 1 = \mathbf{2}$.

Method 2 (explicit division): Using the geometric series identity $x^{13} - 1 = (x-1)(x^{12} + x^{11} + \cdots + x + 1)$, we get $$x^{13} + 1 = (x-1)\underbrace{(x^{12} + x^{11} + \cdots + x + 1)}_{Q(x)} + \underbrace{2}_{R}.$$

Set $P(x) = (1 + x + x^2)^n$. Then $$P(1) = a_0 + a_1 + \cdots + a_{2n}, \qquad P(-1) = a_0 - a_1 + a_2 - \cdots + a_{2n}.$$ Adding and dividing by $2$ isolates the even-indexed coefficients: $$a_0 + a_2 + \cdots + a_{2n} = \frac{P(1) + P(-1)}{2} = \frac{3^n + 1^n}{2} = \mathbf{\frac{3^n + 1}{2}}.$$

Method 1 (congruences): Since $x^4 \equiv 1 \pmod{x^4 - 1}$ and $203 = 4 \cdot 50 + 3$, $$x^{203} = (x^4)^{50} \cdot x^3 \equiv x^3 \pmod{x^4 - 1}.$$ So $x^{203} - 1 \equiv x^3 - 1 \pmod{x^4 - 1}$, and the remainder is $\mathbf{x^3 - 1}$.

Method 2 (evaluate at roots): Write the Euclidean division as $x^{203} - 1 = (x^4 - 1) Q(x) + R(x)$ with $R(x) = a x^3 + b x^2 + c x + d$. The roots of $x^4 - 1$ are $1, -1, i, -i$, and at each root the left side equals $R$ evaluated there. Using $i^{203} = i^{4 \cdot 50 + 3} = i^3 = -i$:

• $x = 1$:   $0 = a + b + c + d$,
• $x = -1$:   $-2 = -a + b - c + d$,
• $x = i$:   $-i - 1 = -a i - b + c i + d$,
• $x = -i$:   $i - 1 = a i - b - c i + d$.

From the first two: $b + d = -1$ and $a + c = 1$. From the last two (real and imaginary parts): $-b + d = -1$ and $a - c = 1$. Solving: $a = 1$, $b = 0$, $c = 0$, $d = -1$, giving $R(x) = \mathbf{x^3 - 1}$.

Set $Y = P(X)$. The equation becomes $P(Y) = Y^k$ for every $Y$ in the image of $P$.

Case 1: $P$ non-constant. Then $P$ takes infinitely many values, so $P(Y) - Y^k$ vanishes at infinitely many points, hence $P(Y) = Y^k$ as polynomials. Conversely, $P(X) = X^k$ satisfies $P(P(X)) = (X^k)^k = X^{k^2} = P(X)^k$.

Case 2: $P$ constant, $P(X) = c$. Then $c = c^k$, i.e. $c(c^{k-1} - 1) = 0$. Over $\mathbb{R}$, this gives $c = 0$, $c = 1$, or $c = -1$ (the last only when $k$ is odd, so that $k-1$ is even).

The real solutions are therefore $P(X) = X^k$, $P(X) = 0$, $P(X) = 1$, and (for odd $k$) $P(X) = -1$.

Setting $y = 1$ gives $f(x) = x f(1)$, so $f(x) = cx$ with $c = f(1)$.

Conversely, $f(x) = cx$ satisfies $f(xy) = c(xy) = x (cy) = x f(y)$. So the solutions are exactly $f(x) = cx$, $c \in \mathbb{R}$.

Method 1: Setting $y = 1$ gives $f(x) = x f(1)$. Writing $c = f(1)$, we get $f(x) = cx$ for all $x$.

Method 2: For $x, y \neq 0$, dividing both sides by $xy$ gives $\frac{f(x)}{x} = \frac{f(y)}{y}$. So $g(t) = \frac{f(t)}{t}$ takes the same value for every nonzero $t$, i.e. $g$ is constant on $\mathbb{R} \setminus \{0\}$. Call this constant $c$; then $f(t) = ct$ for all $t \neq 0$. For $t = 0$, setting $x = 0$ and any $y \neq 0$ in the original equation gives $y f(0) = 0$, hence $f(0) = 0 = c \cdot 0$.

Conversely, any $f(x) = cx$ satisfies $y \cdot cx = x \cdot cy$. So the solutions are exactly the linear maps $f(x) = cx$, $c \in \mathbb{R}$.

Method 1: Setting $y = 0$ gives $2 f(x) = 2 x^2$, so $f(x) = x^2$.

Method 2: Setting $x = y = 0$ gives $2 f(0) = 0$, so $f(0) = 0$. Setting $x = y$ then gives $f(2x) + f(0) = 4 x^2$, so $f(2x) = (2x)^2$, i.e. $f(u) = u^2$ for all $u \in \mathbb{R}$.

Conversely, $f(x) = x^2$ satisfies $(x+y)^2 + (x-y)^2 = 2x^2 + 2y^2$. So $f(x) = x^2$ is the unique solution.

Setting $y = 0$ gives $2 f(x) = 2 x^2$, so $f(x) = x^2$. Setting $x = 0$ gives $f(y) + f(-y) = -2 y^2$, but $f(y) + f(-y) = y^2 + y^2 = 2 y^2$, forcing $4 y^2 = 0$ for all $y$, a contradiction.

Hence no such function exists.

Substituting $x \to \frac{1}{x}$ in the equation gives a second relation: $$f(x) + 2 f(1/x) = x, \qquad f(1/x) + 2 f(x) = \frac{1}{x}.$$

This is a linear system in $f(x)$ and $f(1/x)$. Multiplying the second by $2$ and subtracting the first: $$3 f(x) = \frac{2}{x} - x \implies f(x) = \frac{2 - x^2}{3 x}.$$

Conversely, this $f$ satisfies the equation: $\displaystyle \frac{2 - x^2}{3x} + 2 \cdot \frac{2 - 1/x^2}{3/x} = \frac{2 - x^2 + 4 x^2 - 2}{3 x} = x.$

Note that $a = \frac{1+a}{2} - \frac{1-a}{2}$, so the equation rewrites as $$f\!\left(\frac{1+a}{2}\right) - \frac{1+a}{2} = f\!\left(\frac{1-a}{2}\right) - \frac{1-a}{2}.$$ Defining $g(x) = f(x) - x$, this says $g\!\left(\frac{1+a}{2}\right) = g\!\left(\frac{1-a}{2}\right)$ for all $a$, i.e. $g(u) = g(1 - u)$ for all $u$ (since $\frac{1+a}{2} + \frac{1-a}{2} = 1$).

Now define $h(x) = g\!\left(x + \tfrac{1}{2}\right)$. The condition $g(u) = g(1-u)$ becomes $$h\!\left(u - \tfrac{1}{2}\right) = h\!\left(\tfrac{1}{2} - u\right),$$ i.e. $h(t) = h(-t)$: $h$ must be even.

Hence the solutions are exactly $$f(x) = x + h\!\left(x - \tfrac{1}{2}\right),$$ where $h : \mathbb{R} \to \mathbb{R}$ is any even function. (Taking $h(t) = t^2$ recovers $f(x) = x + (x - \tfrac{1}{2})^2 = x^2 + \tfrac{1}{4}$.)

Cross-multiplying gives $x f(x) = y f(y)$ for all $x, y$. So $x f(x)$ is independent of $x$: there is a constant $c$ with $x f(x) = c$, i.e. $f(x) = \frac{c}{x}$. Since $f$ is $\mathbb{R}^*$-valued, $c \neq 0$.

Conversely, $f(x) = c/x$ satisfies $\frac{c/x}{c/y} = \frac{y}{x}$. So the solutions are $f(x) = \frac{c}{x}$ for $c \in \mathbb{R}^*$.

Setting $x = y$ gives $f(2x) - f(0) = 4 x^2$, so $f(u) = u^2 + f(0)$ for all $u \in \mathbb{R}$.

Conversely, $f(x) = x^2 + c$ satisfies $(x+y)^2 - (x-y)^2 = 4xy$. So the solutions are $f(x) = x^2 + c$, $c \in \mathbb{R}$.

Since $1 - 2x = (1-x) - x$, the equation rewrites as $$f(1-x) - (1-x) = f(x) - x.$$ Define $g(x) = f(x) - x$; then $g(1-x) = g(x)$, so $g$ is symmetric about $\tfrac{1}{2}$.

Equivalently, letting $h(t) = g(t + \tfrac{1}{2})$, the condition $g(1-x) = g(x)$ becomes $h(-t) = h(t)$: $h$ is even.

Hence the solutions are exactly $$f(x) = x + h\!\left(x - \tfrac{1}{2}\right),$$ where $h : \mathbb{R} \to \mathbb{R}$ is any even function.

Factor the denominator: $x^2 - 3x + 2 = (x-1)(x-2)$. Testing $x = 2$ in the numerator: $16 - 12 + 2 - 6 = 0$, so $x - 2$ divides the numerator: $$2 x^3 - 3 x^2 + x - 6 = (x - 2)(2 x^2 + x + 3).$$ Hence for $x \neq 2$, $$f(x) = \frac{2 x^2 + x + 3}{x - 1}.$$ The quadratic $2x^2 + x + 3$ has discriminant $1 - 24 \lt 0$, so it has no real roots and $f$ has no $x$-intercepts.

Polynomial division yields $$f(x) = 2 x + 3 + \frac{6}{x - 1}.$$ Key features:

• Removable discontinuity at $x = 2$: the factor $x - 2$ cancels, so $f$ extends by continuity with $f(2) = 13$ (a "hole" in the graph if we keep the original domain).
• Vertical asymptote $x = 1$: $f \to -\infty$ as $x \to 1^-$, $f \to +\infty$ as $x \to 1^+$.
• Oblique asymptote $y = 2 x + 3$.
• $y$-intercept: $f(0) = -3$.

Recognize the limit as a derivative at $0$: $$\lim_{x \to 0} \frac{\sin x}{x} = \lim_{x \to 0} \frac{\sin x - \sin 0}{x - 0} = \sin'(0) = \cos(0) = 1.$$

Write $\tan 3x = \frac{\sin 3x}{\cos 3x}$ and rearrange: $$\frac{\tan 3 x}{4 x} = \frac{\sin 3 x}{3 x} \cdot \frac{3 x}{4 x \cos 3 x}.$$ As $x \to 0$, $\frac{\sin 3x}{3x} \to 1$ and $\cos 3x \to 1$, so the limit is $\displaystyle 1 \cdot \frac{3}{4} = \mathbf{\frac{3}{4}}$.

Take the log: $$\ln\!\left(1 + \tfrac{1}{n}\right)^n = n \ln\!\left(1 + \tfrac{1}{n}\right) = \frac{\ln(1 + 1/n) - \ln 1}{1/n}.$$ As $n \to \infty$, $h = 1/n \to 0$, and this is the difference quotient for $\ln$ at $1$: $$\frac{\ln(1+h) - \ln 1}{h} \longrightarrow \ln'(1) = 1.$$ By continuity of $\exp$, $\displaystyle \left(1 + \tfrac{1}{n}\right)^n = e^{n \ln(1 + 1/n)} \longrightarrow e^1 = e$.

With $n$ equal compounding periods, the balance after one year is $\left(1 + \tfrac{1}{n}\right)^n$. Letting $n \to \infty$ gives $\displaystyle \lim_{n \to \infty} \left(1 + \tfrac{1}{n}\right)^n = e \approx 2.718$ dollars.

Let $u = x/2$, so $\frac{2}{x} = \frac{1}{u}$ and $3 x = 6 u$: $$\left(1 + \frac{2}{x}\right)^{3 x} = \left(1 + \frac{1}{u}\right)^{6 u} = \left(\left(1 + \frac{1}{u}\right)^{u}\right)^{6}.$$ As $x \to \infty$, $u \to \infty$, and $\left(1 + \frac{1}{u}\right)^u \to e$, so the limit is $\mathbf{e^6}$.

Factor using the sum of cubes: $x^3 + 8 = (x + 2)(x^2 - 2 x + 4)$, so for $x \neq -2$, $$\frac{x^3 + 8}{x + 2} = x^2 - 2 x + 4.$$ Taking $x \to -2$: $(-2)^2 - 2(-2) + 4 = \mathbf{12}$.

Polynomial division gives $$f(x) = x - 3 + \frac{4}{x + 2}.$$ As $x \to \pm \infty$, $\frac{4}{x+2} \to 0$, so the oblique asymptote is $\mathbf{y = x - 3}$. Since the numerator does not vanish at $x = -2$ (it equals $4$ there), $f$ also has a vertical asymptote at $\mathbf{x = -2}$.

Recognize the negative of a difference quotient for $\cos$ at $0$: $$\lim_{x \to 0} \frac{1 - \cos x}{x} = -\lim_{x \to 0} \frac{\cos x - \cos 0}{x - 0} = -\cos'(0) = \sin(0) = \mathbf{0}.$$

Polynomial division: $x^3 = x(x^2 - 1) + x$, so $$f(x) = x + \frac{x}{x^2 - 1}.$$ As $x \to \pm \infty$, $\frac{x}{x^2 - 1} \to 0$, giving the oblique asymptote $\mathbf{y = x}$.

The denominator $x^2 - 1 = (x-1)(x+1)$ vanishes at $x = \pm 1$ while the numerator does not, so there are vertical asymptotes at $\mathbf{x = 1}$ and $\mathbf{x = -1}$.

Convert to polar form: $$|4 + 4 i \sqrt{3}| = \sqrt{16 + 48} = 8, \qquad \arg = \arctan(\sqrt{3}) = \frac{\pi}{3}.$$ So $4 + 4 i \sqrt{3} = 8 e^{i \pi / 3}$.

The three cube roots are $$w_k = 8^{1/3} \, e^{i(\pi/3 + 2 \pi k)/3} = 2 \, e^{i(\pi/9 + 2 \pi k / 3)}, \qquad k = 0, 1, 2.$$ Explicitly: $\displaystyle 2 e^{i \pi / 9}, \; 2 e^{i 7 \pi / 9}, \; 2 e^{i 13 \pi / 9}$.

By De Moivre's theorem, $(\cos \theta + i \sin \theta)^3 = \cos(3\theta) + i \sin(3\theta)$. Expanding the left side: $$\cos^3 \theta + 3 i \cos^2 \theta \sin \theta - 3 \cos \theta \sin^2 \theta - i \sin^3 \theta.$$ Taking the real part and using $\sin^2 \theta = 1 - \cos^2 \theta$: $$\cos(3 \theta) = \cos^3 \theta - 3 \cos \theta (1 - \cos^2 \theta) = \mathbf{4 \cos^3 \theta - 3 \cos \theta}.$$

This is a geometric series with ratio $\omega \neq 1$, so $$1 + \omega + \omega^2 + \cdots + \omega^{n-1} = \frac{1 - \omega^n}{1 - \omega}.$$ Since $\omega$ is an $n$-th root of unity, $\omega^n = 1$, so the numerator vanishes while the denominator $1 - \omega \neq 0$. Hence the sum is $\mathbf{0}$.

Case $\omega = 1$: the product is $(1)(1) = 1$.

Case $\omega \neq 1$ (a primitive cube root): then $1 + \omega + \omega^2 = 0$, so $\omega^2 = -1 - \omega$. Substituting, $$1 - \omega + \omega^2 = (1 + \omega + \omega^2) - 2\omega = -2\omega, \qquad 1 + \omega - \omega^2 = (1 + \omega + \omega^2) - 2\omega^2 = -2\omega^2.$$ Hence the product is $(-2\omega)(-2\omega^2) = 4\omega^3 = 4$ (using $\omega^3 = 1$).

The $n$-th roots of unity are $\omega_k = e^{2\pi i k / n}$ for $k = 0, 1, \ldots, n-1$. Their product is $$\prod_{k=0}^{n-1} e^{2\pi i k / n} = e^{\frac{2\pi i}{n} \sum_{k=0}^{n-1} k} = e^{\frac{2\pi i}{n} \cdot \frac{n(n-1)}{2}} = e^{\pi i (n-1)} = (-1)^{n+1}.$$ So the product is $1$ if $n$ is odd, and $-1$ if $n$ is even.

By the multinomial theorem, $$(a + b + c)^3 = \sum_{i+j+k=3} \binom{3}{i,\,j,\,k} a^i b^j c^k, \qquad \binom{3}{i,\,j,\,k} = \frac{3!}{i!\,j!\,k!}.$$ Group the terms by the shape of $(i, j, k)$:

• $(3,0,0)$ and permutations: coefficient $\frac{3!}{3!} = 1$, giving $a^3 + b^3 + c^3$;
• $(2,1,0)$ and permutations: coefficient $\frac{3!}{2!\,1!} = 3$, giving $3(a^2 b + a^2 c + b^2 a + b^2 c + c^2 a + c^2 b)$;
• $(1,1,1)$: coefficient $\frac{3!}{1!\,1!\,1!} = 6$, giving $6abc$.

Hence $$(a + b + c)^3 = a^3 + b^3 + c^3 + 3(a^2 b + a^2 c + b^2 a + b^2 c + c^2 a + c^2 b) + 6abc.$$

The three quantities are the elementary symmetric sums of $x, y, z$, so by Vieta's formulas $x, y, z$ are the roots of $$t^3 - 7 t^2 - 14 t + 120 = 0.$$ By the rational root theorem, any rational root divides $120$. Testing $t = 5$: $125 - 175 - 70 + 120 = 0$, so $t = 5$ is a root. Factoring, $$t^3 - 7 t^2 - 14 t + 120 = (t - 5)(t^2 - 2 t - 24) = (t - 5)(t - 6)(t + 4).$$ Hence $\{x, y, z\} = \{5, 6, -4\}$. Since the three values are distinct and the system is symmetric, every ordering gives a valid solution, so there are $3! = \mathbf{6}$ ordered solutions $(x, y, z)$.

Multiply both sides by the common denominator $L = abc\,(a-b)(a-c)(b-c)$, which is nonzero. The identity is then equivalent to $f(c) = 0$, where $$f(c) = bc(b-c) - ac(a-c) + ab(a-b) - (a-b)(a-c)(b-c).$$

Regard $a, b$ as fixed and $f$ as a polynomial in $c$. Each term is at most quadratic in $c$, so $\deg f \leq 2$. We check that $f$ vanishes at three distinct points:

• $f(0) = ab(a-b) - (a-b)\,a\,b = 0$;
• $f(a) = ab(b-a) + ab(a-b) = 0$ (the other two terms carry a factor $a-a$);
• $f(b) = -ab(a-b) + ab(a-b) = 0$ (the other two terms carry a factor $b-b$).

A polynomial of degree at most $2$ with three distinct roots $c = 0, a, b$ is identically zero. Hence $f \equiv 0$, and dividing back by $L$ gives the identity.

Since the square of a real number is non-negative, $$0 \leq (a + b + c)^2 = a^2 + b^2 + c^2 + 2(ab + bc + ca) = 1 + 2(ab + bc + ca),$$ so $ab + bc + ca \geq -\frac{1}{2}$.

Equality holds when $a + b + c = 0$ together with $a^2 + b^2 + c^2 = 1$, for instance $a = \frac{1}{\sqrt 2}$, $b = -\frac{1}{\sqrt 2}$, $c = 0$. So the minimum value is $\mathbf{-\frac{1}{2}}$.

The coefficient matrix is $$M = \begin{pmatrix} n & 1 & 0 \\ 0 & n & 1 \\ 1 & 0 & n \end{pmatrix}, \qquad \det M = n^3 + 1.$$ If $\det M \neq 0$ the system has a unique solution. When $\det M = 0$ the system is not guaranteed to be solvable: it has either no solution or infinitely many. So the only candidate for "no solution" is $n^3 + 1 = 0$, i.e. (over the reals) $n = -1$, and we must check which case occurs there.

For $n = -1$ the system is $$-x + y = 1, \qquad -y + z = 1, \qquad x - z = 1.$$ Adding the three equations, the left side is $(-x+y) + (-y+z) + (x-z) = 0$, while the right side is $3$. This gives $0 = 3$, a contradiction, so the system is inconsistent.

Hence the system has no solution exactly when $\mathbf{n = -1}$.

Complete the square: $$x^2 + 2x + 2 = (x + 1)^2 + 1.$$ Since $(x+1)^2 \geq 0$, the expression is at least $1$, with equality at $x = -1$. So the minimum value is $\mathbf{1}$.

We use the single elementary fact that $e^{t} \geq 1 + t$ for all real $t$. To justify it, let $g(t) = e^t - 1 - t$. Then $g'(t) = e^t - 1$, which is negative for $t \lt 0$ and positive for $t \gt 0$, so $g$ is decreasing on $(-\infty, 0]$ and increasing on $[0, \infty)$. Thus $g$ attains its global minimum at $t = 0$, where $g(0) = 0$. Hence $g(t) \geq 0$, i.e. $e^t \geq 1 + t$, with equality only at $t = 0$. Replacing $t$ by $t - 1$, this reads $e^{\,t-1} \geq t$.

Let $A = \dfrac{a_1 + \cdots + a_n}{n}$ be the arithmetic mean. Apply the inequality with $t = \dfrac{a_i}{A}$ for each $i$: $$e^{\,a_i/A - 1} \geq \frac{a_i}{A}.$$ Multiplying these $n$ inequalities (all sides positive), $$\exp\!\left( \frac{a_1 + \cdots + a_n}{A} - n \right) \geq \frac{a_1 a_2 \cdots a_n}{A^n}.$$ Since $a_1 + \cdots + a_n = nA$, the exponent on the left is $n - n = 0$, so the left side is $e^0 = 1$. Hence $$a_1 a_2 \cdots a_n \leq A^n \implies \sqrt[n]{a_1 a_2 \cdots a_n} \leq A,$$ which is exactly the claim. Equality requires $e^{\,t-1} = t$ at each step, i.e. every $a_i/A = 1$, so all the $a_i$ are equal.

Apply AM–GM to the non-negative pairs $x^2, y^2$ etc. For any two reals, $$\frac{x^2 + y^2}{2} \geq \sqrt{x^2 y^2} = |xy| \geq xy, \qquad\text{so}\qquad x^2 + y^2 \geq 2xy.$$ Likewise $y^2 + z^2 \geq 2yz$ and $z^2 + x^2 \geq 2zx$. Adding the three inequalities, $$2(x^2 + y^2 + z^2) \geq 2(xy + yz + zx),$$ hence $x^2 + y^2 + z^2 \geq xy + yz + zx$, with equality if and only if $x = y = z$.

If every $a_i = 0$ both sides are $0$ and the inequality holds. Otherwise $\sum a_i^2 \gt 0$, and we consider the function $$f(t) = \sum_{i=1}^{n} (a_i t + b_i)^2 = \left( \sum a_i^2 \right) t^2 + 2 \left( \sum a_i b_i \right) t + \left( \sum b_i^2 \right).$$ Being a sum of squares, $f(t) \geq 0$ for every real $t$. So this quadratic in $t$ (with positive leading coefficient) has at most one real root, which forces its discriminant to be $\leq 0$: $$\left( 2 \sum a_i b_i \right)^2 - 4 \left( \sum a_i^2 \right) \left( \sum b_i^2 \right) \leq 0.$$ Dividing by $4$ rearranges to $$\left( \sum a_i b_i \right)^2 \leq \left( \sum a_i^2 \right) \left( \sum b_i^2 \right),$$ which is the inequality. Equality holds iff $f$ has a real root, i.e. $a_i t + b_i = 0$ for all $i$ at some $t$, meaning the vectors $(a_i)$ and $(b_i)$ are proportional.

Work backwards. Multiplying by $n \gt 0$, the claim is equivalent to $$n \left( 1^2 + 2^2 + \cdots + n^2 \right) \geq (1 + 2 + \cdots + n)^2.$$ Writing $n = 1^2 + 1^2 + \cdots + 1^2$, this reads $$\left( 1^2 + \cdots + n^2 \right)\left( 1^2 + \cdots + 1^2 \right) \geq (1\cdot 1 + \cdots + n \cdot 1)^2,$$ which is Cauchy–Schwarz with $a_k = k$, $b_k = 1$. As the steps are equivalences, the original holds.

By AM–GM, $$\frac{x + y + z}{3} \geq \sqrt[3]{xyz} = \sqrt[3]{27} = 3,$$ so $x + y + z \geq 9$, with equality when $x = y = z = 3$. The minimum value is $\mathbf{9}$.

Let the box have edge lengths $x, y, z \gt 0$. Covering it uses paper equal to its surface area, so $$2(xy + yz + zx) = 96 \implies xy + yz + zx = 48.$$ We maximize the volume $V = xyz$. By AM–GM applied to the three positive numbers $xy, yz, zx$, $$\frac{xy + yz + zx}{3} \geq \sqrt[3]{(xy)(yz)(zx)} = \sqrt[3]{(xyz)^2},$$ so $16 \geq (xyz)^{2/3}$, giving $xyz \leq 16^{3/2} = 64$.

Equality holds when $xy = yz = zx$, i.e. $x = y = z$; then $6x^2 = 96$ gives $x = 4$ (a cube). The largest box has volume $\mathbf{64}$ cubic meters.

Method 1 (average bound): Since the smaller of two numbers is at most their average, $$\min(x, y) \leq \frac{x + y}{2} = 2,$$ with equality precisely when $x = y$, i.e. $x = y = 2$. So the maximum value of $\min(x, y)$ is $\mathbf{2}$.

Method 2 (order the variables): Without loss of generality, assume $x \geq y$, so $\min(x, y) = y$. Then $x + y \geq 2y$, i.e. $4 \geq 2y$, giving $y \leq 2$. So $\min(x, y) \leq 2$, with equality when $x = y = 2$, and the maximum is $\mathbf{2}$.

By the Cauchy–Schwarz inequality with $b_i = 1$ for all $i$, $$\left( \sum_{i=1}^{n} a_i \right)^2 = \left( \sum_{i=1}^{n} a_i \cdot 1 \right)^2 \leq \left( \sum_{i=1}^{n} a_i^2 \right) \left( \sum_{i=1}^{n} 1^2 \right) = n \sum_{i=1}^{n} a_i^2.$$ Dividing by $n^2$ gives $$\left( \frac{a_1 + \cdots + a_n}{n} \right)^2 \leq \frac{a_1^2 + \cdots + a_n^2}{n}.$$ The right-hand side is non-negative, so taking square roots, $$\frac{a_1 + \cdots + a_n}{n} \leq \left| \frac{a_1 + \cdots + a_n}{n} \right| \leq \sqrt{\frac{a_1^2 + \cdots + a_n^2}{n}},$$ which is the claim. Equality requires the Cauchy–Schwarz vectors to be proportional, i.e. all the $a_i$ equal, and the arithmetic mean to be non-negative.

Apply AM–GM to the positive reals $\frac{1}{a_1}, \ldots, \frac{1}{a_n}$: $$\frac{\frac{1}{a_1} + \cdots + \frac{1}{a_n}}{n} \geq \sqrt[n]{\frac{1}{a_1} \cdots \frac{1}{a_n}} = \frac{1}{\sqrt[n]{a_1 \cdots a_n}}.$$ Both sides are positive, so taking reciprocals reverses the inequality: $$\frac{n}{\frac{1}{a_1} + \cdots + \frac{1}{a_n}} \leq \sqrt[n]{a_1 \cdots a_n},$$ which is exactly $\mathrm{HM} \leq \mathrm{GM}$. Equality holds iff all the $\frac{1}{a_i}$ are equal, i.e. all the $a_i$ are equal.

Method 1 (AM–GM): Expand using the constraint: $$(x + y)^2 = x^2 + 2xy + y^2 = 1 + 2xy.$$ Since $x^2 + y^2 \geq 2xy$ for all reals (it rearranges to $(x - y)^2 \geq 0$), we have $2xy \leq x^2 + y^2 = 1$, so $$(x + y)^2 = 1 + 2xy \leq 2.$$ Equality requires $x = y$; combined with $x^2 + y^2 = 1$ this gives $x = y = \pm\frac{1}{\sqrt 2}$. The maximum value is $\mathbf{2}$.

Method 2 (trigonometry): Since $x^2 + y^2 = 1$, write $x = \cos\theta$, $y = \sin\theta$. Then $$(x + y)^2 = (\cos\theta + \sin\theta)^2 = 1 + 2\sin\theta\cos\theta = 1 + \sin 2\theta.$$ Since $\sin 2\theta \leq 1$, we get $(x + y)^2 \leq 2$, with equality when $\sin 2\theta = 1$, i.e. $\theta = \frac{\pi}{4}$ (so $x = y = \frac{1}{\sqrt 2}$) or $\theta = \frac{5\pi}{4}$ (so $x = y = -\frac{1}{\sqrt 2}$). The maximum value is $\mathbf{2}$.

It suffices to exhibit a family of valid $(x, y, z)$ on which the minimum grows without bound. For a parameter $n \gt 1$, take $$x = y = n, \qquad z = \frac{1}{n^2},$$ which is positive and satisfies $xyz = n \cdot n \cdot \frac{1}{n^2} = 1$.

The three pairwise sums are $$x + y = 2n, \qquad x + z = y + z = n + \frac{1}{n^2}.$$ For $n \gt 1$ we have $\frac{1}{n^2} \lt n$, so $n + \frac{1}{n^2} \lt 2n$, and therefore $$\min(x + y, \, x + z, \, y + z) = n + \frac{1}{n^2} \gt n.$$ As $n \to \infty$ this exceeds any fixed bound, so $\min(x + y, x + z, y + z)$ is unbounded above and has no maximum.

Method 1 (sum of the pairwise sums): Write $M = \max(x + y, \, x + z, \, y + z)$. Each of the three pairwise sums is at most $M$, and adding them gives $$2(x + y + z) = (x + y) + (x + z) + (y + z) \leq 3M,$$ so $M \geq \frac{2}{3}(x + y + z)$.

By AM–GM, $x + y + z \geq 3\sqrt[3]{xyz} = 3$, hence $$M \geq \frac{2}{3} \cdot 3 = 2.$$ So no triple makes the maximum smaller than $2$. The value $2$ is attained at $x = y = z = 1$ (where $xyz = 1$ and all three pairwise sums equal $2$), so the minimum of $\max(x + y, x + z, y + z)$ is exactly $\mathbf{2}$.

Method 2 (order the variables): Without loss of generality, assume $x \leq y \leq z$. Then the largest pairwise sum is the sum of the two largest variables, so $M = y + z$.

Since $x$ is the smallest, $x \leq 1$: otherwise $x \gt 1$ would force $y, z \gt 1$ as well, giving $xyz \gt 1$, a contradiction. By AM–GM, $x + y + z \geq 3\sqrt[3]{xyz} = 3$, so $$M = y + z = (x + y + z) - x \geq 3 - x \geq 2,$$ with equality at $x = y = z = 1$. Hence the minimum is $\mathbf{2}$.

Without loss of generality, assume $x \leq y \leq z$. Then the smallest pairwise product is that of the two smallest variables, so $\min(xy, xz, yz) = xy$.

Since $z$ is the largest, $z \geq 1$ (the largest of three numbers averaging $1$), so $x + y = 3 - z \leq 2$. By AM–GM, $$xy \leq \left(\frac{x + y}{2}\right)^2 \leq 1,$$ with equality at $x = y = z = 1$. Hence the maximum is $\mathbf{1}$.

Apply AM–GM to the two non-negative numbers $2ab$ and $a^2 + b^2$: $$\sqrt{2ab(a^2 + b^2)} \leq \frac{2ab + (a^2 + b^2)}{2} = \frac{(a + b)^2}{2},$$ which is the claim. Equality holds when $2ab = a^2 + b^2$, i.e. $a = b$.

The $n$ numbers $x + r_1, \ldots, x + r_n$ are positive, so AM–GM applies: $$\sqrt[n]{(x + r_1)(x + r_2) \cdots (x + r_n)} \leq \frac{(x + r_1) + (x + r_2) + \cdots + (x + r_n)}{n} = x + \frac{r_1 + \cdots + r_n}{n}.$$ Raising both sides to the $n$-th power gives the claim. Equality holds when all the $x + r_i$ are equal, i.e. all the $r_i$ are equal.

Let the roots be $p, q, r \geq 0$. By Vieta's formulas, $$p + q + r = 12, \qquad pq + qr + rp = a, \qquad pqr = 64.$$ By AM–GM, $$\frac{p + q + r}{3} \geq \sqrt[3]{pqr} \quad\Longrightarrow\quad 4 \geq \sqrt[3]{64} = 4.$$ Equality holds, which forces $p = q = r = 4$. Therefore $$a = pq + qr + rp = 3 \cdot 16 = \mathbf{48}.$$

Raising both sides to the $2n$-th power, the claim is equivalent to $n^n \leq (n!)^2$. Write $$(n!)^2 = \prod_{k=1}^{n} k \cdot \prod_{k=1}^{n} (n + 1 - k) = \prod_{k=1}^{n} k(n + 1 - k),$$ where the second product just runs over the same factors in reverse order. For each $k$ with $1 \leq k \leq n$, $$k(n + 1 - k) - n = (k - 1)(n - k) \geq 0,$$ so $k(n + 1 - k) \geq n$. Multiplying these $n$ inequalities gives $(n!)^2 \geq n^n$, which is the claim.

Count pairs $(A, B)$ with $A \subseteq B \subseteq \{1, \ldots, n\}$, $|B| = k$, $|A| = m$ in two ways.

Picking $B$ then $A$: $\binom{n}{k}$ ways for $B$, then $\binom{k}{m}$ for $A$ inside $B$.

Picking $A$ then $B$: $\binom{n}{m}$ ways for $A$, then $\binom{n - m}{k - m}$ for the remaining elements of $B$, chosen from outside $A$.

Let $S = \sum_{k=0}^{n} k\binom{n}{k}$. Using $\binom{n}{k} = \binom{n}{n-k}$ and reindexing, write the same sum in reverse: $$S = \sum_{k=0}^{n} (n - k)\binom{n}{n - k} = \sum_{k=0}^{n} (n - k)\binom{n}{k}.$$ Adding the two expressions for $S$, $$2S = \sum_{k=0}^{n} \big(k + (n - k)\big)\binom{n}{k} = n \sum_{k=0}^{n} \binom{n}{k} = n \cdot 2^n,$$ so $S = n \cdot 2^{n-1}$.

Count the ways to choose an $n$-element committee from a group of $n$ men and $n$ women, which is $\binom{2n}{n}$.

Split by the number $k$ of men chosen: pick $k$ of the $n$ men in $\binom{n}{k}$ ways and $n - k$ of the $n$ women in $\binom{n}{n - k} = \binom{n}{k}$ ways, giving $\binom{n}{k}^2$ committees. Summing over $k$ from $0$ to $n$ counts every committee once, so $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$.

The general term is $$\binom{6}{k}(x^2)^{6 - k}\left(\frac{1}{x}\right)^k = \binom{6}{k} x^{12 - 3k}.$$ The exponent vanishes when $12 - 3k = 0$, i.e. $k = 4$, giving the constant term $\binom{6}{4} = \mathbf{15}$.

The exponents $2 + 3 + 1 + 4 = 10$ match the power, so the coefficient is the multinomial coefficient $$\binom{10}{2,\,3,\,1,\,4} = \frac{10!}{2!\,3!\,1!\,4!} = \mathbf{12600}.$$

$$(x + y + z)^n = \sum_{\substack{i + j + k = n \\ i,\, j,\, k \geq 0}} \frac{n!}{i!\,j!\,k!}\, x^i y^j z^k,$$ where the sum runs over all non-negative integer triples $(i, j, k)$ with $i + j + k = n$.

Count the $m$-element subsets of an $(n + m)$-element set partitioned into a part $X$ of size $n$ and a part $Y$ of size $m$. There are $\binom{n + m}{m} = \binom{n + m}{n}$ of them.

Split by the number $k$ of elements taken from $X$: pick $k$ from $X$ in $\binom{n}{k}$ ways and the remaining $m - k$ from $Y$ in $\binom{m}{m - k} = \binom{m}{k}$ ways, giving $\binom{n}{k}\binom{m}{k}$ subsets. Summing over $k$ counts every $m$-subset once.

The inner sum is $\sum_{k=1}^{i} \binom{i}{k} = 2^i - \binom{i}{0} = 2^i - 1$. Therefore $$\sum_{i=1}^{10} (2^i - 1) = \sum_{i=1}^{10} 2^i - 10 = (2^{11} - 2) - 10 = 2046 - 10 = \mathbf{2036}.$$

Start from the right-hand side and repeatedly apply Pascal's rule $\binom{m}{j} = \binom{m - 1}{j} + \binom{m - 1}{j - 1}$, each time splitting off one term of the sum: $$\binom{n + k + 1}{k + 1} = \binom{n + k}{k + 1} + \binom{n + k}{k} = \binom{n + k}{k + 1} + \binom{n + k - 1}{k} + \binom{n + k - 1}{k - 1} = \cdots$$ Splitting the rightmost binomial each step peels off the terms $\binom{n + k}{k + 1}, \binom{n + k - 1}{k}, \ldots, \binom{n}{1}$ in turn, and the last remainder is $\binom{n}{0} = \binom{n - 1}{0}$. Collecting these is exactly the left-hand side.

Alternative proof by counting subsets. The right-hand side $\binom{n + k + 1}{k + 1} = \binom{n + k + 1}{n}$ counts the $n$-element subsets of $\{1, 2, \ldots, n + k + 1\}$. Classify each subset by its largest element $m$: the other $n - 1$ elements lie in $\{1, \ldots, m - 1\}$, giving $\binom{m - 1}{n - 1}$ subsets, and $m$ ranges from $n$ to $n + k + 1$. Writing $m = n + j$ for $j = 0, \ldots, k + 1$, this term is $\binom{n - 1 + j}{n - 1} = \binom{n - 1 + j}{j}$, the $j$-th term of the left-hand side. Summing over $m$ counts every subset once.

The sum of the coefficients is the value of the expansion at $a = b = c = d = 1$, namely $(1 + 1 + 1 + 1)^{10} = \mathbf{4^{10}}$.

The sum is $\sum_{k \text{ odd}} k\binom{n}{k}$. Using the absorption identity $k\binom{n}{k} = n\binom{n - 1}{k - 1}$, $$\sum_{k \text{ odd}} k\binom{n}{k} = n \sum_{k \text{ odd}} \binom{n - 1}{k - 1} = n \sum_{j \text{ even}} \binom{n - 1}{j}.$$ The even-indexed binomial coefficients of any positive integer $m$ sum to $2^{m - 1}$; with $m = n - 1$ this gives $\mathbf{n \cdot 2^{n-2}}$.

Alternative proof. Let $S_{\text{odd}} = \sum_{k \text{ odd}} k\binom{n}{k}$ and $S_{\text{even}} = \sum_{k \text{ even}} k\binom{n}{k}$. From the earlier identity $\sum_{k} k\binom{n}{k} = n \cdot 2^{n-1}$, $$S_{\text{odd}} + S_{\text{even}} = n \cdot 2^{n-1}.$$ For the difference, use $k\binom{n}{k} = n\binom{n - 1}{k - 1}$: $$S_{\text{even}} - S_{\text{odd}} = \sum_{k} (-1)^k\, k\binom{n}{k} = n \sum_{k} (-1)^k \binom{n - 1}{k - 1} = -n\,(1 - 1)^{n-1} = 0$$ for $n \geq 2$. Hence $S_{\text{odd}} = S_{\text{even}}$, and adding the two relations gives $S_{\text{odd}} = n \cdot 2^{n-2}$.

Count the $(n + 1)$-element subsets of a set split into two parts $X$ and $Y$ of size $n$ each, of which there are $\binom{2n}{n + 1}$. Splitting by the number $k$ of elements taken from $X$: pick $k$ from $X$ in $\binom{n}{k}$ ways and the remaining $n + 1 - k$ from $Y$ in $\binom{n}{n + 1 - k} = \binom{n}{k - 1}$ ways. Summing over $k$ gives $$\sum_{k=1}^{n} \binom{n}{k}\binom{n}{k - 1} = \binom{2n}{n + 1}.$$

Both sides count the pairs $(A, B)$ with $A \subseteq B \subseteq \{1, \ldots, n\}$ and $|B| = m$.

Picking $A$ then $B$: choose $A$ of size $k$ in $\binom{n}{k}$ ways, then the remaining $m - k$ elements of $B$ from the $n - k$ elements outside $A$ in $\binom{n - k}{m - k}$ ways. Summing over $k = 0, \ldots, m$ gives the left-hand side.

Picking $B$ then $A$: choose the $m$-element set $B$ in $\binom{n}{m}$ ways, then any subset $A \subseteq B$ in $2^m$ ways, giving the right-hand side.

Split the sum with $k^2 = k(k - 1) + k$: $$\sum_{k=1}^{n} k^2 = \sum_{k=1}^{n} k(k - 1) + \sum_{k=1}^{n} k.$$ Since $k(k - 1) = 2\binom{k}{2}$, the hockey-stick identity $\sum_{i=r}^{n} \binom{i}{r} = \binom{n + 1}{r + 1}$ gives $\sum_{k=1}^{n} k(k - 1) = 2\sum_{k=1}^{n} \binom{k}{2} = 2\binom{n + 1}{3}$, and $\sum_{k=1}^{n} k = \binom{n + 1}{2}$. Therefore $$\sum_{k=1}^{n} k^2 = 2\binom{n + 1}{3} + \binom{n + 1}{2} = \frac{n(n + 1)(2n + 1)}{6}.$$

Factor the denominator as $x^2 - 4x + 3 = (x - 1)(x - 3)$ and write $$\frac{2x - 1}{(x - 1)(x - 3)} = \frac{A}{x - 1} + \frac{B}{x - 3}, \qquad 2x - 1 = A(x - 3) + B(x - 1).$$ Setting $x = 1$ gives $1 = -2A$, so $A = -\frac{1}{2}$; setting $x = 3$ gives $5 = 2B$, so $B = \frac{5}{2}$. Therefore $$\frac{2x - 1}{x^2 - 4x + 3} = -\frac{1}{2(x - 1)} + \frac{5}{2(x - 3)}.$$

Write $n = (n+1) - 1$ in the numerator: $$\frac{n}{(n+1)(n+2)} = \frac{(n+1) - 1}{(n+1)(n+2)} = \frac{1}{n+2} - \frac{1}{(n+1)(n+2)}.$$ The second piece telescopes: $\dfrac{1}{(n+1)(n+2)} = \dfrac{1}{n+1} - \dfrac{1}{n+2}$, so $\displaystyle\sum_{n=1}^{\infty} \frac{1}{(n+1)(n+2)} = \frac{1}{2}$ converges. The first piece $\displaystyle\sum_{n=1}^{\infty} \frac{1}{n+2}$ is a tail of the harmonic series, which diverges. A convergent series minus a divergent one diverges, so the sum diverges.

Let $S = \displaystyle\sum_{n=1}^{\infty} \frac{2n}{3^{n+1}}$ and subtract a shifted copy: $$S = \frac{2}{3^2} + \frac{4}{3^3} + \frac{6}{3^4} + \cdots, \qquad \frac{S}{3} = \frac{2}{3^3} + \frac{4}{3^4} + \cdots.$$ Subtracting term by term, each numerator difference is $2$: $$S - \frac{S}{3} = \frac{2}{3^2} + \frac{2}{3^3} + \frac{2}{3^4} + \cdots = 2\sum_{k=2}^{\infty} \frac{1}{3^k} = 2 \cdot \frac{1/9}{1 - 1/3} = \frac{1}{3}.$$ Thus $\dfrac{2}{3}S = \dfrac{1}{3}$, giving $S = \dfrac{1}{2}$.

The powers of $i$ repeat with period $4$: $i^0 = 1$, $i^1 = i$, $i^2 = -1$, $i^3 = -i$. Group the terms into blocks of four starting at $k = 4m$. Using $i^{4m} = 1$, the block is $$(4m+1) + (4m+2)i - (4m+3) - (4m+4)i = -2 - 2i,$$ the same constant for every block. Since $n$ is a multiple of $4$, the terms $k = 0, \ldots, n-1$ form exactly $\frac{n}{4}$ complete blocks, leaving the final term $(n+1)i^n = n+1$. Therefore $$S = \frac{n}{4}(-2 - 2i) + (n+1) = \frac{(n+2) - ni}{2}.$$

Summing the recurrence from $1$ to $n-1$ telescopes: $$a_n = a_1 + \sum_{k=1}^{n-1} 2k = 2 + (n-1)n = n^2 - n + 2.$$ Hence $a_{100} = 100^2 - 100 + 2 = 9902$.

A purchase is determined by how many of each type we take: nonnegative integers $x_1, x_2, \ldots, x_r$ with $$x_1 + x_2 + \cdots + x_r = n.$$ Encode such a solution as a row of $n$ stars and $r - 1$ bars: the stars before the first bar give $x_1$, those between the first and second bar give $x_2$, and so on. Every arrangement of $n$ stars and $r - 1$ bars corresponds to exactly one solution and vice versa. There are $n + r - 1$ symbols, and a purchase is fixed by choosing which $r - 1$ of them are bars, so the number of ways is $$\binom{n + r - 1}{r - 1} = \binom{n + r - 1}{n}.$$

Represent a solution by $n$ stars split into $r$ groups by $r - 1$ bars, where the number of stars in the $i$-th group is $x_i$: $$\underbrace{\star\cdots\star}_{x_1}\;\big|\;\underbrace{\star\cdots\star}_{x_2}\;\big|\;\cdots\;\big|\;\underbrace{\star\cdots\star}_{x_r}.$$ Each arrangement of the $n + r - 1$ symbols gives exactly one solution, so the count is the number of ways to place the $r - 1$ bars among the $n + r - 1$ positions: $$\binom{n + r - 1}{r - 1} = \binom{n + r - 1}{n}.$$

First choose the $5$ occupied chairs so that no two are adjacent, then seat the $5$ distinct people in them. Line up the $15$ empty chairs; they create $16$ gaps (one before each empty chair, one after the last) into which the occupied chairs may be inserted. Choosing $5$ of these gaps, at most one per gap, guarantees no two occupied chairs are adjacent, so there are $\binom{16}{5}$ valid sets of chairs. The $5$ people can then be arranged in $5!$ ways, giving $$\binom{16}{5}\cdot 5!.$$