For a physical model I am trying to solve this sequence:

$$\begin{align*} u_1 &= 1 \\ u_2 &= 1-\left(\frac{u_1}{2}\right) \\ u_3 &= 1-\left(\frac{u_1}{3} + \frac{u_2}{2}\right) \\ u_4 &= 1-\left(\frac{u_1}{4} + \frac{u_2}{3} + \frac{u_3}{2}\right) \\ &\vdots \\ u_n &= 1-\left(\frac{u_1}{n} + \frac{u_2}{n-1} + \cdots + \frac{u_{n-1}}{2} \right) \end{align*}$$

I would like to have at least the asymptotic behavior of $u_n$ but i really don't know how to do.

I tried to use the integral way to solve the harmonic series, so I take $f$ such as $f(n) = u_n$ so $$f(n) = 1-\left(\frac{f(1)}{n} + \frac{f(2)}{n-1} + \cdots + \frac{f(n-1)}{2}\right)$$ I suppose $f$ is decreasing and so I write $$f(n) \sim 1- \int_1^n \frac{f(x)}{n+1-x} \,dx$$ and then $$f'(x) + f(x) = \frac{1}{x}$$ But I'm not sure this is a correct way, and I don't really know how to solve that (seems to be $\sim 1/x$ when $x \to \infty$, but I found a solution $1 + \mathrm{Ei}(x)/e^{-x}$ that seems to be divergent).

  • 2
    $\begingroup$ If my calculation is correct, we have $$ \sum_{n=1}^{\infty} u_n x^n = -\frac{x^2}{(1-x)\log(1-x)}. $$ In particular, $\log |u_n| = 1+o(1)$. But this is a very poor asymptote. Also, I want to point out that $\mathrm{Ei}(x)/e^x$ converges to 0 as $x\to\infty$, in view of L'hospital's rule. $\endgroup$ – Sangchul Lee Mar 11 '13 at 13:23
  • $\begingroup$ Typo in the formula for $u_4$? $\endgroup$ – Eckhard Mar 11 '13 at 13:23
  • $\begingroup$ And it follows that $u_n$ has zero Abel-mean and $nu_n$ has infinite Aben-mean. Thus if $u_n$ has limit, monotone decreasing for example, the it should be zero. $\endgroup$ – Sangchul Lee Mar 11 '13 at 13:28
  • $\begingroup$ You have $u_n=1-\sum_{j=1}^{n-1}u_j\frac{1}{n+1-j}$. My idea would be to investigate objects like $u_{n+m}-u_n$. Of you might be able to plug the $u_j$'s into $u_n$ and obtain something which might look like "$1-\Pi_{k=1}^n\sum_k^{?}(\frac{1}{k!}+...)u_1^k$" $\endgroup$ – Nikolaj-K Mar 11 '13 at 13:38

Here is some observations: Let

$$U(x) = \sum_{n=1}^{\infty} u_n x^n. $$

From the identity $\displaystyle -\frac{\log(1-x)}{x} = \sum_{n=0}^{\infty} \frac{x^n}{n+1}$, it follows that

$$ -\frac{\log(1-x)}{x} U(x) = \sum_{n=1}^{\infty} \left( \sum_{k=1}^{n} \frac{u_k}{n+1-k} \right) x^n = \sum_{n=1}^{\infty} x^n = \frac{x}{1-x} $$

and hence

$$ U(x) = -\frac{x^2}{(1-x)\log(1-x)}. $$

Now let

$$ -\frac{x}{\log(1-x)} = 1 - \sum_{n=1}^{\infty} a_n x^n. $$

Then it is plain to confirm that

$$ u_n = 1 - \sum_{k=1}^{n-1} a_k. $$

Regarding the behavior of $(a_n)$, we claim the following assertions:

  1. $a_n > 0$ for all $n = 1, 2, 3, \cdots$ and
  2. $\sum a_n = 1$.

Once $a_n > 0$ is established, then the second assertion immediately follows. Indeed, the sum $\sum a_n$ tends to some limit in $[0, \infty]$. Then a simple version of Abelian theorems shows that

$$ \sum_{n=1}^{\infty} a_n = \lim_{x\to 1^-} \sum_{n=1}^{\infty} a_n x^n = \lim_{x\to 1^-} \left( 1 + \frac{x}{\log (1-x)} \right) = 1.$$

Thus it remains to prove the first assertion. Let

$$ f(x) = \frac{x-1}{\log x}. $$

Then it is easy to check that $f(x) \geq 0$ on $[0, \infty)$ and

$$ a_n = \frac{(-1)^{n-1}}{n!} f^{(n)}(1). $$

This shows that it suffices to check the condition $ (-1)^{n-1} f^{(n)}(x) > 0 $ for $x > 0$ and $n = 1, 2, 3, \cdots$. In other words, it is sufficient to show that $f$ is a Bernstein function. This follows once we show that

$$ f(s) = \int_{0}^{\infty} \left( -\int_{0}^{1}\frac{t^{u-2}}{(u-2)!} \, du \right) \left( 1 - e^{-st} \right) \, dt, \tag{1}$$

