MATEMATIQKI VESNIK 48 (1996), 99–105

UDK 517.15

originalni nauqni rad research paper

ASYMPTOTIC BEHAVIOUR OF A SEQUENCE DEFINED BY ITERATION

Stevo Stević

Abstract. One considers some results in [1] and [2] concerning asymptotic behaviour of recurrently defined sequences and one gives more general and more precise form to them, especially by obtaining new terms in asymptotic expansion.

Introduction. In this paper we consider asymptotic behaviour of sequences (x_{n})_{n∈N} given by the recurrent formula x_{n} = f(x_{n−1}). We extend the following result (see problem I174 [1]).

Theorem P. Let f : (0, α) → (0, α), where α > 0, be a continuous function such that 0 < f(x) < x for every x ∈ (0, α) and f(x) = x − ax^{k} + bx^{k+p} + o(x^{k+p}), when x → +0, where k > 1, p, a and b are positive numbers. Let x_{0} ∈ (0, α) and

x_{n} = f(x_{n−1}), n ⩾ 1. Then x_{n} ∼ ((k − 1)an)−\frac{1}{(k−1)} .

In the special case of the sequence given by x_{n} = x_{n−1} − x_{n−1}^{2}, 0 < x_{0} < 1 it was proved in [2] that x_{n} ∼ \frac{1}{n} − \frac{ln n}{n^{2}}. Thus the second term in asymptotic development of this sequence is determined.

Now it is natural to ask if we can determine the second term in asymptotic development of the sequence given in Theorem P.

Let us first prove Theorem P. Our version of this proof is somewhat different from its original form, and the idea and structure of this version was starting point and inspiration for our further consideration.

Proof. Since 0 < f(x) < x for every x ∈ (0, α), the sequence x_{n} is decreasing so that there exists lim_{n→+∞} x_{n}. It can be proved by standard procedure that lim_{n→+∞} x_{n} = 0. We have

x_{n} = f(x_{n−1}) = x_{n−1} − ax_{n−1}^{k} + bx_{n−1}^{k+p} + o(x_{n−1}^{k+p}).

AMS Subject Classification: 40A05

Keywords and phrases: Asymptotic behaviour of sequences

Supported by Ministry of Science and technology RS, grant number 04M01

Since x_{n} > 0, we can write

\frac{1}{x_{n}^{k−1}} = \frac{1}{f(x_{n−1})^{k−1}} = \frac{(1 − ax_{n−1}^{k−1} + bx_{n−1}^{k−1+p} + o(x_{n−1}^{k−1+p}))^{−(k−1)}}{x_{n−1}^{k−1}} .

Since x_{n} → 0 when n → +∞, it follows that −ax_{n−1}^{k−1} + bx_{n−1}^{k−1+p} + o(x_{n−1}^{k−1+p}) → 0 when n → +∞. Using the asymptotic formula (1 + x)^{α} = 1 + \binom{α}{1}x + \binom{α}{2}x^{2} + o(x^{2}), x → 0, we get

\frac{1}{x_{n}^{k−1}} = \frac{1}{x_{n−1}^{k−1}} + (k − 1)a − b(k − 1)x_{n−1}^{p} + a^{2}\binom{k}{2}x_{n−1}^{k−1} + o(x_{n−1}^{p}) + o(x_{n−1}^{k−1}). (1)

Hence,

\frac{1}{x_{n}^{k−1}} = \frac{1}{x_{n−1}^{k−1}} + (k − 1)a + O(x_{n−1}^{s})  (2)

for n ⩾ n_{0}, natural number n_{0} being fixed and s = min(p, k − 1).

It follows from (2) that

\frac{1}{x_{n}^{k−1}} = \frac{1}{x_{n_{0}}^{k−1}} + (k − 1)a(n − n_{0}) + O(x_{n_{0}}^{s}) + ⋯ + O(x_{n−1}^{s})  (3)

and hence

