On Certain Reciprocal Sums

Soumyadip Sahu School of Mathematics Tata Institute of Fundamental Research Mumbai 400005 India

                  soumyadip.sahu00@gmail.com

Abstract

We use tail sums of convergent series of positive real numbers to define a sequence of non-negative integers, and explicitly determine this sequence for classes of series defined by reciprocal sums of polynomials and rational functions. For this purpose we develop a new difference calculus method to approximate infinite series.

1 Introduction

Let (x_{m})_{m=1}^{∞} be a sequence of positive real numbers satisfying ∑_{m=1}^{∞} x_{m} < ∞. With (x_{m})_{m≥1} one associates a sequence of non-negative integers (a_{n})_{n=1}^{∞} by defining

a_{n} = ⌊\frac{1}{∑_{m=n}^{∞} x_{m}} ⌋ (n ≥ 1),

where ⌊.⌋ is the floor function. We call (a_{n})_{n=1}^{∞} the reciprocal sequence of (x_{m})_{m=1}^{∞}. The sequence (a_{n})_{n=1}^{∞} is non-decreasing and divergent. Reciprocal sequences capture the rate of convergence of their defining series, and sometimes give rise to nice arithmetic and combinatorial structures. One can replace the floor function by the ceiling function or nearest integer function, and create variants of this notion.

Many authors have already studied reciprocal sequence of sequences defined by reciprocals of linear recurrence. Ohtsuka and Nakamura [4] derived a formula for reciprocal sequence of

x_{m} = \frac{1}{F_{m}} (m ≥ 1),

where F_{m} is the m^{th} Fibonacci number. Ramifications and generalizations of this result appear in several places, e.g., [3, 2]. Some papers have investigated the problem beyond reciprocals of linear recurrence relation. Reciprocal sequences of (\frac{1}{m^{4}} )_{m≥1} and (\frac{1}{m^{5}} )_{m≥1} are recorded in sequences \underline{A248230}, \underline{A248234} respectively. Xin [6] and Xu [7] studied reciprocal sequences of

x_{m} = \frac{1}{m^{k}} (m ≥ 1)

for k = 2, 3, 4, 5. They showed that reciprocal sequences of these sequences are given by polynomials or polynomial like functions (for precise formulas see Section 4.3.2). In present article we extend results of Xin and Xu to general classes of sequences arising from reciprocals of polynomials and rational functions.

Let 𝕂 be a subfield of ℝ. It is sufficient to consider 𝕂 = ℝ, ℚ for the purposes of this article. Suppose that P (X) ∈ 𝕂[X] is a polynomial of degree k ≥ 2 with positive leading coefficient. Now ℚ is a subfield of 𝕂 and 𝕂 is dense in ℝ with respect to Euclidean topology. Hence there exists M_{0} ∈ 𝕂 so that P (x) > 0 for all real x ≥ M_{0} + 1. For fixed choice of such M_{0}, define a sequence of positive real numbers by

x_{m} = \frac{1}{P (m + M_{0})} (m ≥ 1).  (1)

Since k ≥ 2 we have ∑_{m≥1} x_{m} < ∞. To calculate terms of reciprocal sequence of (x_{m})_{m≥1} one needs to estimate sums of the form

∑_{m=n}^{∞} \frac{1}{P (m + M_{0})}.  (2)

The standard way to approximate sums of this form is to apply summation formulas from analysis (e.g., the Euler-Maclaurin summation formula [1, p. 806]). For reciprocal power sums, i.e., P (X) = X^{k} and M_{0} = 0, a precise estimate of (2) is readily available from the asymptotic expansion of the polygamma function [1, p. 260]. Though these summation formulas produce estimates up to higher order, they often lead to complicated computations and problems regarding convergence.

The goal of this paper is to present an improvised technique based on difference calculus, which bypasses analytic tools and provides a good upper bound as well as a lower bound for (2). The central idea behind our method is to find a suitable polynomial f so that the rational function \frac{1}{P (X)} is approximately equal to \frac{1}{f(X)} − \frac{1}{f(X+1)}, i.e., \frac{1}{f(X)} acts like the difference primitive of −\frac{1}{P (X)}. Once we have determined f, bounds on (2) simply follow by telescoping. This strategy bears resemblance to the methods employed by Xin [6] and Xu [7].

Though the technique looks naive and insufficient, it turns out to be powerful enough to calculate the first k − 1 terms in the asymptotic series of (2). Our main result is as follows:

Theorem 1. Let (x_{m})_{m≥1} be the sequence defined by (1). There exists a polynomial h(X) ∈ 𝕂[X] of degree k − 1 and a positive integer N_{0} depending on h such that

0 < h(n) ≤ \frac{1}{∑_{m=n}^{∞} x_{m}} < h(n) + 1 (n ≥ N_{0}).  (3)

Moreover, h is algorithmically computable and uniquely determined by P (X) and M_{0} up to a constant term.

The leftmost inequality in (3) implies that leading coefficient of h is positive. Now (3) can be restated as

0 < \frac{1}{h(n) + 1} < ∑_{m=n}^{∞} \frac{1}{P (m + M_{0})} ≤ \frac{1}{h(n)} (n ≥ N_{0}).  (4)

Note that \frac{1}{h(n)} − \frac{1}{h(n)+1} = \frac{1}{h(n)(h(n)+1)} = O(n^{−2k+2}) and \frac{1}{h(n)}, \frac{1}{h(n)+1} are of O(n^{−k+1}). Hence

∑_{m=n}^{∞} \frac{1}{P (m + M_{0})} = \frac{1}{h(n)} + O(n^{−2k+2}) (n ≥ N_{0}).

Thus we obtain an estimate such that the main term is O(n^{−k+1}) and error term is O(n^{−2k+2}). This improvement is due to a formulation as a fractional expression that resembles the classical Padé approximants. Therefore, Theorem 1 turns out to be a more convenient approximation technique than the usual summation formulas, and one can directly obtain the first k −1 terms of the asymptotic expansion for suitably large n, as explained in Section 4.2.

We can use Theorem 1 to deduce estimates for classical reciprocal power sums.

Corollary 2. Let k be an integer ≥ 2. There is a polynomial h(X) ∈ ℚ[X] of degree k − 1 and a positive integer N_{0} depending on h such that

0 < h(n) ≤ \frac{1}{∑_{m=n}^{∞} m^{−k}} < h(n) + 1 (n ≥ N_{0}).

Moreover, h is algorithmically computable and unique up to a constant term.

Theorem 1 allows us to study sequences defined by rational functions. Let P (X), Q(X) ∈ 𝕂[X] be two nonzero polynomials with positive leading coefficients such that deg_{𝕂}P − deg_{𝕂}Q = k ≥ 2. Set R(X) = \frac{P (X)}{Q(X)} ∈ 𝕂(X). Here R(X) determines k and it is independent of presentation. Since P and Q have positive leading coefficients, there is an M_{0} ∈ 𝕂 so that P (x), Q(x) > 0 for all real numbers x ≥ M_{0} + 1. For fixed choice of M_{0}, consider the sequence

x_{m} = \frac{1}{R(m + M_{0})} (m ≥ 1).  (5)

As before ∑_{m≥1} x_{m} < ∞. We have

0 < h(n) ≤ \frac{1}{∑_{m=n}^{∞} x_{m}} < h(n) + 1 (n ≥ N_{0}).  (6)

Moreover, h is algorithmically computable and uniquely determined by R(X) and M_{0} up to a constant term.

Observe that if Q(X) = 1, then Theorem 3 reduces to Theorem 1. Though Theorem 3 is a generalization of Theorem 1, it follows easily from the earlier one. We prove both the theorems in Section 3. Theorem 3 also offers a convenient asymptotic expression, as described in paragraphs above. More discussion about this point is postponed to Section 4.2.

It is clear from Theorem 3 that the n-th term of the reciprocal sequence of (5) is either ⌊h(n)⌋ or ⌊h(n)⌋ + 1. We pin down the exact expression of the reciprocal sequence if P and Q have coefficients in ℚ, by carefully choosing constant term of h. This procedure and its arithmetic aspects are described in Section 4.1.

1.1 Notation and conventions

The symbols ℕ, ℤ, ℝ, ℂ have their conventional meaning. In our convention 0 ∉ ℕ and the set of nonnegative integers is ℤ_{≥0}. We index sequences by ℕ.

Let 𝕂 be a field. Then 𝕂^{×} = 𝕂−{0} and 𝕂[X] is the ring of polynomials with coefficients in 𝕂. Also 𝕂(X) is the field of rational functions. If there is more than one variable, we use a boldface symbol to denote a tuple, e.g., X = (X_{1}, …, X_{n}). For a fixed integer d ≥ 0, there is a bijection between 𝕂^{×} × 𝕂^{d} and 𝕂[X]_{d}, subset polynomials of degree d, given by ι_{d} : (a_{0}, …, a_{d}) → a_{0}X^{d} + ⋯ + a_{d}. Here, by convention, 𝕂^{×} × 𝕂^{0} = 𝕂^{×}. The degree of the zero polynomial is −∞. If P is a polynomial with coefficients in ℝ, then

sgn P = \begin{cases}0, & if P = 0; \\ 1, & if the leading coefficient of P is positive; \\ −1, & if the leading coefficient of P is negative. \end{cases}

We write ⌊.⌋, ⌈.⌉ for the floor and ceiling functions, respectively. A statement S(n) concerning natural numbers holds for ‘n ≫ 1’ if there exists a real number C (depending on S) so that S(n) is true for all n ≥ C.

2 Approximate difference primitive

We begin by introducing some preliminary concepts necessary to define approximate difference primitives. The main result of this section is the existence of canonical approximants satisfying definite requirements. Our arguments are algebraic in nature, and most of the conclusions are valid even in a formal situation, which is briefly mentioned at the end of section.

Let 𝕂 be a field of characteristic 0 and k be an integer ≥ 2. Suppose that g(X) ∈ 𝕂[X]_{k}. Write

g(X) = a_{0}X^{k} + ⋯ + a_{k}.  (7)

Here (a_{0}, …, a_{k}) is the unique point in 𝕂^{×} × 𝕂^{k} which corresponds to g(X) under ι_{k}. Now f(X) ∈ 𝕂[X] be a nonzero polynomial such that \frac{1}{f(X)} is a difference primitive of −\frac{1}{g(X)}, i.e., \frac{1}{g(X)} = \frac{1}{f(X)} − \frac{1}{f(X+1)} holds in 𝕂(X). Then

f(X)f(X + 1) = g(X)(f(X + 1) − f(X)).  (8)

