Maths Olympiad Prep

Library / /24 of 42

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 k1k \ge 1 and all 1MN1 \le M \le N we have
n=MN1n(n+k)<1kn=MM+k11n. \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(1n1n+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)=1kn=MN(1n1n+k)=1kn=MM+k11n1kn=N+1N+k1n<1kn=MM+k11n. \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 MNk+1M \le N-k+1 the terms 1/n1/n for M+knNM+k \le n \le N cancel out as they appear in both sums. When N<M+k1N < 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=1n=MN1n(n+1)<1M(17) k = 1 \qquad \sum_{n=M}^{N} \frac{1}{n(n+1)} < \frac{1}{M} \qquad (17)
M=1n=1N1n(n+k)<1kn=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+11nm=n1N1m(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=n1M = n - 1 we obtain
m=1N1m(m+1)<1andm=n1N1m(m+1)<1n1. \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(n1)=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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.