\frac{1}{nx_{n}^{k−1}} = \frac{1}{nx_{n_{0}}^{k−1}} + (k − 1)a (1 − \frac{n_{0}}{n} ) + \frac{O(x_{n_{0}}^{s}) + ⋯ + O(x_{n−1}^{s})}{n}.  (4)

By Stoltz theorem, we obtain lim_{n→+∞} \frac{1}{n}[O(x_{n_{0}}^{s}) + ⋯ + O(x_{n−1}^{s})] = 0.

Now it follows from (4) that lim_{n→+∞} 1/(nx_{n−1}^{k−1}) = (k − 1)a.

Finally, we obtain x_{n} ∼ ((k − 1)an)^{− \frac{1}{k−1}} .

Remark. An inspection of the proof shows that the condition b > 0 is not essential.

In order to improve our estimate we are going to consider the following cases. Case 1. Let p > k − 1. Then it follows from (1) that

\frac{1}{x_{n}^{k−1}} = \frac{1}{x_{n−1}^{k−1}} + a(k − 1) + a^{2} \frac{k(k − 1)}{2}x_{n−1}^{k−1} + o(x_{n−1}^{k−1}).  (5)

Using the substitution b_{n} = x_{n}^{k−1}, we can write (5) in the form of

\frac{1}{b_{n}} = \frac{1}{b_{n−1}} + a(k − 1) + a^{2}\binom{k}{2}b_{n−1} + o(b_{n−1}).  (6)

By (6), we obtain

\frac{1}{b_{n}} = \frac{1}{b_{n_{0}}} + a(k − 1)(n − n_{0}) + a^{2}\binom{k}{2}( ∑_{i=n_{0}}^{n−1} b_{i}) + o(b_{n_{0}}) + ⋯ + o(b_{n−1}) (7)

for n ⩾ n_{0}.

From Theorem P it follows that b_{n} = \frac{1}{(k−1)an} + o(\frac{1}{n}), and so
\frac{1}{b_{n}} = \frac{1}{b_{n_{0}}} + a(k − 1)(n − n_{0})

+ a^{2}\binom{k}{2} ∑_{i=n_{0}}^{n−1} (\frac{1}{(k − 1)ai} + o (\frac{1}{i})) + o(b_{n_{0}}) + ⋯ + o(b_{n−1}).

By Euler’s formula, 1 + \frac{1}{2} + ⋯ + \frac{1}{n} − ln n = γ_{n} → γ ∈ ℝ (n → +∞) and since o(b_{i}) = o(\frac{1}{i}) we have

\frac{1}{b_{n}} = \frac{1}{b_{n_{0}}} + a(k − 1)(n − n_{0})

+ a^{2}\binom{k}{2}(\frac{1}{(k − 1)a} (ln (\frac{n − 1}{n_{0} − 1}) + γ_{n−1} − γ_{n_{0}−1}) + ∑_{i=n_{0}}^{n−1} o (\frac{1}{i})).

Hence

\frac{1}{b_{n}} = c(n_{0}) + a(k − 1)n + a^{2}\binom{k}{2}(\frac{1}{(k − 1)a} (ln n + γ_{n−1} − \frac{1}{n}) + ∑_{i=n_{0}}^{n} o (\frac{1}{i})),

where c(n_{0}) is a constant depending of n_{0}.

Since lim_{n→+∞} ∑_{i=n_{0}}^{n−1} o(\frac{1}{i})/ ln n = 0, it follows that \frac{1}{b_{n}} = a(k −1)n+ \frac{ak}{2} ln n+ o(ln n). Hence

x_{n} = b\frac{1}{k−1} ; n = (a(k − 1)n + \frac{ak}{2} ln n + o(ln n))−\frac{1}{k−1}

= \frac{1}{(a(k − 1)n)^{\frac{1}{k−1}}} − \frac{k}{2(k − 1)^{\frac{2k−1}{k−1}} a^{\frac{1}{k−1}}} \frac{ln n}{n^{\frac{k}{k−1}}} + o (\frac{ln n}{n^{\frac{k}{k−1}}} ) .

