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!


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<a_{n+1}<(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.

That's it, please help!

  • $\begingroup$ Is this the olympiad page? Don't they publish solutions? Thanks. $\endgroup$ – Alexey Burdin Jul 20 at 23:22
  • 2
    $\begingroup$ I don't understand the vote to close this question. $\endgroup$ – Robert Shore Jul 20 at 23:27
  • $\begingroup$ They do publish some of the problems solutions, but this one isn't published. $\endgroup$ – Vinnie Carvalho Jul 21 at 0:19
  • $\begingroup$ @RobertShore I'm guessing because of "shows no effort". IE It is "missing context and details". $\endgroup$ – 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}.$$

| cite | improve this answer | |
  • $\begingroup$ Thank you for your help! $\endgroup$ – Vinnie Carvalho Jul 21 at 2:48
  • $\begingroup$ You're welcome.) Spent 3.5 hours so not-a-contest solution) Contests are 4h-6h likely. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Thank you for your help! $\endgroup$ – Vinnie Carvalho Jul 21 at 2:48
  • $\begingroup$ The parts order from this revision made more sense for me. $\endgroup$ – Alexey Burdin Jul 21 at 2:49
  • $\begingroup$ @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). $\endgroup$ – Calvin Lin Jul 21 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.