Maths Olympiad Prep

Library / /33 of 42

Algebra Difficulty 6.8 National olympiad Prove it Ireland

Prove that any finite sum of terms
1abc(a+b+c+1) \frac{1}{abc(a + b + c + 1)}
where a,b,ca, b, c are positive integers, is smaller than 6.

Solution

We will use the following notation:
Hi=k=1i1kPi(m)=k=mNHk+ik(k+1). H_i = \sum_{k=1}^{i} \frac{1}{k} \qquad P_i(m) = \sum_{k=m}^{N} \frac{H_{k+i}}{k(k+1)}.
Lemma 1. For all i1i \ge 1 and all 1MN1 \le M \le N we have
k=MN1k(k+i)<1ik=MM+i11k. \sum_{k=M}^{N} \frac{1}{k(k+i)} < \frac{1}{i} \sum_{k=M}^{M+i-1} \frac{1}{k} .
Proof. Using 1k(k+i)=1i(1k1k+i)\frac{1}{k(k+i)} = \frac{1}{i}\left(\frac{1}{k} - \frac{1}{k+i}\right) we see that
k=MN1k(k+i)=1ik=MN(1k1k+i)=1ik=MM+i11k1ik=N+1N+i1k<1ik=MM+i11k. \sum_{k=M}^{N} \frac{1}{k(k + i)} = \frac{1}{i} \sum_{k=M}^{N} \left( \frac{1}{k} - \frac{1}{k + i} \right) = \frac{1}{i} \sum_{k=M}^{M+i-1} \frac{1}{k} - \frac{1}{i} \sum_{k=N+1}^{N+i} \frac{1}{k} < \frac{1}{i} \sum_{k=M}^{M+i-1} \frac{1}{k}.
If M+i1NM + i - 1 \le N the terms 1/k1/k for M+ikNM + i \le k \le N cancel out as they appear in both sums. When M+i1>NM + i - 1 > N, 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 k=Nk = N, but we don't need this stronger inequality. \square

i=2k=MN1k(k+2)<12M+12(M+1)(32) i = 2 \qquad \sum_{k=M}^{N} \frac{1}{k(k+2)} < \frac{1}{2M} + \frac{1}{2(M+1)} \qquad (32)
M=1k=1N1k(k+i)<1ik=1i1k=Hii(33)M = 1 \qquad \sum_{k=1}^{N} \frac{1}{k(k+i)} < \frac{1}{i} \sum_{k=1}^{i} \frac{1}{k} = \frac{H_i}{i} \qquad (33)

Lemma 2. For all N>m1N > m \ge 1 and i1i \ge 1 we have
Pi(m)<1mHm+i+1ik=m+1m+i1k. P_i(m) < \frac{1}{m} H_{m+i} + \frac{1}{i} \sum_{k=m+1}^{m+i} \frac{1}{k}.
Pi(m)=k=mNHk+ik(k+1)=k=mN(1k1k+1)Hk+i=k=mN1kHk+ik=m+1N+11kHk+i1=1mHm+i+k=m+1N1k(Hk+iHk+i1)1N+1HN+i<1mHm+i+k=m+1N1k(k+i)<1mHm+i+1ik=m+1m+i1kusing Lemma 1. \begin{align*} P_i(m) &= \sum_{k=m}^{N} \frac{H_{k+i}}{k(k+1)} \\ &= \sum_{k=m}^{N} \left( \frac{1}{k} - \frac{1}{k+1} \right) H_{k+i} = \sum_{k=m}^{N} \frac{1}{k} H_{k+i} - \sum_{k=m+1}^{N+1} \frac{1}{k} H_{k+i-1} \\ &= \frac{1}{m} H_{m+i} + \sum_{k=m+1}^{N} \frac{1}{k} (H_{k+i} - H_{k+i-1}) - \frac{1}{N+1} H_{N+i} \\ &< \frac{1}{m} H_{m+i} + \sum_{k=m+1}^{N} \frac{1}{k(k+i)} < \frac{1}{m} H_{m+i} + \frac{1}{i} \sum_{k=m+1}^{m+i} \frac{1}{k} \quad \text{using Lemma 1.} \end{align*}
\square
In particular, we obtain
P1(m)<1m+1+1mHm+1(34) P_1(m) < \frac{1}{m+1} + \frac{1}{m} H_{m+1} \qquad (34)
P2(m)<12(m+1)+12(m+2)+1mHm+2.(35) P_2(m) < \frac{1}{2(m+1)} + \frac{1}{2(m+2)} + \frac{1}{m} H_{m+2}. \quad (35)

S=a,b,c=1N1abc(a+b+c+1)=a,b=1N1abc=1N1c(a+b+c+1)<a,b=1NHa+b+1ab(a+b+1)using (33) with i=a+b+1=a,b=1Na+babHa+b+1(a+b)(a+b+1)=k=22Na+b=k(1a+1b)Hk+1k(k+1)=2k=22Nm=1k11mHk+1k(k+1).\begin{align*} S &= \sum_{a,b,c=1}^{N} \frac{1}{abc(a+b+c+1)} = \sum_{a,b=1}^{N} \frac{1}{ab} \sum_{c=1}^{N} \frac{1}{c(a+b+c+1)} \\ &< \sum_{a,b=1}^{N} \frac{H_{a+b+1}}{ab(a+b+1)} && \text{using (33) with } i = a+b+1 \\ &= \sum_{a,b=1}^{N} \frac{a+b}{ab} \cdot \frac{H_{a+b+1}}{(a+b)(a+b+1)} \\ &= \sum_{k=2}^{2N} \sum_{a+b=k} \left(\frac{1}{a} + \frac{1}{b}\right) \frac{H_{k+1}}{k(k+1)} = 2 \sum_{k=2}^{2N} \sum_{m=1}^{k-1} \frac{1}{m} \cdot \frac{H_{k+1}}{k(k+1)}. \end{align*}

\sum_{k=2}^{2N} \sum_{m=1}^{k-1} \frac{1}{m} \cdot \frac{H_{k+1}}{k(k+1)} = \sum_{m=1}^{2N-1} \frac{1}{m} \sum_{k=m+1}^{2N} \frac{H_{k+1}}{k(k+1)}.
Therefore, Therefore,
S<2m=12N11mk=m+12NHk+1k(k+1)=2m=12N11mP1(m+1)<2m=12N11m(1m+2+1m+1Hm+2)using (34)=2m=12N11m(m+2)+2m=12N1Hm+2m(m+1)=2m=12N11m(m+2)+2P2(1)<1+12+2(14+16+H3)=6.using (32) and (35).\begin{align*} S < 2 \sum_{m=1}^{2N-1} \frac{1}{m} \sum_{k=m+1}^{2N} \frac{H_{k+1}}{k(k+1)} &= 2 \sum_{m=1}^{2N-1} \frac{1}{m} P_1(m+1) \\ &< 2 \sum_{m=1}^{2N-1} \frac{1}{m} \left( \frac{1}{m+2} + \frac{1}{m+1} H_{m+2} \right) && \text{using (34)} \\ &= 2 \sum_{m=1}^{2N-1} \frac{1}{m(m+2)} + 2 \sum_{m=1}^{2N-1} \frac{H_{m+2}}{m(m+1)} \\ &= 2 \sum_{m=1}^{2N-1} \frac{1}{m(m+2)} + 2P_2(1) \\ &< 1 + \frac{1}{2} + 2 \left( \frac{1}{4} + \frac{1}{6} + H_3 \right) = 6. && \text{using (32) and (35).} \end{align*}

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.