3
$\begingroup$

Let $\{u_n\}_{n\in\mathbb{N}}$ be a sequence of nonnegative real numbers (i.e., $u_n\geq 0$ for all $n\in\mathbb{N}$). Assume furthermore that, for some positive constant $C$, the following holds:

$$u_{n+1}\leq \left(1-\frac{1}{n+1}\right)u_n + \frac{C}{n+1}$$

Can anything be said about the convergence of the sequence $\{u_{n}\}_{n\in\mathbb{N}}$? When the final term $\frac{C}{n+1}$ is replaced by a term that is summable, e.g., $\frac{C}{(n+1)^p}$ for $p>1$, there is an old lemma due to K.L. Chung which ensures that the sequence $u_n\to 0$. If we instead relax this lemma to $p=1$, I was wondering if maybe there are results/references saying that $u_n\to u\geq 0$, perhaps with some dependnce on the constant $C$? A counterexample would also be appreciated.

Improve this question
$\endgroup$
2
  • $\begingroup$ @ThomasKojar : There can be no blowup here: If $u_n\le a$ and $a\ge C$, then $u_{n+1}\le a$. $\endgroup$
    – Iosif Pinelis
    Commented Oct 18, 2023 at 17:52
  • $\begingroup$ Every time I encounter the name of Kai Lai Chung I remember that he is the author of a probability textbook in which a section begins as follows: $$ \begin{align} & \text{Everybody knows that} \\ & \qquad\qquad\qquad\qquad e^x = \sum_{n=0}^\infty \frac{x^n}{n!}. \end{align} $$ (Those who don't want to read this present comment are hereby ordered not to do so.) $\endgroup$
    – Michael Hardy
    Commented Oct 18, 2023 at 18:05

1 Answer 1

Reset to default
1
$\begingroup$

A limit of $u_n$ does not have to exist.

Indeed, by rescaling, without loss of generality $C=1$.

Then, using the substitution $$u_n=\frac{w_n}n+\frac{n-1}n,$$ we rewrite the recurrence as $$w_{n+1}\le w_n$$ and the condition $u_n\ge0$ as $w_n\ge1-n$.

So, $(w_n)$ is any nonincreasing sequence such that $w_n\ge1-n$ for all $n$.

It is easy to see that for such a sequence $(w_n)$ a limit of $\frac{w_n}n$ (as $n\to\infty$) does not have to exist.

For instance, one may take $w_n=1-2^{j-1}$ for integers $n\in[2^{j-1},2^j)$, for $j=1,2,\dots$ -- that is, $w_n=1-2^{j_n}$, where $j_n:=\lfloor\log_2 n\rfloor$. Corresponding to this, we have $$u_n=u^*_n:=\frac{n-2^{j_n}}n.$$

So, a limit of $u_n$ does not have to exist. $\quad\Box$

Here is the graph $\{(\log_2 n,u^*_n)\colon n=1,\dots,10000\}$, confirming that the sequence $(u^*_n)$ does not a limit:

enter image description here

And here is the graph $\{(n,\frac n{n+1}\,u^*_n +\frac1{n+1}-u^*_{n+1}\,)\colon n=1,\dots,50\}$, confirming that your recurrence holds with $u^*_n$ in place of $u_n$:

enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for this very nice answer. How did you come up with the change of variables for $w_n$? $\endgroup$
    – giorgi nguyen
    Commented Oct 19, 2023 at 11:37
  • 1
    $\begingroup$ First, I noticed that your recurrence inequality (with $C=1$) holds with the equality for $a_n:=\frac{n-1}n$ in place of $u_n$. So, for $v_n:=u_n-a_n$ we have $v_{n+1}\le (1-\frac{1}{n+1})v_n=\frac n{n+1}\,v_n$, so that $w_{n+1}=(n+1)v_{n+1}\le nv_n=w_n$. (Vice versa, the inequality $w_{n+1}\le w_n$ implies your recurrence inequality (with $C=1$).) $\endgroup$
    – Iosif Pinelis
    Commented Oct 19, 2023 at 12:00
  • $\begingroup$ I guess the best we can hope for is a bound on $u_n$ - and this bound is given by $C$ as you already noted. I derived it another way by taking the sum up from $0$ to $K$ on both sides, dividing and taking the limit. Then I guess since you found a sequence $u_n$ for which we have equality, this can't be improved right? $\endgroup$
    – giorgi nguyen
    Commented Oct 21, 2023 at 17:02
  • $\begingroup$ @giorginguyen : That's right. $\endgroup$
    – Iosif Pinelis
    Commented Oct 21, 2023 at 23:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .