Let $u_1>0$ be a real number. Let us consider $(u_n)_{n\geq 1}$ the sequence such as:

$$ \forall n \geq 1, u_{n+1} = \frac{u_n}{n} + \frac{1}{n^2}\quad (\star) $$

Find an equivalent of $u_n$ as $n\to +\infty$.

So I found a way to show that $u_n \sim \frac{1}{n^2}$, but I'm quite unhappy with this method because I feel like I found it by chance without understanding anything (I did a lot of trials and found this)

My method:

I showed by induction that $u_n \leq (u_1+1)$. Thus, $u_n\to 0$ considering $(\star)$.

Then, $nu_{n+1} = u_n + 1/n$. Thus (since $n+1 \sim n$), $nu_n \to 0$.

To end with, I have $n^2u_{n+1} = nu_n + 1$. Thus, $(n+1)^2 u_n \sim n^2u_n \to 1$.

How would you solve such a problem? Is there any more intuitive method that one may have done?

  • $\begingroup$ It is right actually. I think elementary proof has you find is rather good. Where the intuition comes it that $u_n$ is ponderated with $n$ and $u_{n+1}$ can be with $n^2$ by multiplying all the equation by $n^2$. So I think that ponderation lead you to the equivalent. $\endgroup$ – EDX Jun 4 '20 at 15:39

1. There is a heuristic argument which is useful for guessing the behavior of $u_n$: Rewrite the recurrence relation as

$$ u_{n+1} - u_n = \frac{u_n}{n} - u_n + \frac{1}{n^2}. $$

Its continuum analogue is the following differential equation:

$$ y' = \frac{y}{x} - y + \frac{1}{x^2}. $$

Using the standard method, this equation can be solved as:

$$ y(x) = x e^{-x} \int \frac{e^x}{x^3} \, \mathrm{d}x. $$

Then L'Hospital's Rule then tells that $y(x) \sim x^{-2}$ as $x \to \infty$. From this observation, we may as well expect that $u_n \sim n^{-2}$.

2. The above ansatz suggests that, in the recurrence relation for $u_{n+1}$, $\frac{1}{n^2}$ is the dominating term and $\frac{u_n}{n}$ is much smaller as $n\to\infty$. In particular, nesting this relation will produce an expansion with ever decreasing terms. This idea can be easily tested as follows:

Let $r_n = (n-1)u_n$. Then for $n \geq 2$,

$$ r_n = (n-1)u_{n} = \frac{1}{n-1} + \frac{r_{n-1}}{n-1}. $$

From this, we get

\begin{align*} r_n &= \frac{1}{n-1} + \frac{r_{n-1}}{n-1} \\ &= \frac{1}{n-1} + \frac{1}{(n-1)(n-2)} + \frac{r_{n-2}}{(n-1)(n-2)} \\ &= \frac{1}{n-1} + \frac{1}{(n-1)(n-2)} + \frac{1}{(n-1)(n-2)(n-3)} + \frac{r_{n-3}}{(n-1)(n-2)(n-3)} \\ &\qquad\vdots\\ &= \sum_{k=1}^{n-2} \frac{1}{(n-1)\cdots(n-k)} + \frac{r_2}{(n-1)!} \end{align*}

Using this, it is not hard to conclude that $(n-1)^2 u_n \to 1$ as $n\to\infty$, and in fact, we can extract an asymptotic expansion of $u_n$ up to any prescribed order $\mathcal{O}(n^{-M})$.


This is similar to Sangchul Lee's approach.

If we multiply $n!$ both sides of the recurrence, we obtain $$ n!u_{n+1}=(n-1)!u_n+\frac{n!}{n^2}. $$ Applying the above repeatedly, $$ u_{n+1}=\frac1{n!} \sum_{k=1}^n \frac{k!}{k^2} + \frac{u_1}{n!}. $$

  • $\begingroup$ That's a really good method! Thanks $\endgroup$ – MiKiDe Jun 7 '20 at 9:17

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.