Suppose deg_{𝕂}f = d. Since the left-hand side of (8) is not zero, we have d ≥ 1. Comparing the degrees of both sides gives d = k − 1.

Let x_{0}, x_{1}, …, x_{k−1} be k unknowns. Set

F (X, x) = x_{0}X^{k−1} + ⋯ + x_{k−1} ∈ ℤ[X, x_{0}, …, x_{k−1}].

With each c = (c_{0}, …, c_{k−1}) ∈ 𝕂^{×} × 𝕂^{k−1} one associates F (X, c) ∈ 𝕂[X]_{k−1}. Using (8) we see that \frac{1}{F (X,c)} is a difference primitive of −\frac{1}{g(X)} if and only if

F (X + 1, c)F (X, c) = g(X)(F (X + 1, c) − F (X, c)).

To solve the equation above, one defines a collection of polynomials

{y_{i}(x), u_{j}(x), v_{l}(x, g) | 1 ≤ i ≤ k − 1, 0 ≤ j, l ≤ 2k − 2} ⊆ 𝕂[x_{0}, …, x_{k−1}]

by the relations

F (X + 1, x) = x_{0}X^{k−1} + (x_{1} + y_{1}(x))X^{k−2} + ⋯
⋯ + (x_{k−2} + y_{k−2}(x))X + (x_{k−1} + y_{k−1}(x)),  (9)
H(X, x) = F (X + 1, x)F (X, x)
= u_{0}(x)X^{2k−2} + ⋯ + u_{2k−3}(x)X + u_{2k−2}(x),  (10)
G(X, x, g) = g(X)(F (X + 1, x) − F (X, x))
= v_{0}(x, g)X^{2k−2} + ⋯ + v_{2k−3}(x, g)X + v_{2k−2}(x, g).  (11)

The coefficient of X^{k−1} in F (X + 1, x) is x_{0} and the degrees of H(X, x), G(X, x, g) in X are at most 2k − 2. Therefore, the equations above are justified. Note that the polynomials {y_{i}(x), u_{j}(x) | 0 ≤ i ≤ k − 1, 0 ≤ j ≤ 2k − 2} are independent of g and defined over ℤ[x_{0}, …, x_{k−1}].

As a consequence of the binomial theorem

y_{i}(x) = \binom{k − i}{1}x_{i−1} + \binom{k − i + 1}{2}x_{i−2} + ⋯ + \binom{k − 1}{i}x_{0}  (12)

for all 1 ≤ i ≤ k − 1. For convenience put y_{0}(x) = y_{k}(x) = 0.

Equation (9), (10), and (11) together imply that

u_{j}(x) = ∑_{r=0}^{j} x_{r}(x_{j−r} + y_{j−r}(x)) (0 ≤ j ≤ k − 1),  (13)

v_{l}(x, g) = ∑_{r=0}^{l} a_{r}y_{l−r+1}(x) (0 ≤ l ≤ k − 1).  (14)

Subtracting (10) from (11) gives

G(X, x, g) − H(X, x) = ∑_{i=0}^{2k−2}(v_{i}(x, g) − u_{i}(x))X^{2k−2−i}.  (15)

To construct an approximate difference primitive we need to find a point (c_{0}, …, c_{k−1}) ∈ 𝕂^{k} so that the first few coefficients in (15) vanish at the point (c_{0}, …, c_{k−1}). But for generic (a_{0}, …, a_{k}), one cannot expect to find a common zero of all the coefficients. Moreover, we would like to have c_{0} ≠ 0, so that F (X, c_{0}, …, c_{k−1}) is actually of degree k − 1. These considerations lead to a formal definition.

2.1 Good approximants

Let f(X) ∈ 𝕂[X] be a nonzero polynomial. Set

δ(f, g, X) := \frac{1}{f(X)} − \frac{1}{f(X + 1)} − \frac{1}{g(X)},  (16)
N(f, g, X) := g(X)(f(X + 1) − f(X)) − f(X + 1)f(X).  (17)

A good approximant of g is a polynomial f ∈ 𝕂[X]_{k−1} so that N(f, g, X) is a polynomial of degree ≤ k − 1.

Note that

δ(f, g, X) = \frac{N(f, g, X)}{f(X)f(X + 1)g(X)}  (18)

and N(f, g, X) = 0 if and only if \frac{1}{f(X)} is a difference primitive of −\frac{1}{g(X)}.

The following lemma ensures existence of a canonical good approximant:

Lemma 4. Let k ≥ 2 and g ∈ 𝕂[X]_{k}. Consider the system of k equations

u_{i}(x) = v_{i}(x, g) (0 ≤ i ≤ k − 1)  (19)

in k unknowns x_{0}, …, x_{k−1}. The system of equations (19) has a unique solution in 𝕂^{×}×𝕂^{k−1}, i.e., there is a unique tuple (c_{0}(g), …, c_{k−1}(g)) ∈ 𝕂^{k} with c_{0}(g) ≠ 0, which is a solution to the system of equation (19).

Proof. To fix notation, assume that g is given in the form (7). This polynomial remains fixed throughout the discussion, and we omit it from the notation. Now u_{i} depends on {x_{0}, …, x_{i}, y_{0}, …, y_{i}}. Using (12), one concludes that the set of variables appearing in u_{i} is {x_{0}, …, x_{i}}. Similarly, v_{i} depends on {y_{1}, …, y_{i+1}}, i.e., on {x_{0}, …, x_{i}}. These statements hold for all 0 ≤ i ≤ k − 1. Therefore one can use a recursive approach to solve the system of equations.

Let 0 ≤ i ≤ k − 1 and consider subsystems of i + 1 equations

u_{0} = v_{0}, …, u_{i} = v_{i}  (20)

in i + 1 variables x_{0}, …, x_{i}. We would like to show that (20) has unique solution in 𝕂^{×} × 𝕂^{i} for each 0 ≤ i ≤ k − 1.

For the base case, consider the equation u_{0}(x_{0}) = v_{0}(x_{0}). We have u_{0} = x_{0}^{2}, and v_{0} = y_{1} = a_{0}\binom{k−1}{1}x_{0} = a_{0}(k − 1)x_{0}. Now a_{0}(k − 1) ≠ 0 and it is the only nonzero solution to u_{0} = v_{0}. Put c_{0} = a_{0}(k − 1).

Assume that the statement holds for some 0 ≤ i ≤ k − 2, i.e., there is a unique solution to (20) in 𝕂^{×} × 𝕂^{i}. Note that the first coordinate of this solution is necessarily c_{0}. Let the unique solution be (c_{0}, …, c_{i}). We now construct c_{i+1} ∈ 𝕂 so that (c_{0}, …, c_{i}, c_{i+1}) is the unique solution of u_{i+1} = v_{i+1} in 𝕂^{×} × 𝕂^{i+1}. In what follows, we consider u_{i+1} and v_{i+1} as polynomials of x_{i+1} with coefficients in 𝕂[x_{0}, …, x_{i}]. Equation (13) and (14) together imply that u_{i+1}, v_{i+1} are linear in the variable x_{i+1}.

There are two possibilities.

2.1.1 Case I: i < k − 2

Here i + 1 ≤ k − 2. From (13) and (14) we deduce that coefficient of x_{i+1} in u_{i+1} is 2x_{0} (one x_{0} arises from term x_{0}(x_{i+1} +y_{i+1}) and other x_{0} arises from the term x_{i+1}(x_{0} +y_{0})). Similarly coefficient of x_{i+1} in v_{i+1} is a_{0} times coefficient of x_{i+1} in y_{i+2}, i.e., a_{0}\binom{k−i−2}{1} = a_{0}(k − i − 2).

Hence u_{i+1} = v_{i+1} can be rewritten as

(2x_{0} − a_{0}(k − i − 2))x_{i+1} = a polynomial in x_{0}, …, x_{i} over 𝕂.  (21)

But (2c_{0} − a_{0}(k − i − 2)) = a_{0}(k + i) ≠ 0. Therefore we can substitute x_{0} = c_{0}, …, x_{i} = c_{i} in (21) and solve for x_{i+1} to get a tuple (c_{0}, …, c_{i+1}) ∈ 𝕂^{i+2} that is a solution to the system of equations

u_{0} = v_{0}, …, u_{i+1} = v_{i+1}.

If (C_{0}, …, C_{i+1}) is another solution with C_{0} ≠ 0 then by recursion hypothesis (c_{0}, …, c_{i}) = (C_{0}, …, C_{i}). Using (21) we have C_{i+1} = c_{i+1}. Hence the uniqueness. So for i < k − 2 a solution to the first i + 1 equations of (19) in 𝕂^{×} × 𝕂^{i} extends to a unique solution to the first i + 2 equations in 𝕂^{×} × 𝕂^{i+1}.

2.1.2 Case II: i = k − 2

This case is essentially similar to Case I. Here coefficient of x_{k−1} in v_{k−1} is 0. Now u_{k−1} = v_{k−1} can be rewritten as

2x_{0}x_{k−1} = a polynomial in x_{0}, …, x_{k−2} over 𝕂.

Since c_{0} ≠ 0, the arguments of the previous case go through to yield a unique tuple (c_{0}, …, c_{k−1}) that is a solution to (19).

In this way we can recursively construct (c_{0}(g), …, c_{k−1}(g)) ∈ 𝕂^{k} so that (c_{0}(g), …, c_{k−1}(g)) is the unique solution to (19) in 𝕂^{×} × 𝕂^{k−1}. Hence the lemma is proved.

Lemma 4 constructs a point c(g) = (c_{0}(g), …, c_{k−1}(g)) ∈ 𝕂^{k} such c_{0}(g) ≠ 0 and G(X, c(g), g) − H(X, c(g)) is of degree ≤ k − 2. Therefore F (X, c(g)) is a good approaximant of g. The condition that the first k coefficients of G(X, c(g), g) − H(X, c(g)) vanish is better than expected, but control on one extra term turns out to be useful. For simplicity we frequently omit g from the notation for the solution, if it is understood from the context.

2.2 Consequences of Lemma 4

The technique used to prove Lemma 4 has several corollaries that are indispensable for later developments.

Corollary 5.

(i) Let 0 ≤ i_{0} ≤ k − 1. Consider the subsystem of equations

u_{i}(x) = v_{i}(x, g) (0 ≤ i ≤ i_{0}).

Observe that variables appearing in these equations are x_{0}, …, x_{i_{0}}. This system has a unique solution in 𝕂^{×} × 𝕂^{i_{0}} given by the first i_{0} + 1 coordinates of c, i.e., (c_{0}, …, c_{i_{0}}).

(ii) Let g_{1}, g_{2} ∈ 𝕂[X]_{k} with g_{1} − g_{2} ∈ 𝕂. Then c(g_{1}) = c(g_{2}).

