On the Sum of Reciprocals of Numbers Satisfying a Recurrence Relation of Order s

Takao Komatsu^{1} Graduate School of Science and Technology Hirosaki University Hirosaki, 036-8561 Japan

              komatsu@cc.hirosaki-u.ac.jp

Vichian Laohakosol^{2} Department of Mathematics Kasetsart University Bangkok 10900 Thailand

                   fscivil@ku.ac.th

Abstract

We discuss the partial infinite sum ∑_{k=n}^{∞} u_{k}^{−s} for some positive integer n, where u_{k} satisfies a recurrence relation of order s, u_{n} = au_{n−1} + u_{n−2} + ⋯ + u_{n−s} (n ≥ s), with initial values u_{0} ≥ 0, u_{k} ∈ ℕ (0 ≤ k ≤ s − 1), where a and s(≥ 2) are positive integers. If a = 1, s = 2, and u_{0} = 0, u_{1} = 1, then u_{k} = F_{k} is the k-th Fibonacci number. Our results include some extensions of Ohtsuka and Nakamura. We also consider continued fraction expansions that include such infinite sums.

1 The first author was supported in part by the Grant-in-Aid for Scientific Research (C) (No. 22540005), the Japan Society for the Promotion of Science.

2 The second author was supported in part by the Commission on Higher Education and the Thailand Research Fund RTA5180005.

1 Introduction

The so-called Fibonacci zeta function is defined by

ζ_{F} (s) = ∑_{n=1}^{∞} \frac{1}{F_{n}^{s}} ,

where F_{n} is the n-th Fibonacci number satisfying the recurrence formula

F_{n} = F_{n−1} + F_{n−2} (n ≥ 2), F_{0} = 0, F_{1} = 1 .

Ohtsuka and Nakamura [8] studied the partial infinite sums of reciprocal Fibonacci numbers ∑_{k≥n}^{∞} 1/F_{k}^{s}. They gave an explicit formula for the integer part of (∑_{k≥n}^{∞} F_{k}^{−1})^{−1} and (∑_{k≥n}^{∞} F_{k}^{−2})^{−1}. Holliday and Komatsu [2] generalized these results to the cases of G_{n} and H_{n}, satisfying G_{n} = aG_{n−1} + G_{n−2} (n ≥ 2) with G_{0} = 0 and G_{1} = 1, and H_{n} = H_{n−1} + H_{n−2} (n ≥ 2) with H_{0} = c and H_{1} = 1, where a ≥ 1 and c ≥ 0 are integers. In this paper we shall not consider the integer part, but the nearest integer function of (∑_{k≥n}^{∞} u_{k}^{−1})^{−1}, where {u_{k}}_{k≥0} is a sequence of non-negative integers satisfying a linear recurrence formula of the type

u_{n} = au_{n−1} + u_{n−2} + ⋯ + u_{n−s} ,

where a and s (≥ 2) are positive integers. Here, ∥ · ∥ denotes the nearest integer^{3}, namely, ∥x∥ = ⌊x + 1/2⌋. Our main result is the following:

Theorem 1. Let {u_{n}}_{n≥0} be an integer sequence satisfying the recurrence formula

u_{n} = au_{n−1} + u_{n−2} + ⋯ + u_{n−s} (n ≥ s)  (1)

with initial conditions

u_{0} ≥ 0, u_{k} ∈ ℕ (0 ≤ k ≤ s − 1) ,  (2)

where a and s (≥ 2) are positive integers. Then there is a positive integer n_{0} such that

∥(∑_{k=n}^{∞} \frac{1}{u_{k}} )^{−1}∥ = u_{n} − u_{n−1} (n ≥ n_{0}) .  (3)

If a = 1, u_{0} = 0, u_{1} = u_{2} = 1, u_{3} = 2, ⋯, u_{s−1} = 2^{s−3}, then the u_{n}’s are generalized Fibonacci numbers (sometimes called “Fibonacci s-step numbers” [1]). If s = 2, then u_{k} = F_{k} are Fibonacci numbers, while if s = 3, then u_{k} = T_{k} are Tribonacci numbers.

We need the following two lemmas in order to prove this theorem.

