A Self-Indexed Sequence

23 11

Article 05.3.5

Journal of Integer Sequences, Vol. 8 (2005),

2 3 6 1

47

A Self-Indexed Sequence

Emmanuel Preissmann 11 rue Vinet 1004 Lausanne

Switzerland

[email protected]

Abstract

We investigate the integer sequence (tn)_n∈Z defined by t_n = 0 if n ≤ 0, t₁ = 1, and tn = Pn−1

i=1 tn−ti for n ≥ 2. This sequence has the following properties: if we considerf_n(X) :=−1 +Pn

i=1X^ti and takex_nto be the real positive number such that f_n(xn) = 0, then

n→∞lim t_n

t_n+1 = lim

n→∞x_n= 0.410098516· · · Moreover, if u is the real positive number such that 1 = P∞

i=1u^−ti, then there is a positive constantM such that t_n∼M uⁿ.

1 Definitions and main results

If we look in theOnline Encyclopedia of Integer Sequences of N. J. A. Sloane [1], we find a remarkable sequence by (tn)_n∈Z defined by t_n= 0 if n ≤0,t₁ = 1 and

t_n =

n−1

X

i=1

t_n−ti (1.1)

for n ≥2. This sequence is due to Robert Lozyniak (A052109 in Sloane) and is a cousin of the Hofstadter-Conway $10,000 challenge sequence (A004001in Sloane).

We find t₂ = 1, t₃ = 2, t₄ = 5, t₅ = 12, t₆ = 30, t₇ = 73, . . . Observe that if n ≥ 2 , t_n+1 = 2tn+· · · ≥2tn. Since t₄ = 4 + 1, we have

t_n ≥n+ 1 (n≥4) (1.2)

The serieP∞

i=1X^ti = 2X+X²+· · · converges for|X|<1. Letube the real positive number

such that _∞

X

i=1

u^−ti = 1 (1.3)

We easily see that 2< u <3. Indeed we have P∞ i=1

¡₁

2

¢ti

= ¹₂+¹₂+· · ·>1 andP∞ i=1

¡₁

3

¢ti

<

2

3 +¹₉P∞ i=0

¡₁

3

¢i

= ⁵₆.

Theorem 1.1. There exists a positive constant M such that

n→∞lim t_n uⁿ =M.

Corollary 1.1. Let n ≥ 2 be an integer. Let f_n(X) = −1 +Pn

i=1X^ti and take x_n the real positive number such that f_n(x_n) = 0. Then

n→∞lim t_n t_n+1 = 1

u = lim

n→∞x_n= 0.410098516· · · . Proof. By the theorem, t_n ∼M uⁿ, therefore limn→∞ tn

tn+1 = _u¹ . In addition, the sequence (xn)^∞_n=1 is strictly decreasing. Indeed,

n

X

i=1

x^t_nⁱ = 1 =

n+1

X

i=1

x^t_n+1ⁱ

so that _n

X

i=1

¡x^t_n+1ⁱ −x^t_nⁱ¢

=−x^t_n+1ⁿ⁺¹ <0

This proves thatx_n+1 < x_n for every n. Moreover, this sequence is bounded, so it converges to an element, say v. The function f∞(x) = −1 +P∞

i=1x^ti is continuous. Let ² > 0. We have

0< f_∞(x_n) =

∞

X

i=n+1

x^t_nⁱ < ² if n is big enough. Finally,

f∞(v) = lim

n→∞f∞(xn) = 0.

That is, v = ¹_u, because _u¹ is the only positive zero of f∞.

2 Proof of the Theorem

We begin with a lemma:

Lemma 2.1. If 0 ≤ v_n < 1 for every integer n > 0, then the following inequalities are equivalent

∞

X

n=1

vn < ∞ (2.1)

∞

Proof. Without loss of generality, we can suppose that v_n ≤ ¹₂. If an infinite number of v_n > ¹₂, the claims 2.1 and 2.2 are both wrong, otherwise we can take out the finite number of v_n > ¹₂. By Taylor expansion, we have for 0 ≤x≤ ¹₂

−log(1−x) =x+ 1 2

x²

(1−θx)², 0≤θ ≤1;

hence x≤ −log(1−x)≤2x for 0≤x≤ ¹₂. It follows that for every integer N >0 we have

N

X

n=1

v_n≤ −log

N

Y

n=1

(1−v_n)≤2

N

X

n=1

v_n.

So the lemma is proved.

Lemma 2.2. There exists a constant d such that 0< d≤ t_n

uⁿ for every integer n >0.

Proof. Suppose that n≥4 and d_n is such that 0< d_n ≤ _u^tkk for 1≤k≤n. Then we have t_n+1 =

n

X

i=1

t_n+1−ti ≥

n

X

i=1 n+1−ti>0

d_nu^n+1−ti.

By Eq. (1.2), n+ 1−t_n ≤0. Hence t_n+1 ≥d_nuⁿ⁺¹

n

X

i=1 n+1−ti>0

u^−ti =d_nuⁿ⁺¹

∞

X

i=1 n+1−ti>0

u^−ti =d_nuⁿ⁺¹(1−v_n)

wherev_n=P∞

i=1, ti≥n+1u^−ti by definition of u. So we have d_n(1−v_n)≤ t_k

u^k for 1≤k≤n+ 1. (2.3)

The series

∞

X

n=4

v_n =

∞

X

n=4

∞

X

i=1 ti≥n+1

u^−ti =

∞

X

i=1

u^−ti

∞

X

4≤n<ti

1 =

∞

X

i=4

u^−ti(ti−4)

is convergent; just compare this sum with _(X−1)¹ 2 = P∞

i=1iXⁱ⁻¹ for |X| < 1. Set d₄ = min₁≤k≤4 tk

