A Self-Indexed Sequence

Emmanuel Preissmann 11 rue Vinet 1004 Lausanne Switzerland

                emmanuel.preissmann@lth.epfl.ch

Abstract We investigate the integer sequence (t_{n})_{n∈ℤ} defined by t_{n} = 0 if n ≤ 0, t_{1} = 1,

and t_{n} = ∑_{i=1}^{n−1} t_{n−t_{i}} for n ≥ 2. This sequence has the following properties: if we
consider f_{n}(X) := −1+∑_{i=1}^{n} X^{t_{i}} and take x_{n} to be the real positive number such that
f_{n}(x_{n}) = 0, then

lim_{n→∞} \frac{t_{n}}{t_{n+1}} = lim_{n→∞} x_{n} = 0.410098516 ⋯

Moreover, if u is the real positive number such that 1 = ∑_{i=1}^{∞} u^{−t_{i}}, then there is a positive constant M such that t_{n} ∼ Mu^{n}.

1 Definitions and main results

If we look in the Online Encyclopedia of Integer Sequences of N. J. A. Sloane [1], we find a remarkable sequence by (t_{n})_{n∈ℤ} defined by t_{n} = 0 if n ≤ 0, t_{1} = 1 and

t_{n} = ∑_{i=1}^{n−1} t_{n−t_{i}}  (1.1)

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

We find t_{2} = 1, t_{3} = 2, t_{4} = 5, t_{5} = 12, t_{6} = 30, t_{7} = 73, … Observe that if n ≥ 2 , t_{n+1} = 2t_{n} + ⋯ ≥ 2t_{n}. Since t_{4} = 4 + 1, we have

t_{n} ≥ n + 1 (n ≥ 4)  (1.2)

The serie ∑_{i=1}^{∞} X^{t_{i}} = 2X +X^{2}+⋯ converges for |X| < 1. Let u be the real positive number such that

∑_{i=1}^{∞} u^{−t_{i}} = 1  (1.3)

We easily see that 2 < u < 3. Indeed we have ∑_{i=1}^{∞} (\frac{1}{2})^{t_{i}} = \frac{1}{2} + \frac{1}{2} + ⋯ > 1 and ∑_{i=1}^{∞} (\frac{1}{3})^{t_{i}} < \frac{2}{3} + \frac{1}{9} ∑_{i=0}^{∞} (\frac{1}{3})^{i} = \frac{5}{6}.

Theorem 1.1. There exists a positive constant M such that

lim_{n→∞} \frac{t_{n}}{u^{n}} = M.

Corollary 1.1. Let n ≥ 2 be an integer. Let f_{n}(X) = −1 + ∑_{i=1}^{n} X^{t_{i}} and take x_{n} the real positive number such that f_{n}(x_{n}) = 0. Then

lim_{n→∞} \frac{t_{n}}{t_{n+1}} = \frac{1}{u} = lim_{n→∞} x_{n} = 0.410098516 · · · .

Proof. By the theorem, t_{n} ∼ Mu^{n}, therefore lim_{n→∞} \frac{t_{n}}{t_{n+1}} = \frac{1}{u} .

In addition, the sequence (x_{n})_{n=1}^{∞} is strictly decreasing. Indeed,

∑_{i=1}^{n} x_{n}^{t_{i}} = 1 = ∑_{i=1}^{n+1} x_{n+1}^{t_{i}}

so that

∑_{i=1}^{n} (x_{n+1}^{t_{i}} − x_{n}^{t_{i}}) = −x_{n+1}^{t_{n+1}} < 0