Proof.

(i) Follows from the recursion argument in the proof of Lemma 4.

(ii) A consequence of the fact that for any g ∈ 𝕂[X]_{k}, the polynomials

{v_{i}(X, g) | 0 ≤ i ≤ k − 1}

do not depend on the constant term of g.

The next corollary characterizes all good approximants and provides a necessary and sufficient condition for existence of difference primitives.

Corollary 6.

(i) For each c ∈ 𝕂 the polynomial F (X, c_{0}, …, c_{k−2}, c) is a good approximant of g and every good approximant of g is in this form.

(ii) There exists a nonzero polynomial f(X) ∈ 𝕂[X] so that \frac{1}{f(X)} is a difference primitive of −\frac{1}{g(X)} if and only if the tuple c = (c_{0}, …, c_{k−1}) constructed in Lemma 4 satisfies

u_{i}(c) = v_{i}(c, g) (k ≤ i ≤ 2k − 2).

If this condition holds then f(X) is uniquely determined and equals F (X, c).

Proof.

(i) By definition, all good approximants of g have degree k − 1. Let C = (C_{0}, …, C_{k−1}) ∈ 𝕂^{×} × 𝕂^{k−1}. Using (15) one sees that F (X, C) is good approximant if and only if u_{i}(C) = v_{i}(C, g) for each 0 ≤ i ≤ k − 2. Now the result follows from uniqueness part of Corollary 5.

(ii) We have already seen that f has to be of degree k − 1. From (15) it follows that such f exists if and only if the system of 2k − 1 equations

u_{i}(x) = v_{i}(x, g) (0 ≤ i ≤ 2k − 2)

has a solution in 𝕂^{×} × 𝕂^{k−1}. Lemma 4 implies that if such solution exists it is unique and given by the tuple c = (c_{0}, …, c_{k−1}) ∈ 𝕂^{×} × 𝕂^{k−1} constructed in lemma. Thus both parts of assertion are proved.

The following corollary investigates effect of scaling g.

Corollary 7. Let g_{1}(X) ∈ 𝕂[X] be a nonzero scalar multiple of g(X), i.e., g_{1}(X) = αg(X) for some α ∈ 𝕂^{×}. Then (αc_{0}(g), …, αc_{k−1}(g)) ∈ 𝕂^{×} ×𝕂^{k−1} is the unique solution to system of equations

u_{i}(x) = v_{i}(x, g_{1}) (0 ≤ i ≤ k − 1).

Proof. One writes coefficients as functions of polynomials. By assumption a_{r}(g_{1}) = αa_{r}(g) for all 0 ≤ r ≤ k − 1. From explicit expressions (12), (13) and (14) it follows that u_{j} is quadratic polynomial of {x_{0}, …, x_{k−1}} while v_{l} is linear in both {x_{0}, …, x_{k−1}} and {a_{0}, …, a_{k−1}}. Therefore the system of equations

u_{i}(x) = v_{i}(x, g) (0 ≤ i ≤ k − 1)

is invariant under transformation x_{i} → αx_{i}, 0 ≤ i ≤ k − 1, and a_{r} → αa_{r}, 0 ≤ r ≤ k − 1. Hence (αc_{0}(g), …, αc_{k−1}(g)) is a solution to the system corresponding to g_{1}. But αc_{0}(g) ≠ 0. The result follows by uniqueness.

Let c ∈ 𝕂. Define f_{g}(c, X) ∈ 𝕂[X] by

f_{g}(c, X) := c_{0}(g)X^{k−1} + … + c_{k−2}(g)X + c  (22)

By Corollary 6 f_{g}(c) is a good approximant of g and all good approximants are in this form. The leading term of N(f_{g}(c), g, X) is X^{k−1} and its coefficient is

(v_{k−1}(c_{0}, …, c_{k−2}, c; g) − u_{k−1}(c_{0}, …, c_{k−1}, c)).

By (14) x_{k−1} does not appear in v_{k−1}(x) and from the proof of Lemma 4, we know that the term involving x_{k−1} in u_{k−1}(x) is 2x_{k−1}x_{0}. Now

v_{k−1}(c_{0}, …, c_{k−2}, c; g) − u_{k−1}(c_{0}, …, c_{k−1}, c)
= v_{k−1}(c_{0}, …, c_{k−2}, c_{k−1}; g) − u_{k−1}(c_{0}, …, c_{k−1}, c)
= u_{k−1}(c_{0}, …, c_{k−2}, c_{k−1}; g) − u_{k−1}(c_{0}, …, c_{k−1}, c)
= 2c_{0}(c_{k−1} − c).  (23)

Here in third step one uses Lemma 4. Therefore coefficient of X^{k−1} in N(f_{g}(c), g, X) is 2c_{0}(c_{k−1} − c).

2.3 Formal algebraic version

We conclude the section with a formal version of Lemma 4. Let k ≥ 2 and a_{0}, …, a_{k} be formal variables. Suppose that g(X, a) is an element of ℤ[a_{0}, …, a_{k}] given by

g(X, a) = a_{0}X^{k} + ⋯ + a_{k}.  (24)

Define auxiliary polynomials

{y_{i}(x), u_{j}(x), v_{l}(x, a) | 0 ≤ i ≤ k − 1, 0 ≤ j, l ≤ 2k − 2} ⊆ ℤ[x, a]

using (9), (10) and (11). It is easy to see that these polynomials satisfy (12), (13) and (14). Consider the system of equations

u_{i}(x) = v_{i}(x, a) (0 ≤ i ≤ k − 1)  (25)

in variables x_{0}, …, x_{k−1}.

Lemma 8. Let 𝔽 = ℚ(a_{0}, …, a_{k}), the field of rational functions in variables a_{0}, …, a_{k} with coefficients in ℚ. Then there is a unique tuple of rational functions (c_{0}(a), …, c_{k−1}(a)) ∈ 𝔽^{k} with c_{0}(a) ≠ 0, which is a solution to the system of equations (25). Further, c_{i}(a) ∈ ℚ[a_{0}, …, a_{i}][a_{0}^{−1}] for all 0 ≤ i ≤ k − 1.

Proof. Similar to the proof of Lemma 4. The base case holds since c_{0} = a_{0}(k − 1) ≠ 0. Let 0 ≤ i ≤ k −2. The recursion step goes through, since u_{i+1} is independent of {a_{0}, …, a_{k}} and v_{i+1} depends only on {a_{0}, …, a_{i+1}} and to determine c_{i+1} one needs to divide by an element of ℚ^{×}a_{0}. Recursively, one deduces

c_{i}(a) ∈ ℚ[a_{0}, …, a_{i}][a_{0}^{−1}] (0 ≤ i ≤ k − 1).

In the formal version of the theory, it is enough to consider only one polynomial, namely, the universal polynomial g(X, a). Statements analogous to Corollary 5(i) and Corollary 7 hold in this situation, i.e., one can restrict to suitable subsystems and scaling of variables results into scaling of solution. The notion of good approximant with coefficients in 𝔽 can be introduced in exactly same manner. Lemma 8 constructs a canonical good approximant for g(X, a) and classification of Corollary 6 continues to hold.

3 Proofs of the theorems

In this section we use the theory developed in Section 2 to prove Theorem 1. An appropriate application of the same ideas yields Theorem 3. Corollary 2 is an easy consequence of Theorem 1.

We initiate the discussion with a useful remark. In what follows, 𝕂 is always a subfield of ℝ unless otherwise specified.

Remark 9.

(i) Let ϕ(X) = a_{0}X^{d} + a_{1}X^{d−1} + ⋯ + a_{d} ∈ 𝕂[X] is a polynomial with sgn ϕ = 1. Then ϕ(x) > 0 for all real x satisfying

x ≥ max\{1, \frac{(d + 1)|a_{j}|}{|a_{0}|} | 1 ≤ j ≤ d\}.  (26)

If d = 0 then the right-hand side is interpreted as 1. Note that expression on the right-hand side is an element of 𝕂.

(ii) The lower bound appearing in the first part is not best possible. To determine the best possible bound, we need to locate the real zeroes of ϕ.

(iii) Using (i) one can effectively determine the constant M_{0} appearing in the statement of Theorems 1 and 3.

3.1 Proof of Theorem 1

Let P (X) ∈ 𝕂[X] be of degree k ≥ 2 with sgn P = 1. Suppose that M_{0} is an element of 𝕂 with property that P (x) > 0 for all real x ≥ M_{0} + 1.

With the notation of Section 2 we use Lemma 4 for g(X) = P (X). Note that a_{0}, the leading coefficient of P (X), is positive. Let (c_{0}, …, c_{k−1}) ∈ 𝕂^{×}×𝕂^{k−1} be the unique solution to the system of equations (19) corresponding to P.

Now (c_{k−1} − 1, c_{k−1}) ∩ 𝕂 is nonempty since 𝕂 is dense in ℝ. Let c be an element of (c_{k−1} − 1, c_{k−1}) ∩ 𝕂. Define f_{P} (c, X) ∈ 𝕂[X] by (22). Since c_{0} = a_{0}(k − 1) > 0 there exists a M_{f_{P} (c)} ∈ ℝ so that f_{P} (c, x) > 0 for all real x ≥ M_{f_{P} (c)}. We know that f_{P} (c, X) is a good approximant of P (X), and the coefficient of X^{k−1} in N(f_{P} (c), P, X) is 2c_{0}(c_{k−1} − c). But 2c_{0}(c_{k−1} − c) > 0. Hence there is a M_{1} ∈ ℝ such that N(f_{P} (c), P, x) > 0 for all real x ≥ M_{1}.

Let M′_{1} = max{M_{1}, M_{f_{P} (c)}}. Suppose that m is a positive integer ≥ M′_{1} − M_{0}. Then by (16) and (17)

δ(f_{P} (c), P, m + M_{0}) > 0

i.e.,

\frac{1}{f_{P} (c, m + M_{0})} − \frac{1}{f_{P} (c, m + 1 + M_{0})} > \frac{1}{P (m + M_{0})}.

Using telescoping summation we have

\frac{1}{f_{P} (c, n + M_{0})} > ∑_{m=n}^{∞} \frac{1}{P (m + M_{0})}  (27)

for all positive integers n ≥ M′_{1} − M_{0}.

Now let C = c + 1 ∈ 𝕂, and consider f_{P} (C, X) ∈ 𝕂[X]. It is a good approximant of P and coefficient of X^{k−1} in N(f_{P} (C), P, X) is 2c_{0}(c_{k−1} − C). But c_{k−1} − c − 1 < 0. Therefore 2c_{0}(c_{k−1} − C) < 0 and there exists a M_{2} ∈ ℝ so that N(f_{P} (C), P, x) < 0 for all real x ≥ M_{2}.