Case 2. Let p = k − 1. Now instead of (6), we have

\frac{1}{b_{n}} = \frac{1}{b_{n−1}} + (k − 1)a + b_{n−1} (\binom{k}{2}a^{2} − (k − 1)b) + o(b_{n−1}),

and so the final asymptotic formula of the preceeding case in this case becomes

x_{n} = \frac{1}{(n(k − 1)a)^{\frac{1}{k−1}}} − \frac{ka^{2} − 2b}{2(a(k − 1))^{2}} \frac{ln n}{((k − 1)a)^{\frac{1}{k−1}} n^{\frac{k}{k−1}}} + o (\frac{ln n}{n^{\frac{k}{k−1}}} ) .

Case 3. Let p < k − 1. In the same way as in the cases 1 and 2, we obtain:

\frac{1}{b_{n}} = \frac{1}{b_{n−1}} + (k − 1)a − b(k − 1) b\frac{p}{k−1} ; n−1 + o(b\frac{p}{k−1} ; n−1 )
\frac{1}{b_{n}} = \frac{1}{b_{n_{2}}} + (k − 1)a(n − n_{2}) − b(k − 1) ∑_{i=n_{2}}^{n−1} b\frac{p}{k−1} ; i + ∑_{i=n_{2}}^{n−1} o(b\frac{p}{k−1} ; i).

Hence

\frac{1}{b_{n}} = \frac{1}{b_{n_{2}}} + (n − n_{2})(k − 1)a − b(k − 1) ∑_{i=n_{2}}^{n−1} \frac{1}{(a(k − 1)i)^{\frac{p}{k−1}}} + ∑_{i=n_{2}}^{n−1} o (\frac{1}{i^{\frac{p}{k−1}}} )
= c(n_{2}) + n(k − 1)a − \frac{b(k − 1)}{(a(k − 1))^{\frac{p}{k−1}}} ∑_{i=n_{2}}^{n−1} \frac{1}{i^{\frac{p}{k−1}}} + ∑_{i=n_{2}}^{n−1} o (\frac{1}{i^{\frac{p}{k−1}}} ) .  (8)

We will use the known asymptotic formula

∑_{i=1}^{n−1} \frac{1}{i^{s}} ∼ \frac{n^{1−s}}{1 − s}.  (9)

Combining (8) and (9) with s = p/(k − 1), we get

\frac{1}{b_{n}} = n(k − 1)a − \frac{(k − 1)^{2}b}{(a(k − 1))^{\frac{p}{k−1}}} \frac{1}{(k − 1 − p)}n^{\frac{k−1−p}{k−1}} + o(n^{\frac{k−1−p}{k−1}} ).

Hence

x_{n} =

= (n(k − 1)a)−\frac{1}{k−1} (1 − \frac{(k − 1)b}{a(k − 1 − p)(a(k − 1))^{\frac{p}{k−1}}} \frac{1}{n^{\frac{p}{k−1}}} + o (\frac{1}{n^{\frac{p}{k−1}}} ))−\frac{1}{(k−1)}

= \frac{1}{(n(k − 1)a)^{\frac{1}{k−1}}} + \frac{b}{a(k − 1 − p)(a(k − 1))^{\frac{p+1}{k−1}}} \frac{1}{n^{\frac{p+1}{k−1}}} + o (\frac{1}{n^{\frac{p+1}{k−1}}} ) .

Remark. If b = 0 then we need not investigate the relation between p and k − 1, because it is easy to verify that this case was considered in Case 1.

We state the results obtained in the cases 1, 2 and 3 in the following theorem.

Theorem 1. Under the same condition as in Theorem P we can conclude a) If p > k − 1 then

x_{n} = \frac{1}{(a(k − 1)n)^{\frac{1}{k−1}}} − \frac{k}{2(k − 1)^{\frac{2k−1}{k−1}} a^{\frac{1}{k−1}}} \frac{ln n}{n^{\frac{k}{k−1}}} + o (\frac{ln n}{n^{\frac{k}{k−1}}} ) .