This proves that x_{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 + ∑_{i=1}^{∞} x^{t_{i}} is continuous. Let ϵ > 0. We have

0 < f_{∞}(x_{n}) = ∑_{i=n+1}^{∞} x_{n}^{t_{i}} < ϵ

if n is big enough. Finally,

f_{∞}(v) = lim_{n→∞} f_{∞}(x_{n}) = 0.

That is, v = \frac{1}{u}, because \frac{1}{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

∑_{n=1}^{∞} v_{n} < ∞  (2.1)

∏_{n=1}^{∞} (1 − v_{n}) > 0.  (2.2)

Proof. Without loss of generality, we can suppose that v_{n} ≤ \frac{1}{2}. If an infinite number of v_{n} > \frac{1}{2}, the claims 2.1 and 2.2 are both wrong, otherwise we can take out the finite number of v_{n} > \frac{1}{2}. By Taylor expansion, we have for 0 ≤ x ≤ \frac{1}{2}

− log(1 − x) = x + \frac{1}{2} \frac{x^{2}}{(1 − θx)^{2}} , 0 ≤ θ ≤ 1;

hence x ≤ − log(1 − x) ≤ 2x for 0 ≤ x ≤ \frac{1}{2}. It follows that for every integer N > 0 we have

∑_{n=1}^{N} v_{n} ≤ − log ∏_{n=1}^{N} (1 − v_{n}) ≤ 2 ∑_{n=1}^{N} v_{n}.

So the lemma is proved.

Lemma 2.2. There exists a constant d such that

0 < d ≤ \frac{t_{n}}{u^{n}} for every integer n > 0.

Proof. Suppose that n ≥ 4 and d_{n} is such that 0 < d_{n} ≤ \frac{t_{k}}{u^{k}} for 1 ≤ k ≤ n. Then we have

t_{n+1} = ∑_{i=1}^{n} t_{n+1−t_{i}} ≥ ∑_{{i=1 \atop n+1−t_{i}>0}}^{n} d_{n}u^{n+1−t_{i}}.

By Eq. (1.2), n + 1 − t_{n} ≤ 0. Hence

t_{n+1} ≥ d_{n}u^{n+1} ∑_{{i=1 \atop n+1−t_{i}>0}}^{n} u^{−t_{i}} = d_{n}u^{n+1} ∑_{{i=1 \atop n+1−t_{i}>0}}^{∞} u^{−t_{i}} = d_{n}u^{n+1}(1 − v_{n})

where v_{n} = ∑_{i=1, t_{i}≥n+1}^{∞} u^{−t_{i}} by definition of u. So we have

d_{n}(1 − v_{n}) ≤ \frac{t_{k}}{u^{k}} for 1 ≤ k ≤ n + 1.  (2.3)

The series

∑_{n=4}^{∞} v_{n} = ∑_{n=4}^{∞} ∑_{{i=1 \atop t_{i}≥n+1}}^{∞} u^{−t_{i}} = ∑_{i=1}^{∞} u^{−t_{i}} ∑_{4≤n<t_{i}}^{∞} 1 = ∑_{i=4}^{∞} u^{−t_{i}}(t_{i} − 4)

is convergent; just compare this sum with \frac{1}{(X−1)^{2}} = ∑_{i=1}^{∞} iX^{i−1} for |X| < 1. Set d_{4} = min_{1≤k≤4} \frac{t_{k}}{u^{k}}. By Lemma 2.1 and (2.3), d = d_{4} ∏_{n=4}^{∞}(1−v_{n}) is such that 0 < d ≤ \frac{t_{n}}{u^{n}} for every positive integer n.

Lemma 2.3. For every integer n, one has t_{n} ≤ u^{n−1}.

Proof. If n ≤ 1, this is evident. Suppose that n ≥ 1 and by induction that t_{i} ≤ u^{i−1} when i ≤ n. Then by (1.1) and (1.3), we have

t_{n+1} = ∑_{i=1}^{n} t_{n+1−t_{i}} ≤ ∑_{i=1}^{n} u^{n−t_{i}} ≤ ∑_{i=1}^{∞} u^{n−t_{i}} = u^{n}.

Remark 2.1. Let N ≥ 1. Set C_{N} = sup_{n≥N} (\frac{t_{n}}{u^{n}} ) and D_{N} = inf_{n≥N} (\frac{t_{n}}{u^{n}} ). Lemmas 2.2 and 2.3 prove that C = lim_{N→∞} C_{N} and D = lim_{N→∞} D_{N} with 0 < D ≤ C are meaningful. Define (t′_{n})_{n∈ℤ} by t′_{i} = 0 when i ≤ 1, t′_{2} = 1 and for n ≥ 3 define

t′_{n} = ∑_{i=1}^{∞} t′_{n−t_{i}}.  (2.4)

Define also (a_{n})_{n∈ℤ} by a_{n} = 0 when n ≤ 0, a_{1} = 1 and for n ≥ 2:

a_{n} = 1 + ∑_{i=1}^{∞} a_{n−t_{i}}.  (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+2}t_{n} + u^{n+k}C_{N} (1 − \frac{t′_{k+2}}{u^{k}} ) + a_{k}u^{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} = ∑_{i=1}^{n+l−1} t_{n+l−t_{i}} ≤ ∑_{i=1}^{∞} t_{n+l−t_{i}} = Σ_{1} + Σ_{2} + Σ_{3}

where

Σ_{1} = ∑_{{i=1 \atop n+l−t_{i}≥n}}^{∞} t_{n+l−t_{i}}

Σ_{2} = ∑_{{i=1 \atop N≤n+l−t_{i}<n}}^{∞} t_{n+l−t_{i}}

Σ_{3} = ∑_{{i=1 \atop n+l−t_{i}<N}}^{∞} t_{n+l−t_{i}}.

By induction we have

Σ_{1} ≤ ∑_{{i=1 \atop l−t_{i}≥0}}^{∞} (t′_{l−t_{i}+2}t_{n} + u^{n+l−t_{i}}C_{N}(1 − \frac{t′_{l−t_{i}+2}}{u^{l−t_{i}}}) + a_{l−t_{i}}u^{N}) .

By the definition of C_{N}

Σ_{2} ≤ ∑_{{i=1 \atop N≤n+l−t_{i}<n}}^{∞} C_{N}u^{n+l−t_{i}}.

By Lemma 2.3 and the fact that u > 2,

Σ_{3} ≤ ∑_{i=1}^{N} t_{i} ≤ ∑_{i=0}^{N−1} u^{i} = \frac{u^{N} − 1}{u − 1} < u^{N}.

Finally

t_{n+l} ≤ t_{n} ∑_{{i≥1 \atop l−t_{i}≥0}} t′_{l−t_{i}+2} + C_{N} ∑_{{i≥1 \atop n+l−t_{i}≥N}} u^{n+l−t_{i}} − C_{N} ∑_{{i≥1 \atop l−t_{i}≥0}} u^{n}t′_{l−t_{i}+2} + ∑_{{i≥1 \atop l−t_{i}≥0}} a_{l−t_{i}}u^{N} + u^{N}.

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

t_{n+l} ≤ t′_{l+2}t_{n} + u^{n+l}C_{N}(1 − \frac{t′_{l+2}}{u^{l}}) + a_{l}u^{N}.

Lemma 2.5. There exists d′ > 0 such that d′ ≤ \frac{t′_{n}}{u^{n}} for every n ≥ 2. Proof. Suppose that d′_{n} ≤ \frac{t′_{k}}{u^{k}} for every 2 ≤ k ≤ n. Then

t′_{n+1} = ∑_{i=1}^{∞} t′_{n+1−t_{i}} ≥ ∑_{i=1, n+1−t_{i}>1}^{∞} d′_{n}u^{n+1−t_{i}}.

So we proved \frac{t′_{n+1}}{u^{n+1}} ≥ d′_{n}(1 − ∑_{i=1, t_{i}≥n}^{∞} u^{−t_{i}}) = d′_{n}(1 − v_{n−1}), with v_{n} defined as in Lemma 2.2. Hence, 0 < d′ = \frac{1}{u^{2}} ∏_{n≥1}(1 − v_{n}) is such that d′ ≤ \frac{t′_{n}}{u^{n}} for every n ≥ 2. Lemma 2.6. We have a_{m} ≤ u^{m} − 1 for every integer m > 0. Proof. For m = 1, this is true. if m ≥ 2, we see by induction that

a_{m} = 1 + ∑_{i=1, m>t_{i}}^{∞} a_{m−t_{i}} ≤ 1 + ∑_{i=1, m>t_{i}}^{∞}(u^{m−t_{i}} − 1)

Since ∑_{i=1, m>t_{i}} 1 ≥ 2 and by (1.3),

a_{m} ≤ 1 − ∑_{i=1, m>t_{i}}^{∞} 1 + u^{m} ∑_{i=1, m>t_{i}}^{∞} u^{−t_{i}} < 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_{N}u^{n+k} − t′_{k+2}(C_{N}u^{n} − t_{n}) + a_{k}u^{N} ≤ C_{N}u^{n+k} − d′u^{k+2}(C_{N}u^{n} − 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 \frac{t_{n}}{u^{n}} < D + ϵ. In these conditions, we have

\frac{t_{n+k}}{u^{n+k}} < C + ϵ − d′u^{2}(C − D − ϵ) + ϵ.

There exists k such that \frac{t_{n+k}}{u^{n+k}} > C − ϵ. Then C − ϵ < C + ϵ − d′u^{2}(C − D − ϵ) + ϵ. Letting ϵ tend to 0 gives C ≤ C − d′u^{2}(C − D). Hence d′u^{2}(C − D) ≤ 0. This implies C ≤ D and thus C = 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 \underline{A052109}.)

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

Return to Journal of Integer Sequences home page.