Let M′_{2} = max{M_{2}, M_{f_{P} (c)}} and m be a positive integer ≥ M′_{2} − M_{0}. It follows that

δ(f_{P} (C), P, m + M_{0}) < 0

i.e.,

\frac{1}{f_{P} (c, m + M_{0}) + 1} − \frac{1}{f_{P} (c, m + 1 + M_{0}) + 1} < \frac{1}{P (m + M_{0})}.

By telescoping we have

\frac{1}{f_{P} (c, n + M_{0}) + 1} < ∑_{m=n}^{∞} \frac{1}{P (m + M_{0})}  (28)

for all positive integers n ≥ M′_{2} − M_{0}.

Suppose that M_{3} = max{M′_{1}, M′_{2}}. Using (27) and (28)

0 < \frac{1}{f_{P} (c, n + M_{0}) + 1} < ∑_{m=n}^{∞} \frac{1}{P (m + M_{0})} < \frac{1}{f_{P} (c, n + M_{0})}

for all positive integers n ≥ M_{3} − M_{0}. The leftmost inequality is a consequence of M_{3} ≥ M_{f_{P} (c)}.

Let h(X) = f_{P} (c, X + M_{0}). Note that it has degree k − 1. Since M_{0} ∈ 𝕂, the polynomial h(X) ∈ 𝕂[X]. Put N_{0} = max{⌈M_{3} − M_{0}⌉, 1}. Then

0 < \frac{1}{h(n) + 1} < ∑_{m=n}^{∞} \frac{1}{P (m + M_{0})} < \frac{1}{h(n)}

for all integers n ≥ N_{0}. It is clear that h and N_{0} so defined have properties required by Theorem 1. This construction proves the first part of Theorem 1.

Further Lemma 4 algorithmically determines the tuple (c_{0}, …, c_{k−1}) and c is any element of (c_{k−1} −1, c_{k−1})∩𝕂. Therefore we can determine f_{P} (c) algorithmically. Since M_{0} is part of hypothesis the polynomial h is also algorithmically computable. To finish off proof we need to show uniqueness. This part of assertion is a consequence of Lemma 10. Thus the proof of Theorem 1 is complete, modulo Lemma 10. □

Corollary 2 is a special case of Theorem 1.

3.1.1 Proof of Corollary 2

Follows from Theorem 1 with 𝕂 = ℚ, P (X) = X^{k} ∈ ℚ[X], and M_{0} = 0. □

3.2 Proof of Theorem 3

In this subsection we prove Theorem 3. Main idea behind the proof is to approximate the rational function by appropriate polynomial.

Let P (X), Q(X) be two nonzero polynomials in 𝕂[X] so that deg_{𝕂}P − deg_{𝕂}Q = k ≥ 2 and sgn P = sgn Q = 1. Suppose that R(X) = \frac{P (X)}{Q(X)} and M_{0} ∈ 𝕂 with P (x), Q(x) > 0 for all real x ≥ M_{0} + 1.

Using the division algorithm, we construct polynomials A(X), B(X) ∈ 𝕂[X] such that

P (X) = A(X)Q(X) + B(X)

and deg_{𝕂}B < deg_{𝕂}Q. It is easy to see that A(X) is of degree k and sgn A = 1. Now

R(X) = A(X) + \frac{B(X)}{Q(X)}.  (29)

Note that A(X) is determined by R(X) and does not depend on individual polynomials P (X) and Q(X). It is the unique polynomial so that the difference R(X) − A(X) is either 0 or is given by a rational function whose denominator has degree strictly larger than degree of numerator. Since deg_{𝕂}B < deg_{𝕂}Q, \frac{B(X)}{Q(X)} → 0 as x → ∞ on real line. If B = 0 then R(X) = A(X) and the result is already true by Theorem 1.

Let ϵ ∈ 𝕂 ∩ (sgn B) ℝ_{>0}. If B = 0 then ϵ = 0. Note that Q(x) > 0 for x ≥ M_{0} + 1. Hence there is a real number M_{ϵ} ≥ M_{0} + 1 > 0 such that for all real x ≥ M_{ϵ} we have (sgn B)B(x) ≥ 0 and 0 ≤ |\frac{B(x)}{Q(x)}| ≤ |ϵ|.

Define A_{ϵ}(X) = A(X) + ϵ ∈ 𝕂[X]. It is easy to see that A_{ϵ}(X) is a polynomial of degree k with sgn A_{ϵ} = 1. Moreover, if sgn B ≥ 0 then

A(x) ≤ R(x) ≤ A_{ϵ}(x) (x ≥ M_{ϵ})  (30)

and if sgn B = −1 then

A_{ϵ}(x) ≤ R(x) ≤ A(x) (x ≥ M_{ϵ}).  (31)

Consider the system of equation (19) in Lemma 4 for the polynomials A(X) and A_{ϵ}(X). By Corollary 5(ii) the same tuple (c_{0}, …, c_{k−1}) ∈ 𝕂^{×} × 𝕂^{k−1} is a solution to (19) for both A(X) and A_{ϵ}(X). Since sgn A = 1 we have c_{0} > 0. Let c ∈ (c_{k−1} − 1, c_{k−1}) ∩ 𝕂 and consider f_{A}(c, X) ∈ 𝕂[X] defined in Section 2. It is a good approximant of each of A(X) and A_{ϵ}(X). The coefficient of X^{k−1} in both N(f_{A}(c), A, X) and N(f_{A}(c), A_{ϵ}, X) is 2c_{0}(c_{k−1} − c) > 0. Similarly, the coefficient of X^{k−1} in each of N(f_{A}(c) + 1, A, X) and N(f_{A}(c) + 1, A_{ϵ}, X) is 2c_{0}(c_{k−1} − c − 1) < 0.

Let M′ ∈ ℝ be such that A(x), A_{ϵ}(x) > 0 for all real x ≥ M′. Imitating the proof of Theorem 1, we can find M′_{3}, M′_{3,ϵ} ≥ M′ so that

0 < \frac{1}{f_{A}(c, n + M_{0}) + 1} < ∑_{m=n}^{∞} \frac{1}{A(m + M_{0})} < \frac{1}{f_{A}(c, n + M_{0})},

0 < \frac{1}{f_{A}(c, n + M_{0}) + 1} < ∑_{m=n}^{∞} \frac{1}{A_{ϵ}(m + M_{0})} < \frac{1}{f_{A}(c, n + M_{0})}

holds for all positive integers n ≥ M′_{3} − M_{0} and n ≥ M′_{3,ϵ} − M_{0} respectively.

Let M_{4} = max{M′_{3}, M′_{3,ϵ}, M_{ϵ}}. From inequalities (30), (31) and choice of M′_{3}, M′_{3,ϵ} it follows that

0 < \frac{1}{f_{A}(c, n + M_{0}) + 1} < ∑_{m=n}^{∞} \frac{1}{R(m + M_{0})} < \frac{1}{f_{A}(c, n + M_{0})}

for all positive integers n ≥ M_{4} − M_{0}. Set h(X) = f_{A}(c, X + M_{0}) and N_{0} = max{⌈M_{4} − M_{0}⌉, 1}. One easily sees that h(X) ∈ 𝕂[X]_{k−1} is a polynomial that satisfies the requirements of the statement of the theorem for the prescribed choice of N_{0}. Note that A, B are algorithmically computable. Therefore, by reasoning similar to that in the proof of Theorem 1, h is also algorithmically computable.

Proof of uniqueness is postponed to Lemma 10. □

3.2.1 Effectiveness of constants

Using Remark 9 we can determine effective choices for the constants M_{f_{P} (c)}, M_{1}, M_{2} appearing in the proof of Theorem 1. Hence M′_{1}, M′_{2}, M_{3}, and in particular, N_{0} are effective. These constants depend on choice of c. In the proof of Theorem 3, ϵ is any number in 𝕂∩(sgn B)ℝ_{>0} and the inequalities (sgn B)B(x) ≥ 0, 0 ≤ |\frac{B(x)}{Q(x)}| ≤ |ϵ| effectively determine M_{ϵ}. Now one can use Remark 9 to show that the constants appearing in the proof of Theorem 3 are also effective. These numbers depend on choices of P, Q, c, and ϵ.

3.3 Admissible polynomials

This subsection studies all polynomials which approximate reciprocals of tail sums. First, we prove a lemma which implies uniqueness part of Theorem 1 and 3. Recall that to retrieve Theorem 1 from Theorem 3 one needs to substitute Q = 1. The notation is same as in the statement of Theorem 3.

Lemma 10. Suppose that h_{1}(X), h_{2}(X) ∈ 𝕂[X] are two nonzero polynomials which satisfy

0 < h_{j}(n) ≤ \frac{1}{∑{∞ \atop m=n} \frac{1}{R(m+M_{0})}} < h_{j}(n) + 1 (j = 1, 2)

for infinitely many n ∈ ℕ. Then

(i) deg_{𝕂}h_{1} = deg_{𝕂}h_{2} = k − 1,

(ii) h_{1}(X) − h_{2}(X) ∈ 𝕂,

(iii) |h_{1} − h_{2}| < 2,

(iv) if there is an infinite subset of ℕ on which hypothesis of the lemma hold simultaneously for h_{1} and h_{2}, then |h_{1} − h_{2}| < 1.

Proof. In what follows the statements hold for both j = 1, 2. By assumption

0 < \frac{1}{h_{j}(n) + 1} < ∑_{m=n}^{∞} \frac{1}{R(m + M_{0})} ≤ \frac{1}{h_{j}(n)}  (32)

for infinitely many n ∈ ℕ. These inequalities imply that h_{j} is non-constant and sgn h_{j} = 1.

Let h(X) be the polynomial constructed in the proof of Theorem 3. Comparing with (32)

0 < \frac{1}{h(n) + 1} < \frac{1}{h_{j}(n)},

0 < \frac{1}{h_{j}(n) + 1} < \frac{1}{h(n)}

for infinitely many n ∈ ℕ. Hence on an infinite subset of ℕ

h(n) − 1 < h_{j}(n) < h(n) + 1.  (33)

It follows that |h(n) − h_{j}(n)| < 1 on an infinite subset. But this inequality forces the difference to be constant.

The conclusion above proves both (i) and (ii). The proof of (iii) follows from (33).

Without loss of generality assume h_{1} − h_{2} = C ≥ 0. If C ≥ 1 then

0 < \frac{1}{h_{1}(n)} ≤ \frac{1}{h_{2}(n) + 1} (n ≫ 1).

