Asymptotics on a heriditary recursion

1.   Introduction

To the evaluation of sequences, which may be divergent, asymptotic expansions provide a way to compute sequences with arbitrarily high accuracy ^[4,11,12,17]. Many researchers have studied asymptotics of partial sums and related inequalities. One of the most famous examples is the harmonic sum ^[10,15], which has an asymptotic estimate

where $\gamma = \lim _{n \rightarrow \infty}\left(H_n-\ln n\right) = 0.577 \ldots$ is the constant of Euler and $\varepsilon_n \rightarrow 0$. Zhu ^[20] calculated the asymptotic expansion of the finite sum of some sequences

Other well-known examples of asymptotic formulas include the Euler–Maclaurin formula ^[12], the Euler–Boole type summation formula ^[6] and the prime number theorem ^[1]. Grünberg ^[7] applied the Euler–Maclaurin formula to obtain the asymptotic expansions of the sums,

in closed form to arbitrary order $(p, q\in\mathbb{N})$. Wang and Wong ^[16] carried out the asymptotic estimation of the partial sum $\sum_{k = 0}^n f_n(k) q^{g_n(k)}$. Xu ^[19] provided an estimate for the partial sum

Blagouchine and Moreau ^[2] derived the complete asymptotic expansion of the finite sum

Some researchers have also given asymptotic estimates for some recurrences in combinatorial mathematics and algorithms. For example, Xu ^[18,19] studied the asymptotic series of the generalized Somos recurrence. Hwang, Janson, and Tsai ^[9] gave exact and asymptotic solutions of a divide-and-conquer recurrence. Heuberger, Krenn, and Lipnik ^[8] presented some asymptotic analysis of $q$-recursive sequences.

However, due to computational complexity and lack of tools or methods, very few papers have investigated asymptotic expansions of heriditary recursions (refer to [5, Section 6.3, p. 291]). Recently, Popa ^[13] investigated a heriditary recursion

where $f:(a, \infty) \rightarrow (0, \infty)$ and $a < 0$. He gave the first five terms of the asymptotic expansion of $\left(x_n\right)_{n \geq 1}$. The aim of this paper is to study the generalized form

where $s > 1$. Using only elementary techniques, we establish an asymptotic estimate of $\left(x_n\right)_{n \geq 1}$ in (1.1). We obtain an asymptotic sequence for the case $s > 1$ that is quite different from the case $s = 1$. Some examples and applications are provided.

2.   Preliminaries

In this section we first introduce the Euler–Maclaurin formula (see ^[3,6,14]), from which asymptotic expansions of many sequences and sums can be derived.

Lemma 2.1 (Euler–Maclaurin formula). Suppose $f$ is $k$-times continuously differentiable on the interval $[a, b]$ with $a < b, a, b \in \mathbb{Z}$. Then

Suppose $f$ and all its derivatives go to zero as $x \rightarrow \infty$. Then we obtain by letting $b \rightarrow \infty$ (and adding $f(a)$ to both sides),

where $B_{\ell}(x)$'s are Bernoulli polynomials, $B_{\ell} = B_{\ell}(0)$'s are Bernoulli numbers, and $\psi_k(x) = B_{k}(\{x\})$.

For convenience, let $(k-1)_{i}$ be Pochhammer's symbol defined as

Put $c_{i}(\alpha) = \dfrac{(\alpha-1)_{i}}{i!}$.

For $\alpha > 1$, let $\zeta(\alpha)$ denote the Riemann zeta function, namely,

In order to compute the asymptotic expansion, we need the following asymptotic estimate of sums and sequences.

Lemma 2.2. Let $\alpha > 1$. Then

(i)

(ii)

(iii)

where $c_{i}(\alpha) = \dfrac{(\alpha-1)_{i}}{i!}$.

Proof. (ⅰ) By the Euler–Maclaurin formula, $f(k) = \dfrac{1}{k^{\alpha}}$, $\alpha > 1$, we obtain

(ⅱ) It is clear that

Then the result (ⅱ) immediately follows from (ⅰ).