u^k. By Lemma2.1and (2.3),d =d₄Q∞

n=4(1−v_n) is such that 0< d≤ _u^tnn for every positive integer n.

Lemma 2.3. For every integer n, one has t_n ≤uⁿ⁻¹.

Proof. If n ≤ 1, this is evident. Suppose that n ≥ 1 and by induction that t_i ≤ uⁱ⁻¹ when i≤n. Then by (1.1) and (1.3), we have

t_n+1 =

n

X

i=1

t_n+1−ti ≤

n

X

i=1

u^n−ti ≤

∞

X

i=1

u^n−ti =uⁿ.

Remark 2.1. Let N ≥ 1. Set C_N = sup_n≥N¡_tn

uⁿ

¢ and D_N = infn≥N

¡_tn

uⁿ

¢. Lemmas 2.2 and 2.3 prove that C = limN→∞C_N and D= limN→∞D_N with 0< D≤C are meaningful.

Define (t⁰_n)_n∈Z by t⁰_i = 0 when i≤1, t⁰₂ = 1 and for n ≥3 define t⁰_n=

∞

X

i=1

t⁰_n−ti. (2.4)

Define also (an)_n∈Z bya_n= 0 when n≤0, a₁ = 1 and for n ≥2:

a_n= 1 +

∞

X

i=1

a_n−ti. (2.5)

Lemma 2.4. Let n, N, k be positive integers such that n > N ≥1. Then we have t_n+k ≤t⁰_k+2t_n+u^n+kC_N

µ

1− t⁰_k+2 u^k

¶

+a_ku^N.

Proof. By induction on k. For k = 0, the claim is true. Suppose that l ≥ 1 and that the lemma is true for k = 0,1, . . . ,(l−1). By Eq. (1.1),

t_n+l =

n+l−1

X

i=1

t_n+l−ti ≤

∞

X

i=1

t_n+l−ti = Σ₁+ Σ₂+ Σ₃ where

Σ1 =

∞

X

i=1 n+l−ti≥n

t_n+l−ti

Σ2 =

∞

X

i=1 N≤n+l−ti<n

t_n+l−ti

Σ3 =

∞

X

i=1 n+l−ti<N

t_n+l−ti.

By induction we have

∞

X µ

n+l−t t⁰_l−t+2 ¶

By the definition ofC_N

Σ2 ≤

∞

X

i=1 N≤n+l−ti<n

C_Nu^n+l−ti.

By Lemma 2.3 and the fact that u >2, Σ3 ≤

N

X

i=1

t_i ≤

N−1

X

i=0

uⁱ = u^N −1

u−1 < u^N. Finally

t_n+l ≤t_n X

i≥1 l−ti≥0

t⁰_l−t

i+2+C_N X

i≥1 n+l−ti≥N

u^n+l−ti−C_N X

i≥1 l−ti≥0

uⁿt⁰_l−t

i+2+ X

i≥1 l−ti≥0

a_l−tiu^N +u^N.

This means by (2.4), (2.5) and (1.3) that

t_n+l ≤t⁰_l+2t_n+u^n+lC_N(1− t⁰_l+2

u^l ) +a_lu^N.

Lemma 2.5. There exists d⁰ >0 such that d⁰ ≤ _u^t0nn for every n≥2.

Proof. Suppose that d⁰_n≤ _u^t0kk for every 2≤k≤n. Then t⁰_n+1 =

∞

X

i=1

t⁰_n+1−t

i ≥

∞

X

i=1, n+1−ti>1

d⁰_nu^n+1−ti.

So we proved _u^t0n+1n+1 ≥ d⁰_n(1−P∞

i=1, ti≥nu^−ti) = d⁰_n(1−v_n−1), with v_n defined as in Lemma 2.2. Hence, 0 < d⁰ = _u¹2

Q

n≥1(1−v_n) is such thatd⁰ ≤ _u^t0nn for every n ≥2.

Lemma 2.6. We have a_m ≤u^m−1 for every integer m >0.

Proof. Form= 1, this is true. ifm ≥2, we see by induction that a_m = 1 +

∞

X

i=1, m>ti

a_m−ti ≤1 +

∞

X

i=1, m>ti

(u^m−ti−1) Since P

i=1, m>ti1≥2 and by (1.3), a_m ≤1−

∞

X

i=1, m>ti

1 +u^m

∞

X

i=1, m>ti

u^−ti < u^m−1

Proof of the Theorem. According to Lemmas (2.4), (2.5), (2.6) and the definition of C_N, we have, for 1≤N < n and k ≥0:

t_n+k ≤C_Nu^n+k−t⁰_k+2(CNuⁿ−t_n) +a_ku^N ≤C_Nu^n+k−d⁰u^k+2(CNuⁿ−t_n) +u^N+k Let² > 0. There exists N such that C ≤C_N < C+², and n > N such that u^N−n < ² and

tn

uⁿ < D+².In these conditions, we have t_n+k

u^n+k < C +²−d⁰u²(C−D−²) +².

There exists k such that _u^tn+kn+k > C−². Then C−² < C+²−d⁰u²(C−D−²) +². Letting

² tend to 0 gives C ≤C−d⁰u²(C−D). Hence d⁰u²(C−D)≤0. This implies C ≤D and thusC =D.

3 Acknowledgments

I am grateful to M. Mischler for valuable help and many fruitful discussions during the course of this work.

References

[1] N. J. A. Sloane, Online Encyclopedia of Integer Sequences, http://www.research.att.com/˜njas/sequences/

2000 Mathematics Subject Classification: Primary 11Y55.

Keywords: integer sequences.

(Concerned with sequence A052109.)

Received May 16 2005; revised version received July 28 2005. Published inJournal of Integer Sequences, August 2 2005.

Return to Journal of Integer Sequences home page.