Lemma 2. Let a, s ∈ ℕ, s ≥ 2 and let

f(x) = x^{s} − ax^{s−1} − x^{s−2} − ⋯ − x − 1.

Then (a) f(x) has exactly one positive simple zero α ∈ ℝ with a < α < a + 1;

3In other contexts, this notation is sometimes used for the distance from the nearest integer.

(b) the remaining s − 1 zeros of f(x) lie within the unit circle in the complex plane. Proof. The case where a = 1 can be found in [7], so we assume from now on that a ≥ 2.

By Descarte’s rule of signs, we see that f(x) has at most one positive real zero. Since f(a) < 0 and f(a + 1) > 0, its unique positive real zero, say α, satisfies (2 ≤) a < α < a + 1. Since multiple roots are counted separately by Descarte’s rule again, part (a) is proved. Observe from part (a) that

for real x > α, we have f(x) > 0,  (4)
while for real 0 < x < α, we have f(x) < 0.  (5)

Next, let

g(x) = (x − 1)f(x) = x^{s+1} − (a + 1)x^{s} + (a − 1)x^{s−1} + 1.

Observe further that

for real x > α, we have g(x) > 0,  (6)
while for real 1 < x < α, we have g(x) < 0.  (7)

To prove part (b), we proceed by establishing several claims. Claim 1. f(x) has no complex zero z_{1} with |z_{1}| > α. Proof of Claim 1. If 0 = f(z_{1}) = z_{1}^{s} − az_{1}^{s−1} − z_{1}^{s−2} − ⋯ − z_{1} − 1, then

|z_{1}|^{s} ≤ a |z_{1}|^{s−1} + |z_{1}|^{s−2} + ⋯ + |z_{1}| + 1,

which implies that f (|z_{1}|) ≤ 0, contradicting (4). Claim 2. f(x) has no complex zero z_{2} with 1 < |z_{2}| < α. Proof of Claim 2. If f(z_{2}) = 0, then 0 = g(z_{2}) = z_{2}^{s+1} − (a + 1)z_{2}^{s} + (a − 1)z_{2}^{s−1} + 1 and so

(a + 1) |z_{2}|^{s} ≤ |z_{2}|^{s+1} + (a − 1) |z_{2}|^{s−1} + 1,

i.e., g (|z_{2}|) ≥ 0, contradicting (7). Claim 3. f(x) has no complex zero z_{3} ≠ α, with either |z_{3}| = α or |z_{3}| = 1. Proof of Claim 3. If f(z_{3}) = 0, then

0 = g(z_{3}) = z_{3}^{s+1} − (a + 1)z_{3}^{s} + (a − 1)z_{3}^{s−1} + 1  (8)

so that

(a + 1) |z_{3}|^{s} ≤ |z_{3}|^{s+1} + (a − 1) |z_{3}|^{s−1} + 1.  (9)

If |z_{3}| = α or |z_{3}| = 1, then g (|z_{3}|) = 0 and so (9) must be an equality. Then the two conditions z_{3}^{s+1} and z_{3}^{s−1} ∈ ℝ, or z_{3}^{s+1} = −(a − 1)z_{3}^{s−1} follow from two applications of the fact that

|z_{1} + z_{2}| = |z_{1}| + |z_{2}| ⟺ \frac{z_{1}}{z_{2}} ∈ ℝ_{≥0} (for z_{2} ≠ 0)

and from

(z_{1} + z_{2} ∈ ℝ ∧ \frac{z_{1}}{z_{2}} ∈ ℝ) ⟹ (z_{1}, z_{2} ∈ ℝ ∨ z_{1} = −z_{2}) .

• If z_{3}^{s+1} and z_{3}^{s−1} ∈ ℝ, then (8) shows that z_{3}^{s} ∈ ℝ, which in turn forces z_{3} ∈ ℝ. Thus, z_{3} = ± α or z_{3} = ± 1. The possibility z_{3} = α is ruled out by the hypothesis, and the possibility z_{3} = 1 is ruled out by (5). To rule out the remaining two possibilities of negative zeros, consider

