Find asymptotic of recurrence sequence

Solution 1:

Let $y_n = \frac{1}{x_n} - n$, we have

$$y_{n+1} = \frac{1}{x_{n+1}}-(n+1) = \frac{1}{x_n} + \frac{1}{1-x_n} - (n+1) = y_n + \frac{x_n}{1-x_n}$$ This implies for $n > 1$,

$$y_n = y_1 + \sum_{k=1}^{n-1} \frac{x_k}{1-x_k} \quad\iff\quad \frac{1}{x_n} = n + 1 + \sum_{k=1}^{n-1}\frac{x_k}{1-x_k} \tag{*1}$$ Since $0 \le x_k < 1$, this immediately give us an upper bound of $x_n$:

$$\frac{1}{x_n} \ge n+1 \quad\iff\quad x_n \le \frac{1}{n+1}\tag{*2}$$

Substitute $(*2)$ in $(*1)$ and notice the map $x \mapsto \frac{x}{1-x}$ is an increasing function for $x \in [0,1)$, we obtain a lower bound for $x_n$:

$$\begin{align} & \frac{1}{x_n} \le n+1 + \sum_{k=1}^{n-1}\frac{\frac{1}{k+1}}{1 - \frac{1}{k+1}} = n + 1 + \sum_{k=1}^{n-1}\frac{1}{k} \le n + 1 + \log n + \gamma\\ \implies & x_n \ge \frac{1}{n + 1 + \log n + \gamma}\tag{*3} \end{align}$$ where $\gamma$ is the Euler–Mascheroni constant.

Combine these two bounds, it is clear we can take $\alpha = 1$ and $\displaystyle\lim_{n\to\infty} n^\alpha x_n = 1$.