Maths Olympiad Prep

Library / IRL ABooklet /152 of 191

IRL ABooklet

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 i≥1i \ge 1 and all 1≤M≤N1 \le M \le N we have
∑k=MN1k(k+i)<1i∑k=MM+i−11k. \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(1k−1k+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)=1i∑k=MN(1k−1k+i)=1i∑k=MM+i−11k−1i∑k=N+1N+i1k<1i∑k=MM+i−11k. \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+i−1≤NM + i - 1 \le N the terms 1/k1/k for M+i≤k≤NM + i \le k \le N cancel out as they appear in both sums. When M+i−1>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=2∑k=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=1∑k=1N1k(k+i)<1i∑k=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>m≥1N > m \ge 1 and i≥1i \ge 1 we have
Pi(m)<1mHm+i+1i∑k=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(1k−1k+1)Hk+i=∑k=mN1kHk+i−∑k=m+1N+11kHk+i−1=1mHm+i+∑k=m+1N1k(Hk+i−Hk+i−1)−1N+1HN+i<1mHm+i+∑k=m+1N1k(k+i)<1mHm+i+1i∑k=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=1N1ab∑c=1N1c(a+b+c+1)<∑a,b=1NHa+b+1ab(a+b+1)using (33) with i=a+b+1=∑a,b=1Na+bab⋅Ha+b+1(a+b)(a+b+1)=∑k=22N∑a+b=k(1a+1b)Hk+1k(k+1)=2∑k=22N∑m=1k−11m⋅Hk+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*}

∑k=22N∑m=1k−11m⋅Hk+1k(k+1)=∑m=12N−11m∑k=m+12NHk+1k(k+1).\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<2∑m=12N−11m∑k=m+12NHk+1k(k+1)=2∑m=12N−11mP1(m+1)<2∑m=12N−11m(1m+2+1m+1Hm+2)using (34)=2∑m=12N−11m(m+2)+2∑m=12N−1Hm+2m(m+1)=2∑m=12N−11m(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,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.