This contradicts the hypothesis of (iv). Hence (iv) is proved by way of contradiction.

3.3.1 Admissible polynomials

We introduce a terminology for convenience. A polynomial h(X) ∈ 𝕂[X] is admissible for (R, M_{0}) if

0 < h(n) ≤ \frac{1}{∑{∞ \atop m=n} \frac{1}{R(m+M_{0})}} < h(n) + 1 (n ≫ 1).

In rest of the section let (c_{0}, …, c_{k−1}) ∈ 𝕂^{×} × 𝕂^{k−1} denote the unique solution to system of equations (19) associated with A(X). The polynomial A depends only on R and is determined by (29). Since sgn A = 1 it follows that c_{0} > 0. Moreover, the tuple does not depend on the constant term of A (Corollary 5).

Lemma 10 implies that every admissible polynomial for (R, M_{0}) is of degree k−1 and has positive leading coefficient. Further if h_{1}, h_{2} are two admissible polynomials then h_{1} − h_{2} is constant and |h_{1} − h_{2}| < 1. We have shown in Section 3.2 that for each c ∈ (c_{k−1} − 1, c_{k−1}) ∩ 𝕂 the polynomial f_{A}(c, X + M_{0}) is admissible for (R, M_{0}). In fact it satisfies a stronger inequality, namely,

0 < f_{A}(c, n + M_{0}) < \frac{1}{∑{∞ \atop m=n} \frac{1}{R(m+M_{0})}} < f_{A}(c, n + M_{0}) + 1 (n ≥ N_{0}).

Constant term of this polynomial is f_{A}(c, M_{0}). Now for all x, y ∈ 𝕂

f_{A}(x, X) − f_{A}(y, X) = x − y.  (34)

Since c ∈ (c_{k−1} − 1, c_{k−1}) ∩ 𝕂 is infinite, there are infinitely many distinct choices for c which give rise to infinitely many admissible polynomials.

3.3.2 Effect of scaling

Let α ∈ 𝕂^{×} be positive. Now αR(X) = \frac{αP (X)}{Q(X)}. Therefore same constant M_{0} has desired positivity properties and the quotient polynomial is A_{α}(X) := αA(X). By Corollary 7 c(A_{α}) = αc(A). Therefore if h(X) and h_{α}(X) are admissible polynomials with respect to (R, M_{0}) and (αR, M_{0}) resp., then h_{α}(X) − αh(X) ∈ 𝕂.

3.3.3 Choice of constant term

Let c ∈ (c_{k−1}−1, c_{k−1})∩𝕂. We have seen that f_{A}(c, M_{0}) is the constant term of a polynomial admissible for (R, M_{0}). Let C ∈ 𝕂 be the constant term of some other admissible polynomial H(X).

Lemma 11.

(i) There exists unique c ∈ [c_{k−1} − 1, c_{k−1}] ∩ 𝕂 such that

C = f_{A}(c, M_{0}),
H(X) = f_{A}(c, X + M_{0}).

(ii) Both f_{A}(c_{k−1} − 1, X + M_{0}) and f_{A}(c_{k−1}, X + M_{0}) cannot be admissible polynomials for (R, M_{0}).

Proof.

(i) For brevity write I = (c_{k−1} − 1, c_{k−1}) ∩ 𝕂.

Let c = C − f_{A}(0, M_{0}) ∈ 𝕂. Substituting x = c, y = 0 and X = M_{0} in (34) we have f_{A}(c, M_{0}) = C. Moreover, if x ∈ 𝕂 satisfies f_{A}(x, M_{0}) = C then x = c. By Lemma 10 (iv), |C − f_{A}(x, M_{0})| < 1 holds for each x ∈ I. Hence |c − x| < 1 for all x ∈ I. Therefore c ∈ [c_{k−1} − 1, c_{k−1}]. Now

H(X) − f_{A}(c, X + M_{0}) = H(X) − f_{A}(x, X + M_{0}) + f_{A}(x, X + M_{0}) − f_{A}(c, X + M_{0})

for all x ∈ 𝕂. Letting x ∈ I and using admissibility of H we see that the righthand side is constant (Lemma 10). But the constant term of the left-hand side is 0. Therefore H(X) = f_{A}(c, X + M_{0}).

(ii) Since f_{A}(c_{k−1}, X +M_{0})−f_{A}(c_{k−1}−1, X +M_{0}) = 1 the assertion follows from Lemma 10 (iv).

Lemma 11 characterizes all admissible polynomials with possible exception at boundary of the interval. Analysis of extremal situation is necessary for later development. We need mild improvement over formalism of Section 2 to discuss admissibility of boundary points.

3.3.4 Approximate primitive for rational functions

Let 𝕂 be a field of characteristic 0 and P (X), Q(X), f(X) ∈ 𝕂[X] − {0}. Suppose that deg_{𝕂}P − deg_{𝕂}Q = k ≥ 2. Define

δ(f, R, X) := \frac{1}{f(X)} − \frac{1}{f(X + 1)} − \frac{1}{R(X)},

N(f, R, X) := P (X)(f(X + 1) − f(X)) − Q(X)f(X)f(X + 1) where R = \frac{P}{Q}. These expressions depend on P and Q. However if N(f, R, X) = 0 for one presentation then it is 0 for all presentations. It is clear that

δ(f, R, X) = \frac{N(f, R, X)}{f(X)f(X + 1)P (X)}.  (35)

Further δ(f, R, X) = 0 implies deg_{𝕂}f = k − 1. Let A(X), B(X) ∈ 𝕂[X] be the polynomials obtained by the division algorithm, i.e., P (X) = A(X)Q(X) + B(X) with deg_{𝕂}A = k and deg_{𝕂}B < deg_{𝕂}Q. Then

δ(f, R, X) = δ(f, A, X) + \frac{B(X)}{P (X)A(X)},

i.e,

δ(f, R, X) = \frac{N(f, A, X)}{f(X)f(X + 1)A(X)} + \frac{B(X)}{P (X)A(X)}.

We have deg_{𝕂}P (X)A(X) − deg_{𝕂}B(X) > 2k. Suppose that f ∈ 𝕂[X]_{k−1}. If N(f, A, X) ∈ 𝕂[X]_{k−1} then deg_{𝕂}f(X)f(X +1)A(X)−deg_{𝕂}N(f, A, X) = 2k −1. Here hypothesis amounts to saying that f is a good approximant of A with constant term ≠ c_{k−1}. In such situation behavior of δ(f, R, X) is dominated by δ(f, A, X). Now let f be an arbitrary element of 𝕂[X]_{k−1}. From expression above it follows that δ(f, R, X) = 0 if and only if

N(f, A, X)P (X) = −f(X)f(X + 1)B(X).  (36)

If (36) holds then deg_{𝕂}N(f, A, X) = k − 2 + deg_{𝕂}B − deg_{𝕂}Q < k − 2. Moreover, we have N(f, A, X) = 0 if B(X) = 0.

Notation and assumptions are identical to Section 3.2. Since sgn P = sgn Q = 1 it is easy to see that sgn N(f, R, X) depends only on R and is independent of presentation.

Lemma 12.

(i) Let N(f_{A}(c_{k−1}), R, X) = 0. Then f_{A}(c_{k−1}, X + M_{0}) is admissible for (R, M_{0}).

(ii) Now suppose N(f_{A}(c_{k−1}), R, X) ≠ 0. If sgn N(f_{A}(c_{k−1}), R, X) = 1 then f_{A}(c_{k−1}, X + M_{0}) is admissible and if sgn N(f_{A}(c_{k−1}), R, X) = −1 then f_{A}(c_{k−1} − 1, X + M_{0}) is admissible.

Proof. (i) By assumption N(f_{A}(c_{k−1}), R, X) = δ(f_{A}(c_{k−1}), R, X) = 0. Therefore

\frac{1}{R(X)} = \frac{1}{f_{A}(c_{k−1}, X)} − \frac{1}{f_{A}(c_{k−1}, X + 1)}.  (37)

By (37) the maximum of real zeroes of f_{A}(c_{k−1}, X) is < M_{0} + 1. Hence f_{A}(c_{k−1}, n +

M_{0}) > 0 for all n ∈ ℕ. Telescoping
∑_{m=n}^{∞} \frac{1}{R(m + M_{0})} = \frac{1}{f_{A}(c_{k−1}, n + M_{0})} (n ≥ 1).  (38)

The coefficient of X^{k−1} in both N(f_{A}(c_{k−1}) + 1, A, X) and N(f_{A}(c_{k−1}) + 1, A_{ϵ}, X) is 2c_{0}(c_{k−1} − c_{k−1} − 1) = −2c_{0} < 0. Using (30) and (31) and imitating the proof of Theorem 3, we can show

∑_{m=n}^{∞} \frac{1}{R(m + M_{0})} > \frac{1}{f_{A}(c_{k−1}, n + M_{0}) + 1} (n ≫ 1).

Therefore f_{A}(c_{k−1}, X + M_{0}) is admissible.

(ii) Let N(f_{A}(c_{k−1}), R, X) ≠ 0. Suppose that sgn N(f_{A}(c_{k−1}), R, X) = 1. Hence there is M_{1} ∈ ℝ such that N(f_{A}(c_{k−1}), R, x) > 0 for all real x ≥ M_{1}. One can use (35) and telescoping to deduce

∑_{m=n}^{∞} \frac{1}{R(m + M_{0})} < \frac{1}{f_{A}(c_{k−1}, n + M_{0})} (n ≫ 1).

The coefficient of X^{k−1} in each of N(f_{A}(c_{k−1}) + 1, A, X) and N(f_{A}(c_{k−1}) + 1, A_{ϵ}, X) is 2c_{0}(c_{k−1} − c_{k−1} − 1) = −2c_{0} < 0. We can repeat the arguments from the proof of Theorem 3 to conclude (see part (i))

∑_{m=n}^{∞} \frac{1}{R(m + M_{0})} > \frac{1}{f_{A}(c_{k−1}, n + M_{0}) + 1} (n ≫ 1).

Hence f_{A}(c_{k−1}, X + M_{0}) is an admissible polynomial.

Now assume that sgn N(f_{A}(c_{k−1}), R, X) = −1. As before, we can use (35) and telescoping to conclude

∑_{m=n}^{∞} \frac{1}{R(m + M_{0})} > \frac{1}{f_{A}(c_{k−1}, n + M_{0})} (n ≫ 1).

Note that f_{A}(c_{k−1})−1 is a good approximant of A and A_{ϵ}. Further coefficient of X^{k−1} in both N(f_{A}(c_{k−1})−1, A, X) and N(f_{A}(c_{k−1})−1, A_{ϵ}, X) is 2c_{0}(c_{k−1}−c_{k−1}+1) = 2c_{0} > 0. Therefore

