๐Ÿงฎ Brain Teaser

Sum of Squares Under a Linear Constraint

Let AA be a positive real number. What are the possible values of โˆ‘j=0โˆžxj2,\sum_{j=0}^{\infty} x_j^2, given that x0,x1,x2,โ€ฆx_0, x_1, x_2, \ldots are positive real numbers satisfying โˆ‘j=0โˆžxj=A?\sum_{j=0}^{\infty} x_j = A?

infinite seriesoptimizationinequalitiesPutnam 2000

Answer: Sum of Squares Under a Linear Constraint

Key Idea / Intuition

The sum of squares can be made arbitrarily small by spreading the total weight AA over many terms (like equal slices), but it can never reach zero since all xj>0x_j > 0. On the upper end, concentrating nearly all weight in a single term pushes โˆ‘xj2\sum x_j^2 close to A2A^2, but strict positivity prevents it from actually reaching A2A^2. So the answer is the open interval (0,A2)(0, A^2).


Formal Proof / Solution

Step 1: Upper bound โ€” โˆ‘xj2<A2\sum x_j^2 < A^2.

By the Cauchyโ€“Schwarz inequality (or simply because all xj>0x_j > 0 and their sum is AA): โˆ‘j=0โˆžxj2โ‰ค(โˆ‘j=0โˆžxj)2=A2\sum_{j=0}^{\infty} x_j^2 \leq \left(\sum_{j=0}^{\infty} x_j\right)^2 = A^2 is not the right bound here. Let's think more carefully.

Since all xj>0x_j > 0 and โˆ‘xj=A\sum x_j = A, we have xj<Ax_j < A for every jj. Therefore: โˆ‘j=0โˆžxj2=โˆ‘j=0โˆžxjโ‹…xj<โˆ‘j=0โˆžxjโ‹…A=Aโ‹…A=A2.\sum_{j=0}^{\infty} x_j^2 = \sum_{j=0}^{\infty} x_j \cdot x_j < \sum_{j=0}^{\infty} x_j \cdot A = A \cdot A = A^2.

So โˆ‘xj2<A2\sum x_j^2 < A^2.

Step 2: Approaching A2A^2 โ€” the upper bound is tight.

Let x0=Aโˆ’ฯตโ‹…โˆ‘j=1โˆžrjx_0 = A - \epsilon \cdot \sum_{j=1}^\infty r^j and distribute the remaining weight ฯต\epsilon-small pieces geometrically. More directly: take x0=A(1โˆ’ฯต),xj=Aฯตโ‹…2โˆ’jย forย jโ‰ฅ1,x_0 = A(1-\epsilon), \quad x_j = A\epsilon \cdot 2^{-j} \text{ for } j \geq 1, so that โˆ‘xj=A(1โˆ’ฯต)+Aฯต=A\sum x_j = A(1-\epsilon) + A\epsilon = A. Then: โˆ‘xj2=A2(1โˆ’ฯต)2+A2ฯต2โˆ‘j=1โˆž4โˆ’j=A2(1โˆ’ฯต)2+A2ฯต23.\sum x_j^2 = A^2(1-\epsilon)^2 + A^2\epsilon^2\sum_{j=1}^\infty 4^{-j} = A^2(1-\epsilon)^2 + \frac{A^2\epsilon^2}{3}. As ฯตโ†’0+\epsilon \to 0^+, this approaches A2A^2. So A2A^2 is a supremum but is not achieved.

Step 3: Lower bound โ€” โˆ‘xj2>0\sum x_j^2 > 0.

Since each xj>0x_j > 0, clearly โˆ‘xj2>0\sum x_j^2 > 0.

Step 4: Approaching 00 โ€” the lower bound is tight.

Take xj=Anโ‹…1j<nx_j = \frac{A}{n} \cdot \mathbf{1}_{j < n} for large nn (i.e., equal weights on the first nn terms, tiny positive values for the rest โ€” but we need all xj>0x_j > 0).

More carefully: take xj=cโ‹…rjx_j = c \cdot r^j for 0<r<10 < r < 1, so โˆ‘xj=c1โˆ’r=A\sum x_j = \frac{c}{1-r} = A, meaning c=A(1โˆ’r)c = A(1-r). Then: โˆ‘xj2=c2โˆ‘r2j=c21โˆ’r2=A2(1โˆ’r)21โˆ’r2=A2(1โˆ’r)1+r.\sum x_j^2 = c^2 \sum r^{2j} = \frac{c^2}{1-r^2} = \frac{A^2(1-r)^2}{1-r^2} = \frac{A^2(1-r)}{1+r}. As rโ†’1โˆ’r \to 1^-, this approaches 00. So 00 is an infimum but is not achieved.

Step 5: All values in (0,A2)(0, A^2) are achieved.

The function rโ†ฆA2(1โˆ’r)1+rr \mapsto \frac{A^2(1-r)}{1+r} is continuous and maps (0,1)(0,1) onto (0,A2)(0, A^2) (it equals A2/3A^2/3 at r=1/2r=1/2, etc.). By the intermediate value theorem, every value in (0,A2)(0, A^2) is achieved.

Conclusion:

The set of possible values of โˆ‘j=0โˆžxj2\displaystyle\sum_{j=0}^{\infty} x_j^2 is exactly the open interval (0,โ€‰A2).\boxed{(0,\, A^2)}.

Source: Putnam 2000, Problem A-1

Type: PutnamSource: Putnam 2000, Problem A-1Edit on GitHub โ†—