g(−x) = \begin{cases}−x^{s+1} − (a + 1)x^{s} − (a − 1)x^{s−1} + 1, & if s is even; \\ x^{s+1} + (a + 1)x^{s} + (a − 1)x^{s−1} + 1, & if s is odd. \end{cases}  (10)

By Descarte’s rule of signs applied to g(−x), we deduce that g(x) and so also f(x), has at most one real negative zero if s is even and has no real negative zeros if s is odd. When s is even, since f(0) = −1, f(−1) = a > 0, should f(x) have a real negative zero, such zero must lie in the interval (−1, 0) and so can neither be −α nor −1.

• If z_{3}^{s+1} = −(a − 1)z_{3}^{s−1}, then (8) gives z_{3}^{s} = \frac{1}{a+1}. Thus, either

2^{s} ≤ a^{s} < |α|^{s} = |z_{3}|^{s} = \frac{1}{a + 1} ≤ \frac{1}{3} or 1 = |z_{3}|^{s} = \frac{1}{a + 1} ≤ \frac{1}{3}.

Both possibilities are untenable and Claim 3 is proved.

Part (b) now follows from Claims 1–3.

We shall keep the notation of Lemma 2 throughout the rest of the paper.

Lemma 3. Let s ≥ 2 and let {u_{n}}_{n≥0} be an integer sequence satisfying the recurrence formula (1) and the initial conditions (2). Then there are real numbers c > 0, d > 1, and α > a such that

u_{n} = cα^{n} + O(d^{−n})  (n → ∞) .  (11)

Proof. Let α_{1} = α, α_{2}, …, α_{t} with |α_{j}| < 1 (2 ≤ t ≤ s) be the distinct roots of f(x), and let r_{j} for j = 2, 3, …, t denote the multiplicity of the root α_{j}. Then the expansion formula (11) follows from the shape of u_{n}, which is given by

u_{n} = cα^{n} + ∑_{j=2}^{t} P_{j}(n)α_{J}^{n} ,

where

P_{j}(x) ∈ ℝ[x],  degP_{j} = r_{J} − 1,  1 + r_{2} + r_{3} + ⋯ + r_{t} = s .

Proof of Theorem 1. Applying Lemma 3 and the expansion formula

\frac{1}{1 ± ϵ} = 1 ∓ ϵ + O(ϵ^{2}) = 1 + O(ϵ) (ϵ → 0) ,

we have

\frac{1}{u_{k}} = \frac{1}{cα^{k} + O(d^{−k})} = \frac{1}{cα^{k}(1 + O((αd)^{−k})))}

= \frac{1}{cα^{k}} (1 + O((αd)^{−k}))) = \frac{1}{cα^{k}} + O((α^{2}d)^{−k}) ,

Since

∑_{k=n}^{∞} \frac{1}{u_{k}} = \frac{1}{c} ∑_{k=n}^{∞} \frac{1}{α^{k}} + O (∑_{k=n}^{∞}(α^{2}d)^{−k})

= \frac{α}{c(α − 1)}α^{−n} + O((α^{2}d)^{−n}) ,

we obtain

(∑_{k=n}^{∞} \frac{1}{u_{k}} )^{−1} = \frac{α − 1}{α}cα^{n} + O(d^{−n})
= u_{n} − u_{n−1} + O(d^{−n}) .

Theorem 1 follows by choosing n ≥ n_{0} sufficient large so that the modulus of the last error term becomes less than 1/2.

2 Related results

The following results are similarly obtained. Here, n_{1}, n_{2}, n_{3}, n_{4} and n_{5} are positive integers depending only on a.

Theorem 4.

∥(∑_{k=n}^{∞} \frac{1}{u_{2k}} )^{−1}∥ = u_{2n} − u_{2n−2} (n ≥ n_{1}) .  (12)

∥(∑_{k=n}^{∞} \frac{1}{u_{2k−1}} )^{−1}∥ = u_{2n−1} − u_{2n−3} (n ≥ n_{2}) .  (13)

∥(∑_{k=n}^{∞} \frac{(−1)^{k}}{u_{k}} )^{−1}∥ = (−1)^{n}(u_{n} + u_{n−1}) (n ≥ n_{3}) .  (14)

