Maths Olympiad Prep

Library / IRL ABooklet /92 of 191

IRL ABooklet

Algebra Difficulty 5.9 AIME, harder Prove it Ireland

Prove that the sum of the elements in any finite subset of the set
{1mn(m+n+1):m,n=1,2,3,… } \left\{ \frac{1}{mn(m+n+1)} : m, n = 1, 2, 3, \dots \right\}
is less than 2.

Solution

We will use the following lemma three times.
Lemma. For all k≥1k \ge 1 and all 1≤M≤N1 \le M \le N we have
∑n=MN1n(n+k)<1k∑n=MM+k−11n. \sum_{n=M}^{N} \frac{1}{n(n+k)} < \frac{1}{k} \sum_{n=M}^{M+k-1} \frac{1}{n} .
Proof. Using 1n(n+k)=1k(1n−1n+k)\frac{1}{n(n+k)} = \frac{1}{k} \left( \frac{1}{n} - \frac{1}{n+k} \right) we see that
∑n=MN1n(n+k)=1k∑n=MN(1n−1n+k)=1k∑n=MM+k−11n−1k∑n=N+1N+k1n<1k∑n=MM+k−11n. \begin{align*} \sum_{n=M}^{N} \frac{1}{n(n+k)} &= \frac{1}{k} \sum_{n=M}^{N} \left( \frac{1}{n} - \frac{1}{n+k} \right) \\ &= \frac{1}{k} \sum_{n=M}^{M+k-1} \frac{1}{n} - \frac{1}{k} \sum_{n=N+1}^{N+k} \frac{1}{n} \\ &< \frac{1}{k} \sum_{n=M}^{M+k-1} \frac{1}{n} . \end{align*}
If M≤N−k+1M \le N-k+1 the terms 1/n1/n for M+k≤n≤NM+k \le n \le N cancel out as they appear in both sums. When N<M+k−1N < M+k-1, we have introduced extra terms which appear in both sums. In this case, the sum on the right hand side would only need to go up to n=Nn=N, but we do not need this stronger inequality. □\square

We will use this lemma in two special cases:
k=1∑n=MN1n(n+1)<1M(17) k = 1 \qquad \sum_{n=M}^{N} \frac{1}{n(n+1)} < \frac{1}{M} \qquad (17)
M=1∑n=1N1n(n+k)<1k∑n=1k1n(18) M = 1 \qquad \sum_{n=1}^{N} \frac{1}{n(n+k)} < \frac{1}{k} \sum_{n=1}^{k} \frac{1}{n} \qquad (18)

Let now SS be a sum of a finite number of terms of the form 1mn(m+n+1)\frac{1}{mn(m+n+1)}.
Let NN be such that no term with n>Nn > N or with m>Nm > N appears in SS. For fixed mm we obtain from (18) with k=m+1k = m + 1
∑n=1N1mn(m+n+1)<1m(m+1)∑n=1m+11n. \sum_{n=1}^{N} \frac{1}{mn(m+n+1)} < \frac{1}{m(m+1)} \sum_{n=1}^{m+1} \frac{1}{n} .
Hence
S<∑m=1N1m(m+1)∑n=1m+11n. S < \sum_{m=1}^{N} \frac{1}{m(m+1)} \sum_{n=1}^{m+1} \frac{1}{n} .

Instead of summing by row, we can first add along the columns. This gives
∑m=1N1m(m+1)∑n=1m+11n=∑m=1N1m(m+1)+∑n=2N+11n∑m=n−1N1m(m+1). \sum_{m=1}^{N} \frac{1}{m(m+1)} \sum_{n=1}^{m+1} \frac{1}{n} = \sum_{m=1}^{N} \frac{1}{m(m+1)} + \sum_{n=2}^{N+1} \frac{1}{n} \sum_{m=n-1}^{N} \frac{1}{m(m+1)}.
From (17) with M=1M = 1 and with M=n−1M = n - 1 we obtain
∑m=1N1m(m+1)<1and∑m=n−1N1m(m+1)<1n−1. \sum_{m=1}^{N} \frac{1}{m(m+1)} < 1 \quad \text{and} \quad \sum_{m=n-1}^{N} \frac{1}{m(m+1)} < \frac{1}{n-1}.
Hence, S<1+∑n=2N+11n(n−1)=1+∑n=1N1n(n+1)<2S < 1 + \sum_{n=2}^{N+1} \frac{1}{n(n-1)} = 1 + \sum_{n=1}^{N} \frac{1}{n(n+1)} < 2 by (17) with M=1M = 1.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.