∑_{m=n}^{∞} \frac{1}{R(m + M_{0})} < \frac{1}{f_{A}(c_{k−1}, n + M_{0}) − 1} (n ≫ 1).

Hence f_{A}(c_{k−1} − 1, X + M_{0}) is an admissible polynomial in this case.

3.3.5 Summation by telescoping

If there is f(X) ∈ 𝕂[X]−\{0\} so that \frac{1}{R(X)} = \frac{1}{f(X)} − \frac{1}{f(X+1)} then N(f, R, X) = 0. By (35) and (36) we have deg_{𝕂}f = k − 1, deg_{𝕂}N(f, A, X) < k − 2. Now (15) and Lemma 4 implies that f_{A}(c_{k−1}) is the only polynomial which can possibly satisfy these two conditions. Therefore −\frac{1}{R(X)} has an exact difference primitive if and only if N(f_{A}(c_{k−1}), R, X) = 0. Whenever this criterion holds, we can compute the exact value of the sum by telescoping. (Cf. Corollary 6.)

Remark 13. One can use Remark 9 to calculate effective lower bounds on n for inequalities of Lemma 12 to hold. Computations are analogous to Section 3.2 and we omit the details.

4 Explicit calculations

4.1 Reciprocal sequence

This subsection is devoted to explicit calculation of reciprocal sequence. We begin with an elementary observation. The situation is same as Theorem 3.

Remark 14. Let h be a polynomial given by Theorem 3 and N_{0} be the corresponding integer. Suppose that (a_{n})_{n≥1} is reciprocal sequence of the sequence (x_{m})_{m≥1} given by x_{m} = \frac{1}{R(m+M_{0})}. Then from (6) it follows that, for all n ≥ N_{0},

(i) a_{n} is either ⌊h(n)⌋ or ⌊h(n)⌋ + 1;

(ii) if h(n) is an integer for some n, then a_{n} = h(n).

Let P, Q ∈ ℚ[X] be polynomials so that deg_{ℚ}P −deg_{ℚ}Q = k ≥ 2 and sgn P = sgn Q = 1. Suppose that P (x), Q(x) > 0 for all real x ≥ 1, i.e., 0 is a legitimate choice for M_{0}. One can always ensure this property by shifting the polynomials in hypothesis. Set R(X) = \frac{P (X)}{Q(X)} ∈ ℚ(X) and consider the sequence (x_{m})_{m≥1} given by

x_{m} = \frac{1}{R(m)} (m ≥ 1).  (39)

Subsequent paragraphs contain an algorithmic determination of (a_{n})_{n≥1}, the reciprocal sequence of (x_{m})_{m≥1}.

4.1.1 Algorithm for reciprocal sequence

Let A(X) and B(X) be the polynomials in ℚ[X] obtained by the division algorithm, i.e, P (X) = A(X)Q(X) + B(X) and deg_{ℚ}B < deg_{ℚ}Q. Suppose that (c_{0}, …, c_{k−1}) ∈ ℚ^{×} × ℚ^{k−1} is the unique tuple which is solution to the system of equations (19) corresponding to A(X). Write c_{i} = \frac{p_{i}}{q_{i}} where p_{i}, q_{i} are integers with q_{i} > 0 and gcd(p_{i}, q_{i}) = 1 for each 0 ≤ i ≤ k − 1. Note that if p_{i} = 0 then q_{i} = 1. Let L = lcm(q_{0}, …, q_{k−2}). Put

\begin{matrix}H(X) = c_{0}X^{k−1} + ⋯ + c_{k−2}X, \\ H_{L}(X) = LH(X). \end{matrix}  (40)

It is clear that H_{L}(X) ∈ ℤ[X]. We determine a family of polynomial in ℚ[X] parameterized by residue classes modulo L such that for sufficiently large n value of a_{n} is obtained by evaluating one of these polynomials at n, and this polynomial depends only on residue class of n modulo L.

4.1.2 Case I: q_{k−1} ∤ L

Under this assumption q_{k−1} ≠ 1. Write c_{k−1} = ⌊c_{k−1}⌋ + \frac{r_{k−1}}{q_{k−1}} where r_{k−1} is a positive integer ≤ q_{k−1} − 1. Since gcd(p_{k−1}, q_{k−1}) = 1 it follows that gcd(r_{k−1}, q_{k−1}) = 1. Therefore \frac{r_{k−1}}{q_{k−1}} ∉ \{\frac{n}{L} | n ∈ ℤ\}.

Suppose that r ∈ {1, …, L}. By the argument above, there is a unique integer l(r) that satisfies l(r) − \frac{r}{L} < c_{k−1} < l(r) + 1 − \frac{r}{L}. Now let c(r) = l(r) − \frac{r}{L} and h_{r}(X) = H(X) + c(r). Since c(r) ∈ (c_{k−1} − 1, c_{k−1}) there is an integer N(r) so that

h_{r}(n) ≤ \frac{1}{∑{∞ \atop m=n} \frac{1}{R(m)}} < h_{r}(n) + 1 (n ≥ N(r)).

Fix choice of N(r) for each r ∈ {1, …, L}. Put N = max {N(1), …, N(L)}. Let n ≥ N. Now r(n) be the unique element in {1, …, L} with H_{L}(n) ≡ r(n) (mod L). Evidently r(n) depends only on residue class n mod L. Note that

h_{r(n)}(n) = \frac{H_{L}(n)}{L} + l(r(n)) − \frac{r(n)}{L} ∈ ℤ (n ≥ N).

Remark 14 (ii) implies a_{n} = h_{r(n)}(n).

Therefore in this case we have a closed form formula for a_{n} depending on equivalence class of n modulo L whenever n ≥ N.

4.1.3 Case II: q_{k−1} | L

Let r ∈ \{1, …, L\}. If \frac{r}{L} ≠ 1 + ⌊c_{k−1}⌋ − c_{k−1} then there is a unique integer l(r) with l(r)− \frac{r}{L} < c_{k−1} < l(r)+1− \frac{r}{L}. For these residue classes define c(r) = l(r)− \frac{r}{L} ∈ (c_{k−1}−1, c_{k−1}).

Now let r ∈ \{1, …, L\} with \frac{r}{L} = 1 + ⌊c_{k−1}⌋ − c_{k−1}. Such residue class exists and is unique. Set l(r) = 1 + ⌊c_{k−1}⌋. Note that c_{k−1} = l(r) − \frac{r}{L}. For this residue class define

c(r) = \begin{cases}c_{k−1}, & if sgn N(f_{A}(c_{k−1}), P, X) ≥ 0; \\ c_{k−1} − 1, & if sgn N(f_{A}(c_{k−1}), P, X) = −1. \end{cases}

Let h_{r}(X) = H(X) + c(r). By the proof of Theorem 3 and Lemma 12 it follows that for each r there is an integer N(r) so that

h_{r}(n) ≤ \frac{1}{∑{∞ \atop m=n} \frac{1}{R(m)}} < h_{r}(n) + 1 (n ≥ N(r)).

Suppose that N = max{N(1), …, N(L)}. Let n ≥ N and r(n) be the unique element in {1, …, L} such that H_{L}(n) ≡ r(n) (mod L). It follows that there is a positive integer N so that a_{n} = h_{r(n)}(n) whenever n ≥ N.

The discussion above can be summarized as follows:

Theorem 15. Let (x_{m})_{m≥1} be the sequence defined by (39). There exist a positive integer L, algorithmically computable polynomials h_{r,L}(X) ∈ ℚ[X] parameterized by residue classes modulo L, a polynomial H_{L}(X) ∈ ℤ[X] of degree k − 1 with constant term 0, and natural number N so that

(i) H_{L}(X) − Lh_{r,L}(X) ∈ ℤ for all residue classes r,

(ii) a_{n} = h_{r,L}(n) if H_{L}(n) ≡ r (mod L) for all n ≥ N.

Proof. The statement holds with L = lcm(q_{0}, …, q_{k−2}), H_{L} given by (40), polynomials (h_{r}(X))_{r mod L} and the number N constructed above. The tuple (c_{0}, …, c_{k−1}) is algorithmically constructible and once we have this datum, construction of (h_{r}(X))_{r mod L} is already given in two possible cases.

Remark 16. The choice of L in the proof of the theorem is algorithmically computable. Moreover, one can choose N effectively since by Section 3.2 and Remark 13 each of N(r) is effective.

Theorem 15 is an analogue of Theorem 3 in context of reciprocal sequence. The modulus in the statement of the theorem adds an arithmetic aspect to the theory.

4.1.4 Choice of modulus

Let 𝔪 be a natural number and ϕ(X) ∈ ℤ[X]. A residue class r modulo 𝔪 is nontrivial with respect to ϕ if there exists one (and hence infinitely many) integer n such that ϕ(n) ≡ r (mod 𝔪). Nontrivial residue classes are exactly residue classes of {ϕ(j) | 1 ≤ j ≤ 𝔪}. Observe that we need h_{r,L}(X) only for the residue classes modulo L which are nontrivial with respect to H_{L}. For other residue classes, the constant term of h_{r,L}(X) can be chosen arbitrarily. Let L_{1} be another positive integer so that there exists H_{L_{1}}(X) ∈ ℤ[X] and polynomials {h_{r,L_{1}}(X) | r mod L_{1}} ⊆ ℚ[X] satisfying conditions (i) and (ii) in the statement of theorem. Using condition (i) and Lemma 10

H(X) = \frac{H_{L_{1}}(X)}{L_{1}} = \frac{H_{L}(X)}{L}.

Since L = lcm(q_{0}, …, q_{k−2}) we have L|L_{1} and H_{L_{1}}(X) = \frac{L_{1}}{L} H_{L}(X). Non-constant part of the polynomials {h_{r,L_{1}}(X) | r mod L_{1}} are same and equals H(X). Now H_{L}(n_{1}) ≡ H_{L}(n_{2}) (mod L) if and only if H_{L_{1}}(n_{1}) ≡ H_{L_{1}}(n_{2}) (mod L_{1}) for all n_{1}, n_{2} ∈ ℤ. Hence H_{L}(n) → H_{L_{1}}(n) is a bijection between residue classes modulo L nontrivial with respect to H_{L} and residue classes modulo L_{1} nontrivial with respect to H_{L_{1}}. Let r, r_{1} be two nontrivial residue classes modulo L, L_{1} respectively. By condition (ii) of the theorem, h_{r,L}(X) = h_{r_{1},L_{1}}(X) if r corresponds to r_{1} under the bijection mentioned above.

