Maths Olympiad Prep

Library / /12 of 20

Algebra Difficulty 6.5 National olympiad Prove it China

Suppose that ak>0a_k > 0, k=1,2,,2008k = 1, 2, \dots, 2008.
Prove that if and only if k=12008ak>1\sum_{k=1}^{2008} a_k > 1, there is a sequence {xn}\{x_n\} satisfying
(1) 0=x0<xn<xn+10 = x_0 < x_n < x_{n+1}, n=1,2,3,n = 1, 2, 3, \dots;
(2) limnxn\lim_{n \to \infty} x_n exists;
(3) xnxn1=k=12008akxn+kk=02007ak+1xn+kx_n - x_{n-1} = \sum_{k=1}^{2008} a_k x_{n+k} - \sum_{k=0}^{2007} a_{k+1} x_{n+k}, n=1,2,3,n = 1, 2, 3, \dots

Solution

Proof of necessity: Assume that there exists {xn}\{x_n\} satisfying (1)–(3). Notice that the expression in (3) can be written as
xnxn1=k=12008ak(xn+kxn+k1),nN. x_n - x_{n-1} = \sum_{k=1}^{2008} a_k (x_{n+k} - x_{n+k-1}), \quad n \in \mathbb{N}.
As x0=0x_0 = 0, we then have
xn=l=1n(xlxl1)=l=1nk=12008ak(xl+kxl+k1)=k=12008l=1nak(xl+kxl+k1)=k=12008ak(xn+kxk). \begin{align*} x_n &= \sum_{l=1}^{n} (x_l - x_{l-1}) = \sum_{l=1}^{n} \sum_{k=1}^{2008} a_k (x_{l+k} - x_{l+k-1}) \\ &= \sum_{k=1}^{2008} \sum_{l=1}^{n} a_k (x_{l+k} - x_{l+k-1}) \\ &= \sum_{k=1}^{2008} a_k (x_{n+k} - x_k). \end{align*}
From (2) we are able to define b=limnxnb = \lim_{n \to \infty} x_n. Let nn \to \infty in the above expression. Then we have
b=k=12008ak(bxk)=bk=12008akk=12008akxk<bk=12008ak. b = \sum_{k=1}^{2008} a_k (b - x_k) = b \sum_{k=1}^{2008} a_k - \sum_{k=1}^{2008} a_k x_k \\ < b \sum_{k=1}^{2008} a_k.
Therefore, k=12008ak>1\sum_{k=1}^{2008} a_k > 1.

Proof of sufficiency: Assume that k=12008ak>1\sum_{k=1}^{2008} a_k > 1. Define a polynomial function by
f(s)=1+k=12008aksk,s[0,1]. f(s) = -1 + \sum_{k=1}^{2008} a_k s^k, \quad s \in [0, 1].
f(s)f(s) is strictly increasing on the interval [0,1][0, 1]. In the meantime,
f(0)=1<0,f(1)=1+k=12008ak>0, f(0) = -1 < 0, \quad f(1) = -1 + \sum_{k=1}^{2008} a_k > 0,
and there then exists a unique 0<s0<10 < s_0 < 1 such that f(s0)=0f(s_0) = 0.
Now, define xn=k=1ns0kx_n = \sum_{k=1}^{n} s_0^k, nNn \in \mathbb{N}. It is easy to see that {xn}\{x_n\} satisfies (1) and
xn=k=1ns0k=s0s0n+11s0. x_n = \sum_{k=1}^{n} s_0^k = \frac{s_0 - s_0^{n+1}}{1 - s_0}.
On the other hand, limns0n+1=0\lim_{n \to \infty} s_0^{n+1} = 0 as 0<s0<10 < s_0 < 1. Then we have
limnxn=limns0s0n+11s0=s01s0. \lim_{n \to \infty} x_n = \lim_{n \to \infty} \frac{s_0 - s_0^{n+1}}{1 - s_0} = \frac{s_0}{1 - s_0}.
This means that {xn}\{x_n\} satisfies (2). Finally, we have
0=f(s0)=1+k=12008aks0k. 0 = f(s_0) = -1 + \sum_{k=1}^{2008} a_k s_0^k.
That is to say, k=12008aks0k=1\sum_{k=1}^{2008} a_k s_0^k = 1. Then we have
xnxn1=s0n=(k=12008aks0k)s0n=k=12008aks0n+k=k=12008ak(xn+kxn+k1). \begin{align*} x_n - x_{n-1} &= s_0^n \\ &= \left( \sum_{k=1}^{2008} a_k s_0^k \right) s_0^n \\ &= \sum_{k=1}^{2008} a_k s_0^{n+k} \\ &= \sum_{k=1}^{2008} a_k (x_{n+k} - x_{n+k-1}). \end{align*}
Therefore, {xn}\{x_n\} also satisfies (3). This completes 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 and solution reproduced as published; topic and difficulty added by this site.