(ⅲ) Using the Maclaurin series $(1+x)^{\beta} = 1+\binom{\beta}{1}x+\binom{\beta}{2}x^{2}+o(x^{2})$, we have

□

3.   Main results

We first give some asymptotic estimates of the sequence $\left(x_n\right)_{n \geq 1}$, which is defined by (1.1).

Lemma 3.1. Suppose that the sequence $\left(x_n\right)_{n \geq 1}$ is defined by (1.1), $f$ is decreasing, continuous on $(a, \infty)$, $a < 0$, and twice differentiable at $0$ with a Taylor series $f(x) = f(0)+f^{\prime}(0)x+f^{\prime\prime}(0)x^2+o(x^2)$. Then the following results hold:

${\rm (i)}$$\lim\limits_{n\to\infty}x_{n} = 0$,

${\rm (ii)}$$\lim\limits_{n\to\infty}n^{s-1}x_{n} = f(0)$,

${\rm (iii)}$ the finite sum

Proof. (ⅰ) Since $f$ takes positive real numbers, we get $x_{n} > 0$ for all $n\geq 2$. Since the inequality $\dfrac{x_{k}}{k} > 0$ for all $k\geq 2$ and $f$ is decreasing, we get $f\Big(\dfrac{x_{k}}{k}\Big)\leq f(0)$, and

We deduce that for every $n\geq 1$

Since $s > 1$, it follows from the squeeze theorem that $\lim_{n\to\infty} x_{n} = 0$.

(ⅱ) Moreover, by (ⅰ), we have $\lim_{n\to\infty} x_{n}/n = 0$. From the Stolz–Cesàro theorem, and the continuity at $0$, we obtain

Let $n\geq 2$. It follows from (1.1) that $x_{n} = \dfrac{1}{(n-1)^{s}}\mathop {\mathop \sum \limits_{k = 1} }\limits^{n - 1} f\Big(\dfrac{x_{k}}{k}\Big)$. Then

(ⅲ) Since $f$ is differentiable at $0$, we have

It follows from (ii) and $f(x) = f(0)+f^{\prime}(0)x+f^{\prime\prime}(0)x^2+o(x^2)$ that

By Lemma 2.2 (ⅱ), we have

□

The following theorem gives the first three terms of the asymptotic expansion of $x_n$.

Theorem 3.1. Suppose that the sequence $\left(x_n\right)_{n \geq 1}$ is defined by (1.1), $f$ is decreasing, continuous on $(a, \infty)$, $a < 0$, and twice differentiable at $0$ with a Taylor series $f(x) = f(0)+f^{\prime}(0)x+f^{\prime\prime}(0)x^2+o(x^2)$. Then there exists a constant $C\in \mathbb{R}$ such that

Moreover, the sequence $\left(x_n\right)_{n \geq 1}$ of (1.1) has the following asymptotic expansion:

Proof. For every $n\geq 2$, we have

From Lemma 2.2 (ⅲ) and Lemma 3.1 (ⅲ), we can obtain

It follows that

This completes the proof. □

The following theorem gives the first four terms of the asymptotic expansion.

Theorem 3.2. Suppose that the sequence $\left(x_n\right)_{n \geq 1}$ is defined by (1.1), $f$ is decreasing, continuous on $(a, \infty)$, $a < 0$, and twice differentiable at $0$ with a Taylor series $f(x) = f(0)+f^{\prime}(0)x+f^{\prime\prime}(0)x^2+o(x^2)$. Let $C$ be defined by Theorem 3.1. Then the sequence $\left(x_n\right)_{n \geq 1}$ of (1.1) has the following asymptotic expansion:

${\rm (i)}$ If $1 < s < 2$, then

${\rm (ii)}$ If $s = 2$, then

${\rm (iii)}$ If $s > 2$, then

Proof. From Lemma 2.2 (ⅲ) and Lemma 3.1 (ⅲ), we deduce that

Case 1. Let $1 < s < 2$. Then $2s-1 < s+1$, and

Thus

Case 2. Let $s = 2$. Then $2s-1 = s+1 < 2s$, and

where $D = c_2f(0)- \frac{1}{(s-1)}$. Thus

