Maths Olympiad Prep

Library / /27 of 39

Algebra Difficulty 6.4 National olympiad Prove it Romania

Let mNm \in \mathbb{N}, m2m \ge 2 be a fixed natural number, and let (an)n1(a_n)_{n \ge 1} be a sequence of nonnegative real numbers such that an+1anamna_{n+1} \le a_n - a_{mn}, n1\forall n \ge 1.

a) Prove that the sequence (bn)n1(b_n)_{n \ge 1}, bn=k=1nakb_n = \sum_{k=1}^{n} a_k is bounded above.

b) Prove that the sequence (cn)n1(c_n)_{n \ge 1}, cn=k=1nk2akc_n = \sum_{k=1}^{n} k^2 a_k is bounded above.

Solution

a) We notice that (bn)n1(b_n)_{n \ge 1} is non-decreasing. Also, the sequence (an)n1(a_n)_{n \ge 1} is non-increasing, since 0amnanan+10 \le a_{mn} \le a_n - a_{n+1}. Moreover,
k=1namka1an+1a1. \sum_{k=1}^{n} a_{mk} \le a_1 - a_{n+1} \le a_1.

Using the monotonicity of (an)(a_n) and (bn)(b_n), we have:
bnbmn=k=1mnak=i=1m1ai+k=1namk+k=1n1j=1m1amk+j. b_n \le b_{mn} = \sum_{k=1}^{mn} a_k = \sum_{i=1}^{m-1} a_i + \sum_{k=1}^{n} a_{mk} + \sum_{k=1}^{n-1} \sum_{j=1}^{m-1} a_{mk+j}.
By monotonicity,
k=1n1j=1m1amk+j(m1)k=1n1amk(m1)a1, \sum_{k=1}^{n-1} \sum_{j=1}^{m-1} a_{mk+j} \le (m-1) \sum_{k=1}^{n-1} a_{mk} \le (m-1)a_1,
hence,
bni=1m1ai+k=1namk+(m1)a1i=1m1ai+ma1, b_n \le \sum_{i=1}^{m-1} a_i + \sum_{k=1}^{n} a_{mk} + (m-1)a_1 \le \sum_{i=1}^{m-1} a_i + ma_1,

b) We first prove that the sequence dn=k=1nkakd_n = \sum_{k=1}^{n} k a_k is bounded above. Clearly, (dn)n1(d_n)_{n \ge 1} is non-decreasing. Moreover,
k=1nkamkk=1nk(akak+1)=a1+k=2n(k(k1))aknan+1bn, \sum_{k=1}^{n} k a_{mk} \le \sum_{k=1}^{n} k(a_k - a_{k+1}) = a_1 + \sum_{k=2}^{n} (k - (k-1))a_k - n a_{n+1} \le b_n,
so the sequence (k=1nkamk)n1\left( \sum_{k=1}^{n} k a_{mk} \right)_{n \ge 1} is bounded above.
On the other hand,
dndmn=mk=1nkamk+k=1m1kak+j=1m1k=1n1(mk+j)amk+jmbn+dm1+(m1)k=1n1m(k+1)amkmbn+dm1+m(m1)(bn1+a1), \begin{aligned} d_n \le d_{mn} &= m \sum_{k=1}^{n} k a_{mk} + \sum_{k=1}^{m-1} k a_k + \sum_{j=1}^{m-1} \sum_{k=1}^{n-1} (mk + j)a_{mk+j} \\ &\le m b_n + d_{m-1} + (m-1) \sum_{k=1}^{n-1} m(k+1)a_{mk} \\ &\le m b_n + d_{m-1} + m(m-1)(b_{n-1} + a_1), \end{aligned}
hence (dn)n1(d_n)_{n \ge 1} is bounded above.

Again, (cn)n1(c_n)_{n \ge 1} is non-decreasing. Similarly,
k=1nk2amkk=1nk2(akak+1)=a1+k=2n(k2(k1)2)akn2an+1a1+k=2n2kak2dn, \begin{aligned} \sum_{k=1}^{n} k^2 a_{mk} &\le \sum_{k=1}^{n} k^2 (a_k - a_{k+1}) = a_1 + \sum_{k=2}^{n} (k^2 - (k-1)^2)a_k - n^2 a_{n+1} \\ &\le a_1 + \sum_{k=2}^{n} 2k a_k \le 2 d_n, \end{aligned}
so the sequence (k=1nk2amk)n1\left( \sum_{k=1}^{n} k^2 a_{mk} \right)_{n \ge 1} is bounded above.
Finally,
cncmn=m2k=1nk2amk+cm1+j=1m1k=1n1(mk+j)2amk+j2m2dn+cm1+m2(m1)(k=1n1k2amk+2k=1n1kamk+k=1n1amk), \begin{aligned} c_n \le c_{mn} &= m^2 \sum_{k=1}^{n} k^2 a_{mk} + c_{m-1} + \sum_{j=1}^{m-1} \sum_{k=1}^{n-1} (mk + j)^2 a_{mk+j} \\ &\le 2m^2 d_n + c_{m-1} + m^2(m-1) \left( \sum_{k=1}^{n-1} k^2 a_{mk} + 2 \sum_{k=1}^{n-1} k a_{mk} + \sum_{k=1}^{n-1} a_{mk} \right), \end{aligned}
which is a finite sum of bounded above sequences, hence (cn)n1(c_n)_{n \ge 1} is bounded above.

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.