# Question from the Brazilian Math Olympiad

I am stuck with this problem that appeared in the Undergrad Brazilian Math Olympiad from 2017. The problem is:

let $$x_n$$ be a strictly positive sequence that $$x_n\rightarrow 0$$. Suppose that exists $$c>0$$ that $$|x_{n+1}-x_n|\leq c x_n ^2$$ for all $$n\in\mathbb{N}$$. Show that there is $$d>0$$ that $$n x_n\geq d$$ for all $$n\in \mathbb{N}$$.

I tried using the Stolz-Cesàro lemma, but didn't help me very much. Does anyone have a hint? Thanks!

EDIT:

Let me give some context of my idea. For the Stolz-Cesàro lemma the given sequence $$x_n$$ needs to be strictly decreasing, since it $$x_n\rightarrow 0$$ and $$x_n>0$$. Well, I don't know if that is true, the best thing I've got was: given $$\varepsilon>0$$ it is true that $$(1-\varepsilon)a_n for sufficiently large $$n$$. One could help me on that.

Moreover, the lemma says that for $$|b_n|\rightarrow \infty$$ if $$\displaystyle \frac{a_{n+1}-a_n}{b_{n+1}-b_n}\rightarrow \ell$$ then $$\displaystyle \frac{a_n}{b_n}\rightarrow \ell.$$

Supposing that $$x_n$$ is strictly decreasing, than I can choose $$a_n=n$$ and $$b_n=1/x_n$$. That way I would have $$c_n=\frac{(n+1)-n}{\frac{1}{x_{n+1}}-\frac{1}{x_{n}}}=\frac{1}{\frac{1}{x_{n+1}}-\frac{1}{x_{n}}}.$$ If it is possible to show that this sequence $$c_n$$ converges to some positive number I would have the result.

But with these assumptions (including that $$x_n$$ is strictly decreasing) the best thing that I've got was: $$\frac{1}{c}(1-x_n)\leq \frac{1}{\frac{1}{x_{n+1}}-\frac{1}{x_{n}}}=\frac{x_{n+1}x_n}{x_n-x_{n+1}}.$$

At this point there are two things that I don't know: (1) $$x_n$$ strictly decreases and (2) how do I find a comparison (if there is any) to show that $$\displaystyle \frac{x_{n+1}x_n}{x_n-x_{n+1}}< d_n$$, where $$d_n\rightarrow 1/c$$.

One last thing that I noticed is that the hypothesis $$|x_{n+1}-x_n|\leq c x_n ^2$$ implies that $$x_{n+1}/x_n\rightarrow 1$$ and $$f_n=\frac{|x_{n+1}-x_n|}{x_n ^2}$$ has a convergent subsequence. These facts implies that $$\frac{x_{n+1}x_n}{x_n-x_{n+1}}$$ also has a convergent subsequence.

• Is this the olympiad page? Don't they publish solutions? Thanks. – Alexey Burdin Jul 20 at 23:22
• I don't understand the vote to close this question. – Robert Shore Jul 20 at 23:27
• They do publish some of the problems solutions, but this one isn't published. – Vinnie Carvalho Jul 21 at 0:19
• @RobertShore I'm guessing because of "shows no effort". IE It is "missing context and details". – Calvin Lin Jul 21 at 1:37

We're to show that there exists such $$d>0$$ that $$\frac{1}{nx_n}<\frac{1}{d}$$ i.e. that $$\frac{1}{nx_n}$$ is bounded from above.
Consider $$y_n=\frac{1}{cnx_n}$$ i.e. $$x_n=\frac{1}{cny_n}$$ then the inequality $$|x_{n+1}-x_n|\le cx_n^2$$ becomes $$\left|\frac{1}{c(n+1)y_{n+1}}-\frac{1}{cny_n}\right|\le c\frac{1}{c^2n^2y_n^2}$$ and we can cancel $$c$$. After some rearrangements the inequality becomes $$\frac{1}{n y_n - 1} + 1 \ge (n+1)y_{n+1}-ny_n\ge \frac{1}{1 + n y_n} - 1$$ then, noting $$ny_n\to +\infty$$ as $$ny_n=\frac{1}{cx_n}$$ and $$x_n\to +0$$, we have $$\frac{1}{ny_n-1}+1\to 1$$ thus LHS is bounded by some constant $$C$$ from above and we can write $$C\ge \frac{1}{n y_n - 1} + 1 \ge (n+1)y_{n+1}-ny_n$$ $$C\ge (n+1)y_{n+1}-ny_n$$ summing up for $$n=1,\ldots,\,m$$ we have $$Cm\ge (m+1)y_{m+1}-y_1$$ $$C(m+1)\ge Cm\ge (m+1)y_{m+1}-y_1$$ $$C\ge y_{m+1}-\frac{y_1}{m+1}$$ $$y_1+C\ge\frac{y_1}{m+1}+C\ge y_{m+1}$$ i.e. $$y_{m+1}$$ is bounded from above. QED.