Case 3. Let $s > 2$. Then $s+1 < 2s-1 < 2s$. Hence, we have

□

Below is our main theorem, which gives the first five terms of the asymptotic expansion.

Theorem 3.3. Suppose that the sequence $\left(x_n\right)_{n \geq 1}$ is defined by (1.1), $f$ is decreasing, continuous on $(a, \infty)$, $a < 0$, and twice differentiable at $0$ with a Taylor series $f(x) = f(0)+f^{\prime}(0)x+f^{\prime\prime}(0)x^2+o(x^2)$. Let $C$ be defined by Theorem 3.1. Then the sequence $\left(x_n\right)_{n \geq 1}$ of (1.1) has the following asymptotic expansion:

${\rm (i)}$ If $1 < s < 2$, then

${\rm (ii)}$ If $s = 2$, then

${\rm (iii)}$ If $2 < s < 3$, then

${\rm (iv)}$ If $s = 3$, then

${\rm (v)}$ If $s > 3$, then

Proof. Case 1. Let $1 < s < 2$. Then $2s-1 < s+1 < 2s$. By Lemma 2.2 and Lemma 3.1, we have

Thus

Case 2. Let $s = 2$. Then $s+2 = 2s$, and

where

Case 3. Let $2 < s < 3$. Then $s+1 < 2s-1 < s+2 < 2s$, and

Case 4. Let $s = 3$. Then $2s-1 = s+2 < 2s$, and

where

Case 5. Let $s > 3$. Then $s+2 < 2s-1 < 2s$, and

□

4.   Some examples

In this section, we give some applications of our results to several specific examples and a comparison with Popa's results.

Example 4.1. Let $(x_{n})_{n\geq1}$ be a sequence of the real numbers defined by

Note that $f(x) = e^{-x}$ and $f(0) = 1$.

When $s = \frac{3}{2}$, it follows from Theorem 3.3 (i) that $\underset{n\to\infty}{\lim}x_{n} = 0$. Moreover,

When $s = 1$, it follows from in [13, Theorem 5] that

since $f^{\prime}(0) = -1$.

This example corrects some printing errors in [13, Corollary 6]. And it is easy to see that when $s > 1$, the asymptotic sequence for the case $s > 1$ is completely different from the case $s = 1$.

Example 4.2. Let $(x_{n})_{n\geq1}$ be a sequence of the real numbers defined by $x_{1} > 1-e^{2}$ and

Note that $f(x) = \frac{1}{\ln (e^2+x)}$, and $f(0) = \dfrac{1}{2}$.

When $s = \frac{3}{2}$, by Theorem 3.3 (i), we have $\underset{n\to\infty}{\lim}x_{n} = 0$, and

When $s = 4$, by Theorem 3.3 (v), we have $\underset{n\to\infty}{\lim}x_{n} = 0$, and

5.   Conclusions

Our analysis shows that this heriditary recursion can be further expanded according to the residual terms. By comparing asymptotic sequences, depending on the value of $s$, more and more terms of the asymptotic expansion are obtained.

Our results show that, for the case $s > 1$, Eq (1.1) has the asymptotic expansion of the form

while, for the case $s = 1$, Eq (1.1) has the asymptotic expansion of the form

where $q_j \in[0, \infty), p_j \in \mathbb{R}$ and where some of the constants $a_j$ may depend on the initial values.

Author contributions

Yong-Guo Shi: writing original draft, methodology, proof of conclusions; Xiaoyu Luo: writing original draft, methodology, proof of conclusions; Zhi-jie Jiang: validation, writing review, editing, proof of conclusions. The authors contributed equally to this work. All the authors have read and approved the final version of the manuscript for publication.

Acknowledgments

We would like to thank the reviewers for having read this manuscript very carefully and for their many constructive and valuable comments, which have enhanced the final version of this paper.

Funding

Yong-Guo Shi is supported by NSF of Sichuan Province (2023NSFSC0065). Xiaoyu Luo is Supported by The Innovation Fund of Postgraduate, Sichuan University of Science & Engineering.

Conflict of interest

The authors declare no conflicts of interest.