Maths Olympiad Prep

Library / NMO Selection Tests for BMO and IMO /23 of 47

NMO Selection Tests for BMO and IMO

Algebra Difficulty 8.1 Shortlist Prove it Romania

Given an integer n≥2n \ge 2, determine the integral part of the number
∑k=1n−11(1+1n)⋯(1+kn)−∑k=1n−1(1−1n)⋯(1−kn). \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+⋯+u2n−1)/un(u_{n+1} + \cdots + u_{2n-1})/u_n, and the second is (u0+⋯+un−2)/un−1(u_0 + \cdots + u_{n-2})/u_{n-1}. Notice that un−1=unu_{n-1} = u_n to write the difference of the two in the form
1−u2nun+1un∑k=1n(un+k−un−k). 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=1nun−k\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=1nkun−kand∑k=1n(m−k)un+k<∑k=1n(m−k)un−k(∗) \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(k−n)uk<0\sum_{k=0}^{2n} (k-n) u_k < 0. To establish the latter, simply notice that ∑k=02nkuk=n∑k=02n−1uk<n∑k=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 n≥3n \ge 3. Write
un+kun−k⋅un−k−1un+k+1=1+1n−k(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/un−ku_{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/un−1=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 n≥3n \ge 3, there exists mm in the range 1,2,…,n1, 2, \dots, n such that un+k<un−ku_{n+k} < u_{n-k} for 1≤k<m1 \le k < m, and un+k>un−ku_{n+k} > u_{n-k} for m<k≤nm < k \le n. Consequently, the second inequality (∗)(*) holds termwise for k≠mk \ne m. This ends the proof.

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.