I encounter the following recurrence \begin{equation} \tag{1}\label{eq:1} h_{j+1} = h_{j} ( 1 - 1/j - c h_j ), \quad j \geq j_0, \end{equation} with $h_{j_0}>0$, $c>0$ and $0< 1-1/j_0 - c h_{j_0} < 1$.

Question: How does $h_j$ behave for large $j$?

I believe that $$\tag{2} \label{eq:3} h_j = O(1/j^{1 + \alpha}),$$ for some $\alpha>0$ dependent on $c$, and it seems like I have half a proof:

Lemma: If $$\tag{3} \label{eq:2} x_{j+1} \leq x_{j} ( 1 - \beta/j), \quad j \geq j_0,$$ with $\beta>0$, $x_{j_0}>0$, $0< 1-\beta/x_{j_0}< 1$, then $x_j \leq (x_{j_0}/j_0) j^{-\beta}$.

Proof: We have \begin{align} x_{N+1} &= x_{j_0} \prod_{j=j_0}^N (1-\beta/j) = x_{j_0} \exp\left(\sum_{j=j_0}^N \log(1-\beta/j) \right) \leq x_{j_0} \exp\left(-\sum_{j=j_0}^N \beta/j \right) \\ &\leq x_{j_0} \exp\left( -\beta \int_{j_0}^{N+1}1/x \,dx \right) = x_{j_0} \exp\left(-\beta (\log(N+1)-\log(j_0)) \right) \\ = &(x_{j_0}/j_0) (N+1)^{-\beta}. \quad \quad \mbox{Q.E.D.} \end{align}

In above, we use the inequality $\log(1+x)\leq x$, which is, of course, tight for small $x$. In particular, for any small $\epsilon>0$, we have the inverse inequality $(1-\epsilon) x \leq \log(1+x)$. Therefore, we can also get the following:

Lemma: If $x_{j+1} \geq x_{j} ( 1 - \beta/j)$, $j \geq j_0$, with $\beta>0$, $x_{j_0}>0$, $0< 1-\beta/x_{j_0}< 1$, then for any $\epsilon>0$, there is a $C_\epsilon>0$ such that $x_j \geq C_\epsilon j^{-\beta(1-\epsilon)}$.

To get something out of \eqref{eq:1}, we can use a bootstrapping strategy. First, we have $$ h_{j+1} < h_{j} ( 1 - 1/j ), \quad j \geq j_0. $$ So, by the first lemma, we have $h_j < (h_{j_0}/j_0) j^{-1}$.

The $O(1/j)$ asymptotic for \eqref{eq:1} cannot be tight, otherwise $h_j \geq \gamma / j$ for some $\gamma>0$. But then, by \eqref{eq:1}, $h_{j+1} \leq h_j(1-1/j-\gamma/j) = h_j( 1- (1+\gamma)/j)$, which, by the first lemma, implies that $h_j = O(1/j^{1+\gamma})$, causing a contradiction.

Thus $h_j$ must decay faster than $O(1/j)$. But I don't quite have a proof that the conjecture in \eqref{eq:3} is true.

We can also get a lower bound for $h_j$ from the earlier upper bound: $h_{j+1}> h_j(1-1/j-(h_{j_0}/j_0)(1/j) = h_j(1 - (1+h_{j_0}/j_0)/j)$. This shows, by the second lemma above, $h_j$ cannot decay faster than $O(1/j^{(1+h_{j_0}/j_0)})$.

This is about as much bootstrapping as I can do. If anyone has seen anything related, or know of a proof to \eqref{eq:3} and the optimal value for $\alpha$ thereof, I will be thrilled to hear from you. Thanks.

  • 2
    $\begingroup$ The actual answer is $h_j=\frac{1+o(1)}{cj\log j}$ as $j\to\infty$. $\endgroup$
    – fedja
    May 13 '19 at 9:13
  • $\begingroup$ Thanks very much. Sorry for the late response. I was wondering if this follows from a reasonably well-known trick/method... I also wonder if your 'c' is my 'c' in (1). $\endgroup$
    – Thomas
    May 21 '19 at 16:31
  • 1
    $\begingroup$ Yes, it is.$\hspace{5pt}$ $\endgroup$
    – fedja
    May 21 '19 at 17:00

It looks that it is not so, right behaviour is $(n\log n)^{-1}$.

Clearly your sequence is positive and decreasing. Denote $h_j=1/x_j$. Then $$x_{j+1}=x_j(1-1/j-c/x_j)^{-1}\geqslant x_j(1+(1/j+c/x_j))=x_j+c+x_j/j.$$

Further denoting $x_{j}=j y_j$ we rewrite this as $y_{j+1}\geqslant y_j+c/(j+1)$. Summing up it for $j=j_0,\ldots,n-1$ it yields $y_n\geqslant c\log(n)-C$ for certain constant $C>0$, that is $x_n\geqslant cn\log(n)+O(n)$. It means that $$\log x_{j+1}-\log x_{j}=-\log\left(1-\frac1j-\frac{c}{x_j}\right)\leqslant \frac{1}j+\frac{1}{j\log j}+O\left(\frac{1}{j\log^2 j}\right), $$ thus $\log x_n\leqslant \log n+\log\log n+O(1)$, so $x_n\leqslant {\rm const}\cdot n\log n$.


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.