∥(∑_{k=n}^{∞} \frac{(−1)^{k}}{u_{2k}} )^{−1}∥ = (−1)^{n}(u_{2n} + u_{2n−2}) (n ≥ n_{4}) .  (15)

∥(∑_{k=n}^{∞} \frac{(−1)^{k}}{u_{2k−1}} )^{−1}∥ = (−1)^{n}(u_{2n−1} + u_{2n−3}) (n ≥ n_{5}) .  (16)

Proof. We shall prove only (14). The other identities are proved similarly. By (11) we get

∑_{k=n}^{∞} \frac{(−1)^{k}}{u_{k}} = ∑_{k=n}^{∞} \frac{(−1)^{k}}{cα^{k} + O(d^{−k})}

= ∑_{k=n}^{∞} \frac{(−1)^{k}}{cα^{k}} (1 + O((αd)^{−k}))

= \frac{α}{c(−α)^{n}(α + 1)} + O ((−α^{2}d)^{−n}) .

By taking its reciprocal, we have

(∑_{k=n}^{∞} \frac{(−1)^{k}}{u_{k}} )^{−1} = \frac{c(−α)^{n}(α + 1)}{α} (1 + O((αd)^{−n}))
= (−1)^{n}(cα^{n} + cα^{n−1}) + O((−d)^{−n})
= (−1)^{n}(u_{n} + u_{n−1}) + O(d^{−n}) .

The identity (14) follows by choosing n ≥ n_{3} sufficiently large so that the modulus of the last error term becomes less than 1/2.

3 The sum of reciprocal Tribonacci numbers

The so-called Tribonacci numbers T_{n} ([6, Ch. 46], [9, sequence \underline{A000073}], [3]) are defined by

T_{n} = T_{n−1} + T_{n−2} + T_{n−3} (n ≥ 3), T_{0} = 0, T_{1} = T_{2} = 1 .

By setting a = 1, s = 3 and u_{k} = T_{k} (k ≥ 0) in Theorem 1 and Theorem 4, we get some identities about the partial Tribonacci zeta functions. Numerical evidences imply that identities hold for smaller positive integers n, as indicated in the identities. The detailed explanations for small n can be seen in [5].

Corollary 5.

∥(∑_{k=n}^{∞} \frac{1}{T_{k}} )^{−1}∥ = T_{n} − T_{n−1} (n ≥ 1) .  (17)

∥(∑_{k=n}^{∞} \frac{1}{T_{2k}} )^{−1}∥ = T_{2n} − T_{2n−2} (n ≥ 1) .  (18)

∥(∑_{k=n}^{∞} \frac{1}{T_{2k−1}} )^{−1}∥ = T_{2n−1} − T_{2n−3} (n ≥ 2) .  (19)

∥(∑_{k=n}^{∞} \frac{(−1)^{k}}{T_{k}} )^{−1}∥ = (−1)^{n}(T_{n} + T_{n−1}) (n ≥ 2) .  (20)

∥(∑_{k=n}^{∞} \frac{(−1)^{k}}{T_{2k}} )^{−1}∥ = (−1)^{n}(T_{2n} + T_{2n−2}) (n ≥ 1) .  (21)

∥(∑_{k=n}^{∞} \frac{(−1)^{k}}{T_{2k−1}} )^{−1}∥ = (−1)^{n}(T_{2n−1} + T_{2n−3}) (n ≥ 2) .  (22)

4 Continued fraction expansion of generalized m-step zeta functions

The first author [4] studied several continued fraction expansions of some types of Fibonacci zeta functions ζ_{F} (s) := ∑_{n=1}^{∞} F_{n}^{−s} and Lucas zeta functions in ζ_{L}(s) := ∑_{n=1}^{∞} L_{n}^{−s}, where L_{n} is the n-th Lucas number defined by

L_{n} = L_{n−1} + L_{n−2} (n ≥ 2) L_{0} = 2, L_{1} = 1.

A continued fraction expansion of the generalized m-step zeta functions defined by ζ_{u^{(m)}}(s) := ∑_{n=1}^{∞} u_{n}^{−s}, where

u_{n} = au_{n−1} + u_{n−2} + ⋯ + u_{n−m} (n ≥ m)

with initial positive integral values u_{k} (0 ≤ k ≤ m − 1), is given by

