When analyzing an algorithm's utility, I've encountered the following recursion, where $n$ is a parameter:
$ a_k=a_{k-1}+1+(1-1/n)^{a_{k-1}}$
I am interested in the limit of $a_n$ as $n\rightarrow\infty$. Any help is greatly appreciated!
9
-
1$\begingroup$ What is $a_0$ (or, rather, does it depend on $n$?). $\endgroup$– fedjaCommented Jan 3, 2023 at 17:55
-
$\begingroup$ The question is not clear. What goes to infinity? $k$ or the parameter $n$? $\endgroup$– Christophe LeuridanCommented Jan 3, 2023 at 18:29
-
$\begingroup$ Sorry, $a_0=0$ , the parameter $n$ goes to infinity, essentially I'm taking the limit of the series $b_n$ where $b_n$ is defined as $a_n$ (the $n$th element in the defined recursion) with the parameter $n$. $\endgroup$– user497270Commented Jan 3, 2023 at 18:54
-
3$\begingroup$ It is still not clear. Is $n$ a parameter or the index of the sequence. First, you say that it is a parameter, and you define a sequence $(a_k)$ by recursion. The recursion formula involves $n$ as a parameter. Then you ask for the behavior of $a_n$ as $n$ goes to infinity. Should we read $a_k$ as $k$ goes to infinity? Is there a typo somewhere? Do you have a sequence $(a_k)$ depending on a parameter $n$? Be clear with the notations, the assumptions and the question! $\endgroup$– Christophe LeuridanCommented Jan 3, 2023 at 21:19
-
1$\begingroup$ @fedja : A formal, complete proof certainly seems within reach now (reducing to two certain inequalities for elementary functions of one variable, which in turn are reducible to inequalities for polynomials in one variable). However, my proof is going to be long and messy, and at this point I am unsure if it is worth the effort. $\endgroup$– Iosif PinelisCommented Jan 4, 2023 at 3:11
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
The situation is governed by the following instance of a very general comparison principle (so general that I wouldn't even try to formulate it in full).
Let $f:[0,+\infty)\to[0,+\infty)$ be a decreasing function. Let $a_0=0$, $a_k=a_{k-1}+f(a_{k-1})$. Let $A(0)=0$, $A'(x)=f(A(x))$. Then for all $k$, we have $|a_k-A(k)|\le f(0)$.
Proof:
Let $k$ be the first index for which $a_k>A(k)+f(0)$ (if it exists). Then $a_{k-1}=a_k-f(a_{k-1})\ge a_k-f(0)>A(k)$, so $a_k-a_{k-1}\le f(A(k))$ while $A(k)-A(k-1)=\int_{k-1}^k f(A(t))\,dt\ge f(A(k))$, so we must already have $a_{k-1}>A(k-1)+f(0)$, contradicting the choice of $k$.
Similarly, let $k$ be the first index for which $a_k<A(k)-f(0)$ (if it exists). Then $A(k-1)=A(k)-\int_{k-1}^k f(A(t))\,dt\ge A(k)-f(0)>a_k$, so $A(k)-A(k-1)=\int_{k-1}^k f(A(t))\,dt\le f(a_k)$ while $a_k-a_{k-1}=f(a_{k-1})\ge f(a_k)$, so we must already have $a_{k-1}<A(k-1)-f(0)$, contradicting the choice of $k$.
Now just solve the related differential equation and use the fact that $\log(1-1/n)\asymp -1/n$ for large $n$.