This phenomenon shows that the modulus in Theorem 15 is essentially unique.

4.2 Asymptotic of summation

In this subsection we write down the asymptotic form of Theorem 3. For this purpose one requires a familiar technique from complex analysis.

Lemma 17. Let ϕ(z) = a_{0}z^{d}+a_{1}z^{d−1}+⋯+a_{d} ∈ ℂ[z] be a polynomial of degree d ≥ 1. There exists M(ϕ) > 0 (depending on ϕ) so that on an open set containing the region |z| ≥ M(ϕ)

\frac{1}{ϕ(z)} = ∑_{j≥d} \frac{A_{j}}{z^{j}}

where the right-hand side converges absolutely on the open set. Moreover, there are computable polynomials F_{j} ∈ ℤ[x_{1}, …, x_{d}], j ≥ d, which depend only on the integer d so that

(i) A_{j} = a_{0}^{−1}F_{j}(\frac{a_{1}}{a_{0}} , …, \frac{a_{d}}{a_{0}} ),

(ii) F_{d} is identically 1 and for d + 1 ≤ j ≤ 2d − 1 the set of variables appearing in F_{j} is {x_{1}, …, x_{j−d}}.

Proof. We have

ϕ(z)^{−1} = a_{0}^{−1}z^{−d}(1 + \frac{a_{1}}{a_{0}z} + ⋯ + \frac{a_{d}}{a_{0}z^{d}})^{−1}.

Write Φ(z) = −(\frac{a_{1}}{a_{0}} z + ⋯ + \frac{a_{d}}{a_{0}} z^{d}). It is easy to see that |Φ(\frac{1}{z})| ≤ \frac{d}{d+1} whenever |z| ≥ M = max\{1, \frac{(d+1)|a_{j}|}{|a_{0}|} | 1 ≤ j ≤ d\}. Let M(ϕ) = 1 + M and the open set be \{z ∈ ℂ | |z| > M\}. Observe that ϕ(z) has no zeroes in region |z| ≥ M. One obtains the first part of assertion by expanding (1 − Φ(\frac{1}{z}))^{−1} in a geometric series for |z| > M.

For any p ≥ 0, coefficient of z^{−p} in (1 − Φ(\frac{1}{z}))^{−1} is the coefficient of z^{−p} in the finite sum ∑_{r=0}^{p} Φ(\frac{1}{z})^{r}. Hence, the second part of the assertion is a consequence of the multinomial theorem.

4.2.1 Asymptotic form of Theorem 3

With the notation of Theorem 3 we have deg_{𝕂}h(X) = k − 1 ≥ 1 and leading coefficient of h(X) of is c_{0} > 0. Further h(n) > 0 for n ≥ N_{0}. The inequality (6) is equivalent to

0 < \frac{1}{h(n) + 1} < ∑_{m=n}^{∞} \frac{1}{R(m + M_{0})} ≤ \frac{1}{h(n)} (n ≥ N_{0}).  (41)

Now \frac{1}{h(X)} − \frac{1}{h(X)+1} = \frac{1}{h(X)(h(X)+1)}, and the first term in Taylor series of \frac{1}{h(z)(h(z)+1)} is c_{0}^{−2}z^{−2(k−1)}. Therefore \frac{1}{h(n)(h(n)+1)} = O(n^{−2k+2}) and

∑_{m=n}^{∞} \frac{1}{R(m + M_{0})} = \frac{1}{h(n)} + O(n^{−2k+2}) (n ≥ N_{0}).  (42)

Lemma 17 implies that for each n ≥ max{M(h), M(h + 1), N_{0}}

0 < \frac{1}{h(n)} = ∑_{j≥k−1} \frac{A_{j}^{(1)}}{n^{j}} ,

0 < \frac{1}{h(n) + 1} = ∑_{j≥k−1} \frac{A_{j}^{(2)}}{n^{j}} .

By the second part of the lemma, we have A_{j}^{(1)}, A_{j}^{(2)} ∈ 𝕂 for all j ≥ k − 1. Since leading term in expansion of \frac{1}{h(z)(h(z)+1)} is c_{0}^{−2}z^{−2k+2} we have

\begin{aligned}A_{j}^{(1)} & = A_{j}^{(2)}(= say, A_{j}) (k − 1 ≤ j ≤ 2k − 3), \\ A_{2k−2}^{(1)} & = A_{2k−2}^{(2)} + c_{0}^{−2} > A_{2k−2}^{(2)}. \end{aligned}

These statements also follow from lemma above. Moreover, from absolute convergence ensured by the lemma, it is easy to see that

\frac{1}{h(n)} = ∑_{j=k−1}^{2k−3} \frac{A_{j}}{n^{j}} + O_{h}(n^{−2k+2}),
\frac{1}{h(n) + 1} = ∑_{j=k−1}^{2k−3} \frac{A_{j}}{n^{j}} + O_{h+1}(n^{−2k+2}) (n ≫ 1).

From (41) one deduces

| ∑_{m=n}^{∞} \frac{1}{R(m + M_{0})} − ∑_{j=k−1}^{2k−3} \frac{A_{j}}{n^{j}} |

≤ max \{|\frac{1}{h(n)} − ∑_{j=k−1}^{2k−3} \frac{A_{j}}{n^{j}} |, |\frac{1}{h(n) + 1} − ∑_{j=k−1}^{2k−3} \frac{A_{j}}{n^{j}} |\} (n ≥ N_{0}).

Hence

∑_{m=n}^{∞} \frac{1}{R(m + M_{0})} = ∑_{j=k−1}^{2k−3} \frac{A_{j}}{n^{j}} + O(n^{−2k+2}) (n ≫ 1).  (43)

Thus we have calculated the first k − 1 terms in the asymptotic expansion of the sum in the left-hand side in the traditional sense. (Compare (42) and (43).)

The constants M and M(ϕ) appearing in Lemma 17 are effective. Let |z| ≥ M. Then |Φ(\frac{1}{z})| ≤ \frac{d}{d+1} and

\frac{1}{ϕ(z)} = a_{0}^{−1}z^{−d}( ∑_{r=0}^{p} Φ(\frac{1}{z})^{r} + ∑_{r≥p+1} Φ(\frac{1}{z})^{r}) (p ≥ 0).

Now suppose j ≥ d and p = j − d. It is clear that the terms ∑_{r=d}^{j} \frac{A_{r}}{z^{r}} in expansion of the lemma appear from the first summation, namely, a_{0}^{−1}z^{−d} ∑_{r=0}^{j−d} Φ(\frac{1}{z})^{r}. This summation contributes only finitely many terms in orders higher than (\frac{1}{z})^{j}. To estimate the second summation, note that in the region under consideration |Φ(\frac{1}{z})| ≤ \frac{α}{|z|} where α = |\frac{a_{1}}{a_{0}} | + \frac{d−1}{d+1}.

Thus, if |z| ≥ α+1 then | ∑_{r≥p+1} Φ(\frac{1}{z})^{r}| ≤ \frac{α^{p+1}(α+1)}{|z|^{p+1}}. Hence for fixed ϵ > 0 one can effectively determine M_{ϕ,j,ϵ} > 0 such that

| ∑_{r≥j+1} \frac{A_{r}}{z^{r}} | ≤ ϵ|z|^{−j} (|z| ≥ M_{ϕ,j,ϵ}).

From this argument, we conclude that the constant and range appearing in O_{h}, O_{h+1}, and (43) are effective.

4.3 The example: P (X) = X^{k}

Let k ≥ 2 and P (X) = X^{k}, Q(X) = 1 ∈ ℚ[X]. With the notation of Section 3, R(X) = P (X) = A(X) = X^{k}, B(X) = 0 and we are in the situtation of Theorem 1. The objective of this section is to write down the first few coefficients of the admissible polynomial f_{P} (X) as a function of k.

We introduce formal binomial coefficients for convenience. Let X be a formal variable and r ∈ ℤ_{≥0}. Define \binom{X}{r} to be an element of ℚ[X] given by the expression

\binom{X}{r} = \begin{cases}\frac{X(X−1)···(X−r+1)}{r!}, & if r ≥ 1; \\ 1, & if r = 0. \end{cases}

With the notation of Section 2 suppose that g(X) = X^{k}. For this polynomial

a_{r} = \begin{cases}1, & if r = 0; \\ 0, & if 1 ≤ r ≤ k. \end{cases}

By (14)

v_{l}(x, X^{k}) = y_{l+1}(x)
= \binom{k − l − 1}{1}x_{l} + \binom{k − l}{2}x_{l−1} + ⋯ + \binom{k − 1}{l + 1}x_{0}  (44)

for all 0 ≤ l ≤ k − 1. If l = k − 1 then one observes that (44) holds with formal binomial coefficients.

Substituting (12) into (13) we obtain

u_{j}(x) = ∑_{r=0}^{j} x_{j−r}x_{r} + ∑_{r=1}^{j} ∑_{s=1}^{r} \binom{k − s}{r − s + 1}x_{j−r}x_{s−1} (0 ≤ j ≤ k − 1).  (45)

Now one can proceed to solve the system of equations

u_{i}(x) = v_{i}(x, X^{k}) (0 ≤ i ≤ k − 1)

following the algorithm of Lemma 4. The first few solutions are as follows:

\begin{aligned}c_{0}(k) & = k − 1, \\ c_{1}(k) & = −\frac{(k − 1)^{2}}{2} , \\ c_{2}(k) & = \frac{(k − 1)^{2}(2k − 3)}{12} (k ≥ 3), \\ c_{3}(k) & = −\frac{(k − 1)^{3}(k − 3)}{24} (k ≥ 4), \\ c_{4}(k) & = \frac{(k − 1)^{2}}{720} (6k^{3} − 47k^{2} + 92k − 45) (k ≥ 5). \end{aligned}  (46)

In general one can use (44), (45), and recursion argument of Lemma 7 to conclude that c_{r}(k) is a rational function of k whenever k ≥ r + 1.

4.3.1 Asymptotic expansion of polygamma [1, p. 260]

Let k ≥ 1. The polygamma function of order k is a holomorphic function on ℂ−{0, −1, −2, …} defined by the series

ψ^{(k)}(z) = (−1)^{k+1}k! ∑_{n=0}^{∞}(z + n)^{−k−1}.

Let 0 < θ < \frac{π}{2} and S_{θ} = \{z ∈ ℂ | z ≠ 0, | arg z| ≤ π − θ\}. Finite order asymptotic expansion of polygamma function on S_{θ} is