since the integrand is positive inside the domain of the integration. But this follows from the following calculation:

\begin{align*} \frac{s-1}{\log s} &= s \int_{0}^{1} \frac{du}{s^u} = s \int_{0}^{1} \frac{1}{\Gamma(u)} \int_{0}^{\infty} t^{u-1} e^{-st} \, dtdu \\ &= s \int_{0}^{\infty} \left( \int_{0}^{1} \frac{t^{u-1}}{\Gamma(u)} \, du \right) e^{-st} \, dt \\ &= \left[ \left( \int_{0}^{1} \frac{t^{u-1}}{\Gamma(u)} \, du \right) \left( 1 - e^{-st} \right) \right]_{0}^{\infty} - \int_{0}^{\infty} \left( \int_{0}^{1} \frac{t^{u-1}}{\Gamma(u)} \, du \right)' \left( 1 - e^{-st} \right) \, dt. \end{align*}

Now combining the two assertions and $(1)$, we have

\begin{align*} u_n = \sum_{k=n}^{\infty} a_k &= \sum_{k=n}^{\infty} \frac{(-1)^{k-1}}{k!} f^{(k)}(1) \\ &= \sum_{k=n}^{\infty} \int_{0}^{\infty} \int_{0}^{1} \frac{1-u}{\Gamma(u)} \frac{t^{u+k-2}}{k!} e^{-t} \, du \, dt \\ &= \int_{0}^{\infty} \int_{0}^{1} \frac{1-u}{\Gamma(u)} t^{u-2} \int_{0}^{t} \frac{v^{n-1}}{(n-1)!} e^{-v} \, dv \, du \, dt \\ &= \int_{0}^{\infty} \int_{0}^{1} \frac{t^{u+n-2}}{(n-1)!\Gamma(u)}e^{-t} \, du \, dt \\ &= \int_{0}^{1} \frac{\Gamma(u+n-1)}{(n-1)!\Gamma(u)} \, du \\ &= \int_{0}^{1} \prod_{k=1}^{n-1} \left( 1 - \frac{u}{k} \right) \, du. \end{align*}

Finally, heuristic calculation then suggests that

$$\lim_{n\to\infty} u_n \log n = 1, $$

which I'm trying to prove.


Start with the generating function

$$\sum_{n=1}^{\infty} u_n x^n = -\frac{x^2}{(1-x)\log(1-x)}$$

The coefficients of $u_{n+1}$ can be obtained by a contour integral around the origin:

$$u_{n+1} = \frac{1}{2\pi i}\int_{C} \frac{dx}{x^n(x-1)\log(1-x)}\tag{*}$$ In the integrand, there is a pole at $x = 1$ and a branch cut from $\log(1-x)$ over the interval $[1,\infty)$. If we deform the contour $C$ to start from $\infty - i\epsilon$, runs along bottom of the branch cut to the pole $x = 1$, walks around the pole clockwisely and then runs along top of the branch cut back to $\infty + i\epsilon$. We can convert $(*)$ to:

$$u_{n+1} = \frac{1}{2\pi i} \int_{1}^{\infty} \frac{dt}{t(1+t)^n}\left[\frac{1}{\log(t)-\pi i} - \frac{1}{\log(t)+\pi i}\right]$$

Let $ t = e^{\pi y}$, this can be simplified to: $$u_{n+1} = \frac{1}{\pi}\int_{-\infty}^{\infty} \frac{dy}{y^2 + 1} \left(\frac{1}{e^{\pi y}+1}\right)^n$$

For large $n$, the factor $\left(\frac{1}{e^{\pi y}+1}\right)^n$ sort of behaves like a step function. When $e^{\pi y} + 1$ is close to $1$, its value is about $1$, when $e^{\pi y} + 1$ differs from $1$, its value vanishes quickly. To the lowest order, we can approximate this factor as a step function $\theta(y_0 - y)$ where $y_0$ is chosen such that the factor becomes $\frac12$, i.e:

$$\left(\frac{1}{e^{\pi y_0} + 1}\right)^n = \frac12 \implies y_0 = \frac{\log(2^{\frac{1}{n}} - 1)}{\pi} \sim \frac{\log\log(2) - \log n}{\pi} $$

This leads to an approximation:

$$u_{n+1} \sim \frac{1}{\pi}\int_{-\infty}^{y_0} \frac{dy}{1 + y^2} = \frac{1}{\pi} \arctan( \frac{\pi}{\log n - \log\log 2} ) \tag{**}$$

The way of choosing $y_0$ still need to be justified. This means the offset $\log\log 2$ in $(**)$ may change under more rigorous treatment. However, $(**)$ alone seems to provide a very good approximation to $u_{n+1}$. Up to what I have tested ( $20 \le n \le 300$ ), the R.H.S for $(**)$ can reproduce the value of $u_{n+1}$ with a relative error less than 1 percent.

For large $n$, we once again obtain:

$$u_{n+1} \sim \frac{1}{\pi}\frac{\pi}{\log n - \log\log 2} \sim \frac{1}{\log n}$$