b) If p = k − 1 then

x_{n} = \frac{1}{(a(k − 1)n)^{\frac{1}{k−1}}} − \frac{ka^{2} − 2b}{2(a(k − 1))^{2}} \frac{ln n}{((k − 1)a)^{\frac{1}{k−1}} n^{\frac{k}{k−1}}} + o (\frac{ln n}{n^{\frac{k}{k−1}}} ) .

c) If p < k − 1 and b ≠ 0 then

x_{n} = \frac{1}{(a(k − 1)n)^{\frac{1}{k−1}}} + \frac{b}{a(k − 1 − p)(a(k − 1))^{\frac{p+1}{k−1}}} \frac{1}{n^{\frac{p+1}{k−1}}} + o (\frac{1}{n^{\frac{p+1}{k−1}}} ) .

Example 1. Let f(x) = sin x and α = π. Since sin x = x − \frac{x^{3}}{3!} + \frac{x^{5}}{5!} + o(x^{5}) we see that a = 1/6, b = 1/120, k = 3, p = 2. Since k − 1 = p, by the Case 2. we obtain

x_{n} = \begin{matrix}√ & \overline{3} \\ √ & \overline{n} \end{matrix} − 3\frac{\sqrt{3}}{10} \frac{ln n}{n^{3/2}} + o (\frac{ln n}{n^{3/2}} ) .

Example 2. Let f(x) = ln(1 + x), and α = +∞. Since ln(1 + x) = x − \frac{x^{2}}{2} + \frac{x^{3}}{3} + o(x^{3}) we see that a = 1/2, b = 1/3, k = 2, p = 1. Again we have as in the Example 1 k − 1 = p, and by the Case 2.

x_{n} = \frac{2}{n} + \frac{2}{3} \frac{ln n}{n^{2}} + o (\frac{ln n}{n^{2}}) .

Example 3. Let f(x) = x − x^{2}, and α = 1. Then a = 1, b = 0, k = 2. Since b = 0 we obtain

x_{n} = \frac{1}{n} − \frac{ln n}{n^{2}} + o (\frac{ln n}{n^{2}}) .

Clearly, we can try to determine other terms in asymptotic development of our sequence. The following theorem gives us a formula which contains three terms in asymptotic developments of the sequence x_{n} in Case 1:

Theorem 2. Let p > k − 1 and let all others conditions of Theorem P be satisfied. Then

x_{n} = \frac{1}{(a(k − 1)n)^{\frac{1}{k−1}}} − \frac{k}{2a^{\frac{1}{k−1}} (k − 1)^{\frac{2k−1}{k−1}}} \frac{ln n}{n^{\frac{k}{k−1}}} + \frac{d}{n^{\frac{k}{k−1}}} + o (\frac{1}{n^{\frac{k}{k−1}}} )

where d is a constant depending on x_{0}.

Proof. We can repeat the procedure from Theorem 1. By Case 1 we have

\frac{1}{b_{n}} = a(k − 1)n + \frac{ak}{2} ln n + o(ln n).

Hence

b_{n} = \frac{1}{a(k − 1)n} − \frac{k}{2a(k − 1)^{2}} \frac{ln n}{n^{2}} + o (\frac{ln n}{n^{2}}) .  (10)

Using standard substitution b_{n} = x_{n}^{k−1} in (1) we get

\frac{1}{b_{n}} = \frac{1}{b_{n−1}} + a(k − 1) + a^{2}\binom{k}{2}b_{n−1} + O(b_{n−1}^{l/(k−1)}), \frac{l}{k − 1} = \frac{min(p, 2(k − 1))}{k − 1} > 1.

By (10), we obtain

\frac{1}{b_{n}} = c + a(k − 1)n

