Maths Olympiad Prep

Library / /27 of 52

Algebra Difficulty 8.1 Shortlist Prove it Romania

Given an integer n2n \ge 2, determine the integral part of the number
k=1n11(1+1n)(1+kn)k=1n1(11n)(1kn). \sum_{k=1}^{n-1} \frac{1}{\left(1 + \frac{1}{n}\right) \cdots \left(1 + \frac{k}{n}\right)} - \sum_{k=1}^{n-1} \left(1 - \frac{1}{n}\right) \cdots \left(1 - \frac{k}{n}\right).

Solution

The required integral part is 00. The difference of the two sums is positive, since positivity clearly holds termwise.

To show it less than 11, let uk=nk/k!u_k = n^k/k!, k=0,1,2,k = 0, 1, 2, \dots, and express the two sums in terms of the uku_k. The first sum is (un+1++u2n1)/un(u_{n+1} + \cdots + u_{2n-1})/u_n, and the second is (u0++un2)/un1(u_0 + \cdots + u_{n-2})/u_{n-1}. Notice that un1=unu_{n-1} = u_n to write the difference of the two in the form
1u2nun+1unk=1n(un+kunk). 1 - \frac{u_{2n}}{u_n} + \frac{1}{u_n} \sum_{k=1}^{n} (u_{n+k} - u_{n-k}).
It is therefore sufficient to prove that k=1nun+k<k=1nunk\sum_{k=1}^n u_{n+k} < \sum_{k=1}^n u_{n-k}. To this end, we will show that
k=1nkun+k<k=1nkunkandk=1n(mk)un+k<k=1n(mk)unk() \sum_{k=1}^{n} k u_{n+k} < \sum_{k=1}^{n} k u_{n-k} \quad \text{and} \quad \sum_{k=1}^{n} (m-k) u_{n+k} < \sum_{k=1}^{n} (m-k) u_{n-k} \quad (*)
for some mm in the range 1,2,,n1, 2, \dots, n. Addition of the two inequalities ()(*) yields the desired inequality.

The first inequality ()(*) is equivalent to k=02n(kn)uk<0\sum_{k=0}^{2n} (k-n) u_k < 0. To establish the latter, simply notice that k=02nkuk=nk=02n1uk<nk=02nuk\sum_{k=0}^{2n} k u_k = n \sum_{k=0}^{2n-1} u_k < n \sum_{k=0}^{2n} u_k.

To establish the second inequality ()(*), discard the trivial case n=2n = 2 and let n3n \ge 3. Write
un+kunkunk1un+k+1=1+1nk(k+1)n2,k=0,1,,n, \frac{u_{n+k}}{u_{n-k}} \cdot \frac{u_{n-k-1}}{u_{n+k+1}} = 1 + \frac{1}{n} - \frac{k(k+1)}{n^2}, \quad k = 0, 1, \dots, n,
to infer that, as a function of kk, the ratio un+k/unku_{n+k}/u_{n-k} is strictly decreasing for k(k+1)<nk(k+1) < n and strictly increasing for k(k+1)>nk(k+1) > n; the situation at the possible case k(k+1)=nk(k+1) = n causes no trouble. Since un+1/un1=n/(n+1)<1u_{n+1}/u_{n-1} = n/(n+1) < 1, and u2n/u0=n2n/(2n)!>1u_{2n}/u_0 = n^{2n}/(2n)! > 1 for n3n \ge 3, there exists mm in the range 1,2,,n1, 2, \dots, n such that un+k<unku_{n+k} < u_{n-k} for 1k<m1 \le k < m, and un+k>unku_{n+k} > u_{n-k} for m<knm < k \le n. Consequently, the second inequality ()(*) holds termwise for kmk \ne m. This ends the proof.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.