Same conclusion as everyone else.

  • $\begingroup$ I usually experience some sort of estranging whe I see a complex-analysis-based solution, but your solution is so appealing! I sense some flavor of analytic number theory, though I'm not sure of this feeling... $\endgroup$ – Sangchul Lee Mar 12 '13 at 12:42

Related problem: (I), (II). Here is a closed form formula for the $n$th derivative of the generating function

$$ U(x)=\frac{x^2}{(1-x)\ln(1-x)} $$

at $x=0$

$$ U^{(n)}(0) = (-1)^n\sum_{k=0}^{n} \left[\matrix{n\\k}\right]\frac{1+(-1)^{k+1}}{k+1}, $$

where $\left[\matrix{n\\k}\right]$ are Stirling numbers of the first kind. This allows us to construct the Taylor series of the generating function at the point $x=0$ as

$$ U(x)=\frac{x^2}{(1-x)\ln(1-x)}= \sum_{n=0}^{\infty}\sum_{k=0}^{n} \left[\matrix{n\\k}\right]\frac{1+(-1)^{k+1}}{k+1}\frac{(-x)^n}{n!}. $$

Now, it is clear what the closed form formula for $u_n$ is?


Once you accept sos440's integral formula, you can get the asymptotics of $u_n$ pretty easily. I think you could avoid the sinc function if necessary, but I like it.

Fix $0\leq u\leq 1$. The bounds $1-w^2\leq (1-w)\exp(w)\leq 1$ for $0\leq w\leq 1$, give
$$\prod_{k=1}^{n}\left(1-{u^2\over k^2}\right) \exp(-u H_{n}) \leq \prod_{k=1}^{n}\left(1-{u\over k}\right)\leq \exp(-u H_n),$$ where $H_n$ is the $n$th harmonic number. The infinite product expansion of the sinc function is $${\rm sinc}(\pi u)=\prod_{k=1}^{\infty}\left(1-{u^2\over k^2}\right),$$ so we have $${\rm sinc}(\pi u)\exp(-u H_n)\leq\prod_{k=1}^{n}\left(1-{u\over k}\right)\leq\exp(-u H_n).\tag1$$

Setting $u_{n+1}=\int_0^1 \prod_{k=1}^{n}\left(1-{u\over k}\right)\,du$, using the bounds (1) and a change of variables gives

$$\int_0^{H_n} {\rm sinc}(\pi w/H_{n}) \exp(-w)\,dw \leq H_n u_{n+1} \leq \int_0^{H_n} \exp(-w)\,dw,$$ and since the sinc function is bounded, continuous, and takes the value 1 at zero, using monotone convergence we conclude that $H_n u_{n+1} \to1$. In other words, $u_n\sim 1/\log(n)$.

  • $\begingroup$ Oh, introducing the sinc function was my last missing ingredient! I also made a similar calculation, but it lacked a precise description for the lower bound, hence remained as a mere heuristics. +1 upvote! $\endgroup$ – Sangchul Lee Mar 12 '13 at 3:06
  • 1
    $\begingroup$ @sos440 Glad to help. I was playing around with the sinc function this weekend, so it was on my mind. $\endgroup$ – user940 Mar 12 '13 at 3:15
  • $\begingroup$ I suppose we have $u_n \sim 1/log(n)$ at the end. Thank you very much for this answer. $\endgroup$ – user66240 Mar 12 '13 at 10:51
  • $\begingroup$ @user66240 Whoops! Thanks for pointing out my mistake. $\endgroup$ – user940 Mar 12 '13 at 12:05
  • $\begingroup$ Nice and clear derivations. $\endgroup$ – Mhenni Benghorbal Mar 12 '13 at 13:40

Change the recurrence to: $$ u_{n} = 1 - \sum_{0 \le k < n} \frac{u_k}{n - k + 1} \qquad u_0 = 0 $$ This also gives $u_1 = 1$ and simplifies some of the following.

Define the ordinary generating function $U(z) = \sum_{n \ge 0} u_n z^n$. By properties of the generating functions, as the sum is the convolution of the secuence $\langle \frac{1}{n + 1} \rangle$ and $\langle u_n \rangle$, and: $$ \sum_{n \ge 0} \frac{z^n}{n + 1} = - \frac{\ln (1 - z)}{z} $$ this gives: $$ \begin{align*} U(z) &= \frac{1}{1 - z} + U(z) \frac{\ln(1 - z)}{z} \\ U(z) &= -\frac{z}{z^2 - z(\ln (1 - z) + 1) + \ln(1 - z)} \end{align*} $$ Update

The denominator factors nicely: $$ U(z) = - \frac{z}{(1 - z) (\ln (1 - z) - z)} $$ This has simple poles at 0 and at 1.

  • 1
    $\begingroup$ Comparing with the actual values of the sequence (obtained by Mathematica, by solving the given system of equations directly) shows that your power series does not agree with the sequence. I think you unwittingly made a mistake when dealing with the Cauchy product of $u_n$ and $1/(n+1)$. $\endgroup$ – Sangchul Lee Mar 12 '13 at 3:09

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.