"Some rearrangements":

$$\left|\frac{1}{c(n+1)y_{n+1}}-\frac{1}{cny_n}\right|\le c\frac{1}{c^2n^2y_n^2}$$ $$-\frac{1}{n^2y_n^2}\le \frac{1}{(n+1)y_{n+1}}-\frac{1}{ny_n}\le \frac{1}{n^2y_n^2}$$ $$\frac{1}{ny_n}-\frac{1}{n^2y_n^2}\le \frac{1}{(n+1)y_{n+1}}\le \frac{1}{ny_n}+\frac{1}{n^2y_n^2}$$ $$\frac{ny_n-1}{n^2y_n^2}\le \frac{1}{(n+1)y_{n+1}}\le \frac{ny_n+1}{n^2y_n^2}$$ Now we consider only that $$y_n$$ for which $$ny_n-1>0$$, the other are already bounded from above by $$\frac 1n$$. $$\frac{n^2y_n^2}{ny_n-1}\ge (n+1)y_{n+1}\ge \frac{n^2y_n^2}{ny_n+1}$$ $$\frac{n^2y_n^2-ny_n(ny_n-1)}{ny_n-1}\ge (n+1)y_{n+1}-ny_n\ge \frac{n^2y_n^2-ny_n(ny_n+1)}{ny_n+1}$$ $$\frac{ny_n}{ny_n-1}\ge (n+1)y_{n+1}-ny_n\ge \frac{-ny_n}{ny_n+1}.$$

• Thank you for your help! – Vinnie Carvalho Jul 21 at 2:48
• You're welcome.) Spent 3.5 hours so not-a-contest solution) Contests are 4h-6h likely. – Alexey Burdin Jul 21 at 2:51

[This seems a lot easier than I expected, so there might be errors in it. If so, please let em know where.]

These steps can be demystified by referencing the subsequent block of text

1. Pick $$N$$ such that $$\forall n > N$$, $$x_n < \frac{ 1}{2c}$$.
2. Set $$k = \min ( \frac{1}{2c}, Nx_N )$$. Observe that $$\frac{N}{N+1} \geq \frac{1}{2} \geq ck$$ and $$Nx_N \geq k$$.
3. Hence $$(N+1) x_{N+1} \geq (N+1)( x_N - cx_N^2) \geq (N+1)(\frac{k}{N} - \frac{ ck^2}{N^2}) = k + \frac{k( \frac{N}{N+1} - ck ) }{N^2(N+1)} \geq k$$.
4. Also, $$\frac{N+1}{N+1+1} \geq \frac{1}{2} \geq ck$$.
5. Proceed by induction to conclude that $$n x_n \geq k$$.

We claim that under suitable conditions (to be determined), if $$n x_n \geq k$$, then $$(n+1) x_{n+1} \geq k$$. If so, the result follows by induction.

Which conditions make sense?

1. We have $$x_{n+1} \in ( x_n - c x_n^2, x_n + cx_n^2)$$.
2. We have $$\frac{k}{n} < x_n$$.
3. We will likely want $$x - c x^2$$ to be increasing, which requires $$x_n < \frac{1}{2c}$$. This can be satisfied as $$\lim x_n = 0$$.
4. Henceforth, we assume $$\frac{k}{n} < x_n < \frac{1}{2c}$$. This necessitates $$2ck < n$$, which can be achieved.
5. Now, $$(n+1) x_{n+1} > (n+1) \left[ x_n - c x_n^2\right] > (n+1) \left[\frac{k}{n} - \frac{ ck^2 } { n^2 } \right]$$. Verify that $$(n+1) \left[\frac{k}{n} - \frac{ ck^2 } { n^2 } \right] \geq k \Leftrightarrow \frac{n}{n+1} \geq ck$$.

This gives us all of the conditions that we need.

• Thank you for your help! – Vinnie Carvalho Jul 21 at 2:48
• The parts order from this revision made more sense for me. – Alexey Burdin Jul 21 at 2:49
• @AlexeyBurdin I agree with you. It's the difference between presenting a clean direct solution for the olympiad vs motivating the approach / values chosen. I just started writing stuff down and it follows immediately (which is why I'm questioning if there is an error). – Calvin Lin Jul 21 at 2:54