ζ_{u^{(m)}}(s) = \frac{1}{u_{1}^{s} − \frac{u_{1}^{2s}}{u_{1}^{s} + u_{2}^{s} − \frac{u_{2}^{2s}}{u_{2}^{s} + u_{3}^{s} − \frac{u_{3}^{2s}}{u_{3}^{s} + u_{4}^{s} − ... − \frac{u_{n−1}^{2s}}{u_{n−1}^{s} + u_{n}^{s} − ⋯}}}}} .

Define A_{n} (respectively, B_{n}) as the numerator (respectively, denominator) of the n^{th} convergent of the continued fraction expansion given for ζ_{u^{(m)}}(s):

\frac{A_{n}}{B_{n}} = \frac{1}{u_{1}^{s} − \frac{u_{1}^{2s}}{u_{1}^{s} + u_{2}^{s} − \frac{u_{2}^{2s}}{u_{2}^{s} + u_{3}^{s} − \frac{u_{3}^{2s}}{u_{3}^{s} + u_{4}^{s} − ... − \frac{u_{n−1}^{2s}}{u_{n−1}^{s} + u_{n}^{s}}}}}} .

Hence {A_{ν}}_{ν≥0} and {B_{ν}}_{ν≥0} satisfy the following recurrence formulas.

A_{ν} = (u_{ν−1}^{s} + u_{ν}^{s})A_{ν−1} − u_{ν−1}^{2s}A_{ν−2}  (ν ≥ 2),  A_{0} = 0,  A_{1} = 1;
B_{ν} = (u_{ν−1}^{s} + u_{ν}^{s})B_{ν−1} − u_{ν−1}^{2s}B_{ν−2}  (ν ≥ 2),  B_{0} = 1,  B_{1} = u_{1}^{s}

In fact, A_{ν} and B_{ν} can be expressed explicitly as follows.

Lemma 6. For n = 1, 2, …

A_{n} = (u_{1}u_{2} ⋯ u_{n})^{s} ∑_{ν=1}^{n} \frac{1}{u_{ν}^{s}} , B_{n} = (u_{1}u_{2} ⋯ u_{n})^{s} .

Proof. By induction we have B_{n} = (u_{1}u_{2} ⋯ u_{n})^{s}. Thus,

A_{n} = B_{n} ∑_{ν=1}^{n} \frac{1}{u_{ν}^{s}} = (u_{1}u_{2} ⋯ u_{n})^{s} ∑_{ν=1}^{n} \frac{1}{u_{ν}^{s}} .

Theorem 1 provides us with interesting information about the nearest integer of the reciprocal of ζ_{u^{(m)}}(s) − A_{n}/B_{n}.

References

[1] Eric Weisstein, World of Mathematics, published electronically at

   http://mathworld.wolfram.com/Fibonaccin-StepNumber.html.

[2] S. H. Holliday and T. Komatsu, On the sum of reciprocal generalized Fibonacci numbers, submitted.

[3] E. Kiliç, Tribonacci sequences with certain indices and their sums, Ars Combin. 86 (2008), 13–22.

[4] T. Komatsu, On continued fraction expansions of Fibonacci and Lucas Dirichlet series, Fibonacci Quart. 46/47 (2008/2009), 268–278.

[5] T. Komatsu, On the sum of reciprocal Tribonacci numbers, Ars Combin., to appear.

[6] T. Koshy, Fibonacci and Lucas Numbers with Applications, John Wiley & Sons, 2001.

[7] M. D. Miller, On generalized Fibonacci numbers, Amer. Math. Monthly 78 (1971), 1108–1109.

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

[9] N. J. A. Sloane, (2010), The On-Line Encyclopedia of Integer Sequences, published

   electronically at http://www.research.att.com/~njas/sequences/ .

2010 Mathematics Subject Classification: Primary 11A55; Secondary 11B39. Keywords: Fibonacci numbers, recurrence relations of s-th order, partial infinite sum.

(Concerned with sequence \underline{A000073}.)

Received January 20 2010; revised version received May 19 2010. Published in Journal of Integer Sequences, May 20 2010.

Return to Journal of Integer Sequences home page.