ψ^{(k)}(z) = (−1)^{k+1}(\frac{(k − 1)!}{z^{k}} + \frac{k!}{2z^{k+1}} + ∑_{n=1}^{p} B_{2n} \frac{(2n + k − 1)!}{(2n)!z^{2n+k}} + O_{p,θ}(\frac{1}{z^{k+2p+1}} ))

where p is any positive integer. Hence on S_{θ}

\frac{1}{∑_{n=0}^{∞}(z + n)^{−k−1}}

= kz^{k}(1 + \frac{k}{2z} + k ∑_{n=1}^{p} \frac{B_{2n}}{2n} \binom{k + 2n − 1}{2n − 1}z^{−2n} + O_{p,θ}(\frac{1}{z^{2p+1}} ))^{−1}.  (47)

As z → ∞ on the sector one can expand the right-hand side to get asymptotic expansion up to arbitrary high order by choosing a large p. One can put p = ⌈\frac{k}{2}⌉ to retrieve the first k terms in the asymptotic expansion of \frac{1}{∑_{n=0}^{∞}(z+n)^{−k−1}} . These formulas give an alternate gateway to results of this subsection as mentioned in introduction.

4.3.2 Numerical formula

Let k ≥ 2. Consider the sequence defined by x_{m} = m^{−k}, m ≥ 1. We explicitly determine the reciprocal sequences associated with (x_{m})_{m≥1} for small values of k. Set up is same as beginning of this section, i.e., R(X) = P (X) = A(X) = X^{k}, Q(X) = 1 and B(X) = 0. Notation and arguments from the proof of Theorem 1 and Section 4.1 are frequently used in the discussion below. Here M_{0} = 0, which is compatible with theory in Section 4.1.

4.3.3 k = 2

(Xin [6]) Using (46) we have (c_{0}, c_{1}) = (1, −\frac{1}{2}). Hence L = 1 and one needs to use Case I. It is clear that c(1) = −1. From explicit expression of f_{P} (−1, X) and numerator polynomials it follows that 2 is a legitimate choice for N. Hence

a_{n} = n − 1 (n ≥ 2).

4.3.4 k = 3

(Xin [6]) By (46) one concludes (c_{0}, c_{1}, c_{2}) = (2, −2, 1). Here L = 1 and we are in the situation of Case II. Therefore, the constant term has to be c_{k−1} or c_{k−1} − 1. Note that N(f_{P} (c_{k−1}), P, X) is a degree 0 polynomial with negative leading coefficient. Hence c(1) = c_{k−1} − 1 = 0. It is easy to see that N = 2 is a legitimate choice. Thus

a_{n} = 2n(n − 1) (n ≥ 2).

4.3.5 k = 4

(Xu [7]) From (46) it follows that (c_{0}, c_{1}, c_{2}, c_{3}) = (3, −\frac{9}{2}, \frac{15}{4}, −\frac{9}{8}). Here L = 4 and Case I holds. All residue classes are nontrivial and c(1) = −\frac{5}{4}, c(2) = −\frac{3}{2}, c(3) = −\frac{7}{4}, c(4) = −2. The choice of constants M_{f_{P} (c)} = 1, M_{1} = M_{2} = 1 works for c = c(2), c(3), c(4). If the constant term is c(1), then a legitimate choice is M_{f_{P} (c)} = M_{2} = 0, M_{1} = 5. Therefore N(2), N(3), N(4) = 1 and N(1) = 5 is a legitimate choice of constants. Hence N = 5 and for all n ≥ 5

a_{n} = \begin{cases}3n^{3} − \frac{9}{2}n^{2} + \frac{15}{4}n − \frac{5}{4}, & if n ≡ 1 (mod 4); \\ 3n^{3} − \frac{9}{2}n^{2} + \frac{15}{4}n − \frac{3}{2}, & if n ≡ 2 (mod 4); \\ 3n^{3} − \frac{9}{2}n^{2} + \frac{15}{4}n − \frac{7}{4}, & if n ≡ 3 (mod 4); \\ 3n^{3} − \frac{9}{2}n^{2} + \frac{15}{4}n − 2, & if n ≡ 4 (mod 4). \end{cases}

4.4 k = 5

(Xu [7]) Using (46) we see that (c_{0}, c_{1}, c_{2}, c_{3}, c_{4}) = (4, −8, \frac{28}{3}, −\frac{16}{3}, −\frac{2}{9}). Hence L = 3 and Case I holds. Nontrivial residue classes modulo L with respect to H_{L}(X) are {2, 3} and c(2) = −\frac{2}{3}, c(3) = −1. The choice of constants M_{f_{P} (c)} = 2, M_{1} = 1, M_{2} = 5 works for c ∈ {c(2), c(3)}. Therefore N = 5 and for all n ≥ 5

a_{n} = \begin{cases}4n^{4} − 8n^{3} + \frac{28}{3}n^{2} − \frac{16}{3}n − 1, & if n ≡ 1 (mod 3); \\ 4n^{4} − 8n^{3} + \frac{28}{3}n^{2} − \frac{16}{3}n − \frac{2}{3}, & if n ≡ 2 (mod 3); \\ 4n^{4} − 8n^{3} + \frac{28}{3}n^{2} − \frac{16}{3}n − 1, & if n ≡ 3 (mod 3). \end{cases}

Remark 18. The results for k = 4, 5 answer questions of Kotesovec [5]. Theorem 15 provides an algorithmically computable answer to the problem of determining reciprocal sequence for a large class.

5 Complements: Sequence of polynomials

The discussion in Section 4.3 leads to new kind of formalism. Let 𝕂 be a field of characteristic 0 and (P_{k}(X))_{k≥1} be sequence of polynomials in 𝕂[X] such that d_{k} = deg_{𝕂}P_{k} ≥ 2 for all k ≥ 1 and d_{k} → ∞ as k → ∞. For r ∈ ℤ_{≥0} define

m_{r} = min{k_{0} ∈ ℕ | k ≥ k_{0} ⟹ d_{k} ≥ r + 1}.

Write I_{r} = {k ∈ ℕ | k ≥ m_{r}}. By Lemma 4 one has a well defined function c_{r} : I_{r} → 𝕂 given by c_{r}(k) = c_{r}(P_{k}). Since the system equations

u_{i}(X) = v_{i}(X, P_{k}) X = (X_{0}, …, X_{r}), (0 ≤ i ≤ r ≤ d_{k} − 1)

determines c_{r}(k), it depends only on coefficients of X^{d_{k}}, …, X^{d_{k}−r} in P_{k}(X). These coefficients are denoted by a_{0}(k), …, a_{r}(k) respectively.

We can study behavior of this function for different sequences. The subsequent remark summarizes some examples of interest.

Example 19.

(i) Let P_{k}(X) = X^{k+1} ∈ ℚ[X]. Note that

a_{r}(k) = \begin{cases}1, & r = 0; \\ 0, & r ≥ 1. \end{cases}

One uses recursion argument of Lemma 4 to conclude that there is a rational function C_{r}(X) ∈ ℚ(X) so that c_{r}(k) = C_{r}(X) for all k ∈ I_{r} (cf. Section 4.3). For r ≥ 1 these rational functions are divisible by X^{2}. Moreover, the asymptotic expansion in (47) implies that these rational functions are actually polynomials.

(ii) Let a ∈ 𝕂, and P (X) ∈ 𝕂[X] be a non-constant polynomial. Suppose that P_{k}(X) = P (X)(X + a)^{k} ∈ 𝕂[X]. For this sequence a_{0}(k) = a_{0}(P). Suppose that k ≥ r. Then a_{r}(k) is 𝕂-linear combination of elements of the form

\{\binom{k}{j}a^{j} | 0 ≤ j ≤ r\}

with coefficients independent of k. By recursion argument there exists a rational function C_{r}(X) ∈ 𝕂(X) such that c_{r}(k) = C_{r}(k) for k ≫ 1.

(iii) Let P (X), Q(X) ∈ 𝕂[X] be so that deg_{𝕂}P, deg_{𝕂}Q ≥ 1. Construct a sequence by P_{k}(X) = P (X)Q(X)^{k}. Assume leading coefficient of P (X) is a_{0}(P) and

Q(X) = X^{d} + A_{1}X^{d−1} + ⋯ + A_{d} ∈ 𝕂[X]

with d ≥ 1. Therefore a_{0}(k) = a_{0}(P). Using multinomial theorem we deduce that if k ≥ dr then a_{r}(k) is a 𝕂-linear combination of elements

\{\binom{k}{j}A^{j} | j = (j_{0}, …, j_{d}) ∈ ℤ_{≥0}^{d+1}, ∑_{s=0}^{d} j_{s} = k, 0 ≤ ∑_{s=0}^{d} sj_{s} ≤ r\}

whose coefficients are independent of k. Observe that constraints on j imply that j_{0} ≥ k − rd and j_{s} ≤ r for all 1 ≤ s ≤ r. For k ≥ dr all possible choices for j appear and these depend only on d, r. Then each of these multinomial terms is a polynomial in k of degree ≤ dr. Using recursion, we can construct C_{r}(X) ∈ 𝕂(X) such that c_{r}(k) = C_{r}(X) for k ≫ 1.

In special cases one can use recursion to find finer properties of these functions which indicate possibility of richer structure.

6 Acknowledgments

I wish to thank Prof. P. Rath (CMI) for useful comments on an earlier draft. Part of this work was developed during my stay in Chennai Mathematical Institute.

References

[1] M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions With Formulas, Graphs and Mathematical Tables, National Bureau of Standards, tenth printing, 1972.

[2] P. Anantakitpaisal and K. Kuhapatanakul, Reciprocal sums of the Tribonacci numbers, J. Integer Sequences 19 (2016), Article 16.2.1.

[3] T. Komatsu and V. Laohakosol, On the sum of reciprocals of numbers satisfying a recurrence relation of order s, J. Integer Sequences 13 (2010), Article 10.5.8.

[4] H. Ohtsuka and S. Nakamura, On the sum of reciprocal Fibonacci numbers, Fibonacci Quart. 46/47 (2008/2009) 153–159.

[5] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2020.

[6] L. Xin, Some identities related to Riemann zeta-function, J. Inequal. Appl. (2016), Paper no. 32.

[7] H. Xu, Some computational formulas related Riemann zeta-function tails, J. Inequal. Appl. (2016), Paper no. 132.

2010 Mathematics Subject Classification: Primary 11B83; Secondary 39A05, 40A25. Keywords: reciprocal sum, difference primitive.

(Concerned with sequences \underline{A248230} and \underline{A248234}.)

Received June 11 2017; revised versions received June 11 2020; August 13 2020; November 28 2020; November 29 2020. Published in Journal of Integer Sequences, December 2 2020.

Return to Journal of Integer Sequences home page.