+ a^{2}\binom{k}{2} ∑_{i=n_{0}}^{n−1} (\frac{1}{a(k − 1)i} − \frac{k}{2a(k − 1)^{2}} \frac{ln i}{i^{2}} + o (\frac{ln i}{i^{2}})) + ∑_{i=n_{0}}^{n−1} O (\frac{1}{i^{\frac{l}{k−1}}} )

where c is a constant depending on x_{0} and n_{0}, hence

\frac{1}{b_{n}} = a(k − 1)n + \frac{ak}{2} ln n + c_{n}.

The sequence c_{n} has a finite limit since the following two series are convergent

∑_{i=n_{0}}^{+∞} \frac{ln i}{i^{2}},  ∑_{i=n_{0}}^{+∞} O (\frac{1}{i^{\frac{l}{k−1}}} ).

If we put c_{n} = c(x_{0}) + d_{n}, where c(x_{0}) = lim_{n→+∞} c_{n} we have

b_{n} = \frac{1}{a(k − 1)n} − \frac{k}{2a(k − 1)^{2}} \frac{ln n}{n^{2}} − \frac{c(x_{0})}{a(k − 1)n^{2}} + o (\frac{1}{n^{2}} ) .  (12)

Finally, by (12), we obtain

x_{n} = b\frac{1}{k−1} ; n = \frac{1}{(a(k − 1)n)^{\frac{1}{k−1}}} − \frac{k}{2a^{\frac{1}{k−1}} (k − 1)^{\frac{2k−1}{k−1}}} \frac{ln n}{n^{\frac{k}{k−1}}} + \frac{d(x_{0})}{n^{\frac{k}{k−1}}} + o (\frac{1}{n^{\frac{k}{k−1}}} )

where d(x_{0}) = −c(x_{0})/a^{\frac{1}{k−1}} (k − 1)^{\frac{k}{k−1}} .

Of course, we can obtain in the same manner an analogous formula for other two cases. This task we leave to the reader.

We finish this paper by determination of first five terms in the asymptotic development of the sequence given by x_{n} = x_{n−1} − x_{n−1}^{2} , 0 < x_{0} < 1. This sequence satisfies the following relation

\frac{1}{x_{n}} = \frac{1}{x_{n−1}} + 1 + x_{n−1} + x_{n−1}^{2} + o(x_{n−1}^{2}).  (13)

Using Theorem 2 we get

1/x_{n} = n + ln n + c(x_{0}) + d_{n},  (14)

where lim_{n→+∞} d_{n} = 0.

By (13) and (14), we have

d_{n} = d_{n−1} − \frac{ln n}{n^{2}} + o (\frac{ln n}{n^{2}}) ,

hence

d_{n} = ∑_{k=n}^{+∞}(d_{k} − d_{k+1}) = ∑_{k=n}^{+∞} (\frac{ln k}{k^{2}} + o (\frac{ln k}{k^{2}} )) ∼ ∑_{k=n}^{+∞} \frac{ln k}{k^{2}} ∼ \frac{ln n}{n}

and

1/x_{n} = n + ln n + c(x_{0}) + \frac{ln n}{n^{2}} + o (\frac{ln n}{n^{2}}) .

The last equality gives us the desired asymptotic development, i.e.

x_{n} = \frac{1}{n} − \frac{ln n}{n^{2}} − \frac{c(x_{0})}{n^{2}} + \frac{ln^{2}n}{n^{3}} + (2c(x_{0}) − 1)\frac{ln n}{n^{3}} + o (\frac{ln n^{2}}{n^{3}} ) .

Of course, if we had a better asymptotic evaluation of f(x), we could obtain better asymptotic formula for x_{n}.

REFERENCES

[1] G. Polya und G. Szegö, Aufgaben und Lehrsätze aus der Analysis, Verlag von Julius Springer, Berlin 1925

[2] D. Cox, Problem E 3034, Amer. Math. Monthly 91 (1984), 58

(received 27.09.1996.)

Faculty of Mathematics, Studentski trg 16, 11000 Beograd, Yugoslavia