Maths Olympiad Prep

Library / /473 of 520

Algebra Difficulty 7.6 National olympiad, round 2 Prove it

Let {an}n1\{a_n\}_{n \geq 1} be a bounded sequence satisfying
an<k=a2n+2006akk+1+12n+2007n=1,2,3,a_n < \displaystyle\sum_{k=a}^{2n+2006} \frac{a_k}{k+1} + \frac{1}{2n+2007} \quad \forall \quad n = 1, 2, 3, \ldots
Show that
an<1nn=1,2,3,a_n < \frac{1}{n} \quad \forall \quad n = 1, 2, 3, \ldots

Solution

To show that an<1nn=1,2,3,a_n < \frac{1}{n} \quad \forall \quad n = 1, 2, 3, \ldots, we will proceed with the following steps:

1. Boundedness and Initial Inequality:
Given that {an}n1\{a_n\}_{n \geq 1} is a bounded sequence, there exists a constant DD such that an<Da_n < D for all nn. The given inequality is:
an<k=n2n+2006akk+1+12n+2007. a_n < \sum_{k=n}^{2n+2006} \frac{a_k}{k+1} + \frac{1}{2n+2007}.

2. Applying the Boundedness:
Using the boundedness of ana_n, we can write:
an<12n+2007+k=n2n+2006Dk+1. a_n < \frac{1}{2n+2007} + \sum_{k=n}^{2n+2006} \frac{D}{k+1}.

3. Estimating the Sum:
The sum k=n2n+20061k+1\sum_{k=n}^{2n+2006} \frac{1}{k+1} can be approximated using the integral test, which gives us:
k=n2n+20061k+1ln(2n+2007n). \sum_{k=n}^{2n+2006} \frac{1}{k+1} \approx \ln\left(\frac{2n+2007}{n}\right).
Since ln(2n+2007n)=ln(2+2007n)\ln\left(\frac{2n+2007}{n}\right) = \ln(2 + \frac{2007}{n}), for large nn, this can be approximated by ln2.5\ln 2.5.

4. Combining the Estimates:
Therefore, we have:
an<12n+2007+Dln2.5. a_n < \frac{1}{2n+2007} + D \cdot \ln 2.5.

5. Iterative Process:
We now consider the iterative process. Suppose an<Cna_n < \frac{C}{n} for some constant CC. Then:
an<12n+2007+k=n2n+2006Ck+1. a_n < \frac{1}{2n+2007} + \sum_{k=n}^{2n+2006} \frac{C}{k+1}.
Using the same approximation for the sum, we get:
an<12n+2007+Cln2.5. a_n < \frac{1}{2n+2007} + C \cdot \ln 2.5.

6. **Refining the Constant CC:**
We need to show that CC can be reduced to 1. Assume C=1+ϵC = 1 + \epsilon for some small ϵ>0\epsilon > 0. Then:
an<12n+2007+(1+ϵ)ln2.5. a_n < \frac{1}{2n+2007} + (1 + \epsilon) \cdot \ln 2.5.
For large nn, 12n+2007\frac{1}{2n+2007} becomes negligible, and we can iterate this process to show that CC approaches 1.

7. Final Step:
By iterating the inequality and reducing CC step by step, we can show that for any ϵ>0\epsilon > 0, there exists an NN such that for all n>Nn > N, an<1+ϵna_n < \frac{1 + \epsilon}{n}. Taking the limit as ϵ0\epsilon \to 0, we get:
an<1n. a_n < \frac{1}{n}.

Thus, we have shown that an<1na_n < \frac{1}{n} for all nn.

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.