Putnam 2020, Problem A-6

For a positive integer \( N \), let \( f_N \) be the function defined by
\[
f_N(x) = \sum_{n=0}^{N} \frac{N + 1/2 - n}{(N + 1)(2n + 1)} \sin((2n + 1)x).
\]
Determine the smallest constant \( M \) such that \( f_N(x) \leq M \) for all \( N \) and all real \( x \).

Solution:
The smallest constant $M$ is $\pi/4$.

We start from the expression
$$f_N(x) = \sum_{n=0}^N \frac{1}{2} \left( \frac{2}{2n+1} - \frac{1}{N+1} \right) \sin((2n+1)x). \tag{8}$$

Note that if $\sin(x) > 0$, then
$$\sum_{n=0}^N \sin((2n+1)x) = \frac{1}{2i} \sum_{n=0}^N \left( e^{i(2n+1)x} - e^{-i(2n+1)x} \right)$$
$$= \frac{1}{2i} \left( \frac{e^{i(2N+3)x} - e^{ix}}{e^{2ix} - 1} - \frac{e^{-i(2N+3)x} - e^{-ix}}{e^{-2ix} - 1} \right)$$
$$= \frac{1}{2i} \left( \frac{e^{i(2N+2)x} - 1}{e^{ix} - e^{-ix}} - \frac{e^{-i(2N+2)x} - 1}{e^{-ix} - e^{ix}} \right)$$
$$= \frac{e^{i(2N+2)x} + e^{-i(2N+2)x} - 2}{2i(e^{ix} - e^{-ix})}$$
$$= \frac{2\cos((2N+2)x) - 2}{2i(2i \sin(x))}$$
$$= \frac{1 - \cos((2N+2)x)}{2 \sin(x)} \geq 0.$$

We use this to compare the expressions of $f_N(x)$ and $f_{N+1}(x)$ given by (8). For $x \in (0,\pi)$ with $\sin((2N+3)x) \geq 0$, we may omit the summand $n = N+1$ from $f_{N+1}(x)$ to obtain
$$f_{N+1}(x) - f_N(x)$$
$$\geq \frac{1}{2} \left( \frac{1}{N+1} - \frac{1}{N+2} \right) \sum_{n=0}^N \sin((2n+1)x) \geq 0.$$

For $x \in (0,\pi)$ with $\sin((2N+3)x) \leq 0$, we may insert the summand $n = N+1$ into $f_{N+1}(x)$ to obtain
$$f_{N+1}(x) - f_N(x)$$
$$\geq \frac{1}{2} \left( \frac{1}{N+1} - \frac{1}{N+2} \right) \sum_{n=0}^{N+1} \sin((2n+1)x) \geq 0.$$

In either case, we deduce that for $x \in (0,\pi)$, the sequence $\{f_N(x)\}_N$ is nondecreasing.

Now rewrite (8) as
$$f_N(x) = \sum_{n=0}^N \frac{\sin((2n+1)x)}{2n+1} - \frac{1 - \cos((2N+2)x)}{4(N+1) \sin(x)} \tag{9}$$

and note that the last term tends to $0$ as $N \to \infty$. Consequently, $\lim_{N \to \infty} f_N(x)$ equals the sum of the series
$$\sum_{n=0}^\infty \frac{1}{2n+1} \sin((2n+1)x),$$

which is the Fourier series for the "square wave" function defined on $(-\pi,\pi]$ by
$$x \mapsto \begin{cases} -\pi/4 & x \in (-\pi,0) \\ \pi/4 & x \in (0,\pi) \\ 0 & x = 0,\pi \end{cases}$$

and extended periodically. Since this function is continuous on $(0,\pi)$, we deduce that the Fourier series converges to the value of the function; that is,
$$\lim_{N \to \infty} f_N(x) = \frac{\pi}{4} \quad (x \in (0,\pi)).$$

This is enough to deduce the desired result as follows. Since
$$f_N(x+2\pi) = f_N(x), \quad f_N(-x) = -f_N(x),$$

it suffices to check the bound $f_N(x) \leq \pi$ for $x \in (-\pi,\pi]$. For $x = 0,\pi$ we have $f_N(x) = 0$ for all $N$. For $x \in (-\pi,0)$, the previous arguments imply that
$$0 \geq f_0(x) \geq f_1(x) \geq \cdots$$

For $x \in (0,\pi)$, the previous arguments imply that
$$0 \leq f_0(x) \leq f_1(x) \leq \cdots \leq \frac{\pi}{4}$$

and the limit is equal to $\pi/4$. We conclude that $f_N(x) \leq M$ holds for $M = \pi/4$ but not for any smaller $M$, as desired.

**Remark.** It is also possible to replace the use of the convergence of the Fourier series with a more direct argument; it is sufficient to do this for $x$ in a dense subset of $(0,\pi)$, such as the rational multiples of $\pi$.

Another alternative (described at https://how-did-i-get-here.com/2020-putnam-a6/) is to deduce from (9) and a second geometric series computation (omitted here) that
$$f_N'(x) = \sum_{n=0}^N \cos((2n+1)x) - \frac{d}{dx} \left( \frac{1 - \cos((2N+2)x)}{4(N+1) \sin(x)} \right)$$
$$= \frac{\sin((2N+2)x)}{2 \sin(x)}$$
$$- \frac{(2N+2) \sin((2N+2)x) - \cos(x)(1 - \cos((N+2)x))}{4(N+1) \sin(x)^2}$$
$$= \frac{\cos(x)(1 - \cos((N+2)x))}{4(N+1) \sin(x)^2},$$

which is nonnegative for $x \in (0,\pi/2]$ and nonpositive for $x \in [\pi/2,\pi)$. This implies that $f_N(x)$ always has a global maximum at $x = \pi/2$, so it suffices to check the convergence of the Fourier series for the square wave at that point. This reduces to the Madhava-Gregory-Newton series evaluation
$$1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots = \arctan(1) = \frac{\pi}{4}.$$