오늘의 계산 52 - Asymptotic Behavior of a Sqeuence

이번 계산에서는, 마지막 부분에 제가 깔끔하게 처리하지 못한 부분을 다른 분의 도움을 얻어 깔끔하게 처리해보았습니다. 어떤 분은 복소로 풀어내기도 했는데, 이 풀이 역시 상당히 마음에 와닿더군요.

Problem. Let $(u_n)$ be the sequence defined by \begin{equation} \label{eqn:recur} \frac{u_1}{n} + \frac{u_2}{n-1} + \cdots + \frac{u_{n-1}}{2} + u_n = 1. \end{equation} Find the asymptotic behavior of $u_n$.

Solution. We introduce the generating function $U(x)$ of $(u_n)$ given by

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

From the Taylor expansion

$$-\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 we obtain the explicit formula for $U(x)$ as follows:

\begin{equation} \label{eqn:u_1} U(x) = -\frac{x^2}{(1-x)\log(1-x)}. \end{equation}

To analyze the behavior of $u_n$, we introduce the sequence $(a_n)$ defined by

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

Then it is plain from \eqref{eqn:u_1} that

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

Now, 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$.

Note that once $a_n > 0$ is established, the second assertion also 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

\begin{equation} \label{eqn:a_1} f(s) = \int_{0}^{\infty} \left( -\int_{0}^{1}\frac{t^{u-2}}{(u-2)!} \, du \right) \left( 1 - e^{-st} \right) \, dt, \end{equation}

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*}

Combining the two assertions and \eqref{eqn:a_1}, we obtain the following integral representation formula.

\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*}

From now on, we adopt Byron Schmuland's proof that $u_n$ satisfies the following asymptotic behavior:

\begin{equation} \label{eqn:asymp} \lim_{n\to\infty} u_n \log n = 1. \end{equation}

To this end we make the following easy observation.

$$ 1 - w^2 \leq (1 - w)e^w \leq 1, \quad 0 \leq w \leq 1. $$

Plugging $w = u/k$ for $k = 1, \cdots, n$ and $0 \leq u \leq 1$ and multiplying termwise, we obtain

$$ e^{-u H_n} \prod_{k=1}^{n} \left( 1 - \frac{u^2}{k^2} \right) \leq \prod_{k=1}^{n} \left( 1 - \frac{u}{k} \right) \leq e^{-u H_n}. $$

By recalling that

$$ \mathrm{sinc}(\pi x) = \frac{\sin \pi x}{\pi x} = \prod_{k=1}^{\infty} \left( 1 - \frac{x^2}{k^2} \right), $$

it follows that

$$ e^{-u H_n} \mathrm{sinc} (\pi u) \leq \prod_{k=1}^{n} \left( 1 - \frac{u}{k} \right) \leq e^{-u H_n}. $$

Thus by our integral representation formula for $(u_n)$, we obtain

$$ \int_{0}^{H_n} e^{-w} \mathrm{sinc} \left( \frac{\pi w}{H_n} \right) \, dw \leq u_{n+1} H_n \leq \int_{0}^{H_n} e^{-w} \, dw. $$

Taking $n \to \infty$, dominated convergence yields the desired equality \eqref{eqn:asymp}, together with the fact that $H_n \sim \log n$.

References

1. Solve the sequence: $u_n = 1-(\frac{u_1}{n} + \frac{u_2}{n-1} + \ldots + \frac{u_{n-1}}{2})$ in "Math StackExchange"