# Nonlinear recurrence

I encounter the following recurrence $$$$\tag{1}\label{eq:1} h_{j+1} = h_{j} ( 1 - 1/j - c h_j ), \quad j \geq j_0,$$$$ 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.

• The actual answer is $h_j=\frac{1+o(1)}{cj\log j}$ as $j\to\infty$. May 13 '19 at 9:13
• 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). May 21 '19 at 16:31
• Yes, it is.$\hspace{5pt}$ 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$$.