Integer Sequences, Functions of Slow Increase, and the Bell Numbers

Rafael Jakimczuk División Matemática Universidad Nacional de Luján Buenos Aires Argentina

             jakimczu@mail.unlu.edu.ar

In memory of my sister Fedra Marina Jakimczuk (1970–2010)

Abstract

In this article we first prove a general theorem on integer sequences A_{n} such that the following asymptotic formula holds,

\frac{A_{n}}{A_{n−1}} ∼ Cn^{α}f(n)^{β},

where f(x) is a function of slow increase, C > 0, α > 0 and β is a real number.

We also obtain some results on the Bell numbers B_{n} using well-known formulae. We compare the Bell numbers with a^{n} (a > 0) and (n!)^{h} (0 < h ≤ 1).

Finally, applying the general statements proved in the article we obtain the formula

B_{n+1} ∼ e (B_{n})^{1+ \frac{1}{n}} .

1 Integer Sequences. A General Theorem.

We shall need the following well-known lemmas [12, pp. 332, 294]. Lemma 1. If s_{n} is a sequence of positive numbers with limit s then the sequence

\sqrt[n]{s_{1}s_{2} ⋯ s_{n}}

has also limit s.

Lemma 2. The following limit holds,

lim_{n→∞} \frac{\sqrt[n]{n!}}{n} = \frac{1}{e}.

We recall the definition of function of slow increase [7, Definition 1 ].

Definition 3. Let f(x) be a function defined on interval [a, ∞) such that f(x) > 0, lim_{x→∞} f(x) = ∞ and with continuous derivative f′(x) > 0 . The function f(x) is of slow increase if and only if the following condition holds

lim_{x→∞} \frac{f′(x)}{\frac{f(x)}{x}} = lim_{x→∞} \frac{xf′(x)}{f(x)} = 0.  (1)

Typical functions of slow increase are f(x) = log x, f(x) = log^{2} x and f(x) = log log x.

Lemma 4. If f(x) is a function of slow increase on the interval [b, ∞) then the following asymptotic formula holds

\sqrt[n]{f(b)f(b + 1) ⋯ f(n)} ∼ f(n),  (2)

where b is a positive integer.

Proof. Note that we always can suppose that f(x) > 1 on the interval [b, ∞).

Since log f(x) is increasing and positive in the interval [b, ∞) we find that

∑_{i=b}^{n} log f(i) = ∑_{i=b}^{n}(1 · log f(i)) = ∫_{b}^{n} log f(x) dx + O(log f(n)) = n log f(n)

+ ∫_{b}^{n} \frac{xf′(x)}{f(x)} dx + O(log f(n)).  (3)

Note that the second equation in (3) is a sum of areas of rectangles of height log f(i) and base 1. Consequently the third equation in (3) is immediate.

L’Hôpital’s rule gives (see (1))

lim_{x→∞} \frac{log f(x)}{x} = lim_{x→∞} \frac{f′(x)}{f(x)} = 0.

Therefore

O(log f(n)) = o(n).  (4)

If the integral ∫_{b}^{x} \frac{tf′(t)}{f(t)} dt converges we obtain

lim_{x→∞} \frac{∫_{b}^{x} \frac{tf′(t)}{f(t)} dt}{x} = 0.

On the other hand, if the integral ∫_{b}^{x} \frac{tf′(t)}{f(t)} dt diverges we obtain from L’Hôpital’s rule and (1) that

lim_{x→∞} \frac{∫_{b}^{x} \frac{tf′(t)}{f(t)} dt}{x} = 0.

Therefore

∫_{b}^{n} \frac{xf′(x)}{f(x)} dx = o(n).  (5)

Equations (3), (4) and (5) give

∑_{i=b}^{n} log f(i) = n log f(n) + o(n).  (6)

That is,

\frac{1}{n} ∑_{i=b}^{n} log f(i) = log f(n) + o(1).

That is (2).

Theorem 5. Let A_{n} (n ≥ 0) be a sequence of positive numbers (in particular integers) such that

\frac{A_{n}}{A_{n−1}} ∼ Cn^{α}f(n)^{β},  (7)

where f(x) is a function of slow increase on the interval [b, ∞), C > 0, α > 0 and β is a real number. If 1 ≤ n < b we put f(n) = 1.

The following formulae hold,

\frac{\sqrt[n]{\frac{A_{1}}{A_{0}} \frac{A_{2}}{A_{1}} ⋯ \frac{A_{n}}{A_{n−1}}}}{\frac{A_{n}}{A_{n−1}}} → \frac{1}{e^{α}} ,  (8)

A_{n+1} ∼ e^{α}A_{n}^{1+ \frac{1}{n}} ,  (9)
log A_{n} = αn log n + βn log f(n) + (−α + log C)n + o(n),  (10)
log A_{n} ∼ αn log n,  (11)

A_{n} = \frac{(Cn^{α}f(n)^{β})^{n}}{e^{(α+o(1))n}} .  (12)

Proof. We have (see (7))

\frac{\frac{A_{n}}{A_{n−1}}}{Cn^{α}f(n)^{β}} → 1.  (13)

Consequently (13) and Lemma 1 give

\sqrt[n]{∏_{k=1}^{n} \frac{\frac{A_{k}}{A_{k−1}}}{Ck^{α}f(k)^{β}}} = \sqrt[n]{∏_{k=1}^{n} Ck^{α}f(k)^{β}}^{\sqrt[n]{∏{n \atop k=1} \frac{A_{k}}{A_{k−1}}}} → 1.

That is

\sqrt[n]{A_{n}} ∼ \sqrt[n]{\frac{A_{1}}{A_{0}} \frac{A_{2}}{A_{1}} ⋯ \frac{A_{n}}{A_{n−1}}} ∼ \sqrt[n]{∏_{k=1}^{n} Ck^{α}f(k)^{β}}.  (14)

Lemma 2 and Lemma 4 give

\sqrt[n]{∏_{k=1}^{n} Ck^{α}f(k)^{β}} = C (\sqrt[n]{n!})^{α} (\sqrt[n]{f(1)f(2) ⋯ f(n)})^{β} ∼ C \frac{n^{α}}{e^{α}} f(n)^{β}.  (15)

Equations (14), (15) and (7) give

\sqrt[n]{A_{n}} ∼ \sqrt[n]{\frac{A_{1}}{A_{0}} \frac{A_{2}}{A_{1}} ⋯ \frac{A_{n}}{A_{n−1}}} ∼ C \frac{n^{α}}{e^{α}} f(n)^{β} ∼ \frac{1}{e^{α}} \frac{A_{n}}{A_{n−1}} .  (16)

Equation (16) gives (8). Equation (16) and [7, Theorem 8] give

An^{\frac{1}{n}} ∼ An−1^{\frac{1}{n−1}}.  (17)

Equations (17) and (16) give

A_{n} ∼ e^{α}A_{n−1}^{1+ \frac{1}{n−1}} .

That is (9). Equation (16) gives

\frac{1}{n} log A_{n} = log (C \frac{n^{α}}{e^{α}} f(n)^{β}) + o(1).

That is (10). Equation (10) gives (11), since (from L’Hôpital’s rule and (1))

lim_{x→∞} \frac{log f(x)}{log x} = lim_{x→∞} \frac{xf′(x)}{f(x)} = 0.

Finally, equation (12) is an immediate consequence of equation (10).

Remark 6. Note that: (i) The following limit holds Cn^{α}f(n)^{β} → ∞ (see(7)).

If β ≥ 0 the proof is trivial. If β < 0 use [7, Theorem 2 and Theorem 4]. Consequently we have

lim_{n→∞} \frac{A_{n+1}}{A_{n}} = ∞.

(ii) This last limit implies the following formula (A_{n+1} − A_{n}) ∼ A_{n+1}. (iii) Equation (7) implies the more general relation,

\frac{A_{n}}{A_{n−m}} = \frac{A_{n}}{A_{n−1}} \frac{A_{n−1}}{A_{n−2}} ⋯ \frac{A_{n−m+1}}{A_{n−m}} ∼ C^{m} ∏_{k=n−m+1}^{n} k^{α}f(k)^{β}.

2 Introduction to Bell Numbers.

The n-th Bell number B_{n} is the number of partitions of a set of n elements in disjoint subsets. The Bell numbers satisfy the following recurrence relation [1, p. 216].

B_{0} = 1,

B_{n+1} = ∑_{k=0}^{n} \binom{n}{k}B_{k}.  (18)

The first Bell numbers are B_{0} = 1, B_{1} = 1, B_{2} = 2, B_{3} = 5, B_{4} = 15, B_{5} = 52, B_{6} = 203, B_{7} = 877, B_{8} = 4140, B_{9} = 21147, B_{10} = 115975.

N. G. de Bruijn [6, pp. 102–109] proved the following asymptotic formula,

log B_{n} = n log n − n log log n − n + o(n).  (19)

L. Lovász [10, Ex. 9(b), p. 17] proved the following asymptotic formula

B_{n} ∼ n^{− \frac{1}{2}} (λ(n))^{n+ \frac{1}{2}} e^{λ(n)−n−1},  (20)

where

λ(n) = \frac{n}{W (n)}.  (21)

The function x = W (y) is the inverse function of y = xe^{x} on the interval (0, ∞). The function x = W (y) is called Lambert W-function.

The following results are well-known [5]. We establish these results in the next lemma. For sake of completeness we give a proof of the lemma.

Lemma 7. The function x = W (y) is positive, strictly increasing on the interval (0, ∞) and lim_{y→∞} W (y) = ∞.

The following formulae hold.

W (y) ∼ log y,  (22)

W′(y) = \frac{W (y)}{y(1 + W (y))}.  (23)

Proof. The first statement is trivial.

We have (definition of x = W (y))

y = W (y)e^{W (y)}.  (24)

Consequently

1 = W′(y)e^{W (y)} + W (y)e^{W (y)}W′(y).

That is

W′(y) = \frac{1}{e^{W (y)}(1 + W (y))} = \frac{W (y)}{y(1 + W (y))}.

On the other hand (24) gives

log y = log W (y) + W (y).

Therefore

\frac{W (y)}{log y} = 1 − \frac{log W (y)}{log y}.  (25)

Also (from L’Hôpital’s rule and (23))

lim_{y→∞} \frac{log W (y)}{log y} = lim_{y→∞} \frac{yW′(y)}{W (y)} = lim_{y→∞} \frac{1}{1 + W (y)} = 0.  (26)

Finally, equations (25) and (26) give (22). Remark 8. Note that the Lambert W-function W (y) is a function of slow increase since (see (1) and (23))

lim_{y→∞} \frac{yW′(y)}{W (y)} = lim_{y→∞} \frac{1}{1 + W (y)} = 0.

3 Some Results on Bell Numbers.

The limit

lim_{n→∞} \frac{B_{n}}{n!} = 0.

is well-known [9, p. 64]. In the following Theorem we include it for sake of completeness. Theorem 9. The following limits hold.

lim_{n→∞} \frac{B_{n}}{a^{n}} = ∞  (a > 0),  (27)
lim_{n→∞} \frac{B_{n}}{(n!)^{h}} = ∞  (0 < h < 1),  (28)

lim_{n→∞} \frac{B_{n}}{n!} = 0.

Proof. Equation (19) gives

log (\frac{B_{n}}{a^{n}} ) = log B_{n} − n log a = n log n − n log a + o(n log n).

Therefore

lim_{n→∞} log (\frac{B_{n}}{a^{n}} ) = ∞,

and consequently

lim_{n→∞} \frac{B_{n}}{a^{n}} = ∞.

That is (27).

The well-known Stirling formula is

n! ∼ \sqrt{2π} \frac{n^{n}\sqrt{n}}{e^{n}}.

Therefore

log n! = n log n − n + \frac{1}{2} log n + log \sqrt{2π} + o(1) = n log n − n + o(n),

and

log(n!)^{h} = hn log n − hn + o(n).

Consequently (see (19))

log (\frac{B_{n}}{(n!)^{h}} ) = (1 − h)n log n − n log log n − n + hn + o(n).  (29)

If 0 < h < 1 equation (29) gives

lim_{n→∞} log (\frac{B_{n}}{(n!)^{h}} ) = ∞.

That is,

lim_{n→∞} \frac{B_{n}}{(n!)^{h}} = ∞.

On the other hand if h = 1 equation (29) gives

lim_{n→∞} log (\frac{B_{n}}{n!} ) = −∞.

That is,

lim_{n→∞} \frac{B_{n}}{n!} = 0.

M. Klazar [8, Proposition 2.6] and D. E. Knuth [9, eq. (30), p. 69] proved the following asymptotic formula

\frac{B_{n+1}}{B_{n}} ∼ \frac{n}{log n}.

This formula is derived as a consequence of the asymptotic formula obtained in the classical paper [11].

In the following Theorem we derive this formula from the Lovász’s formula (20). We also use the well-known properties of the Lambert W-function established in Lemma 7.

Theorem 10. The following asymptotic formula holds,

\frac{B_{n+1}}{B_{n}} ∼ \frac{n}{log n}.  (30)

Proof. Substituting (21) into (20) we obtain

B_{n} ∼ \frac{n^{n}}{W (n)^{n+ \frac{1}{2}}} e^{\frac{n}{W (n)} −n−1}.

Consequently

\frac{B_{n+1}}{B_{n}} ∼ \frac{n + 1}{W (n + 1)}\sqrt{\frac{W (n)}{W (n + 1)}} (\frac{W (n)}{W (n + 1)})^{n} e^{(\frac{n+1}{W (n+1)} − \frac{n}{W (n)})}.  (31)

Equation (22) gives

W (n + 1) ∼ W (n).  (32)

Equations (32) and (22) give

\frac{n + 1}{W (n + 1)} ∼ \frac{n}{log n}.  (33)

Equation (32) gives

\sqrt{\frac{W (n)}{W (n + 1)}} → 1.  (34)

Let us consider the function \frac{y}{W (y)}. The derivative of \frac{y}{W (y)} is (see (23))

\frac{W (y) − yW′(y)}{W (y)^{2}} = \frac{W (y) − \frac{W (y)}{1+W (y)}}{W (y)^{2}} = \frac{1}{1 + W (y)}.

Consequently we have (Lagrange’s Theorem)

\frac{n + 1}{W (n + 1)} − \frac{n}{W (n)} = \frac{1}{1 + W (n + ϵ(n))} → 0,  (35)

where 0 < ϵ(n) < 1.

We have

(\frac{W (n + 1)}{W (n)})^{n} = exp (n (log W (n + 1) − log W (n))) .  (36)

Let us consider the function log W (y). The derivative of log W (y) is (see (23))

\frac{W′(y)}{W (y)} = \frac{1}{y(1 + W (y))}.

Consequently we have (Lagrange’s Theorem)

n (log W (n + 1) − log W (n)) = n\frac{1}{(n + ϵ(n))(1 + W (n + ϵ(n)))}

= \frac{1}{(1 + \frac{ϵ(n)}{n})(1 + W (n + ϵ(n)))} → 0,  (37)

where 0 < ϵ(n) < 1.

Equations (36) and (37) give

(\frac{W (n)}{W (n + 1)})^{n} → 1.  (38)

Finally, equations (31), (33), (34), (35) and (38) give (30).

The asymptotic formula (30) implies that the Bell numbers satisfy condition (7). In this case C = 1, α = 1, β = −1 and f(n) = log n. Consequently we have the following Corollary.

Corollary 11. The following formulae hold,

lim_{n→∞} \frac{B_{n+1}}{B_{n}} = ∞,

(B_{n+1} − B_{n}) ∼ B_{n+1},

\frac{\sqrt[n]{\frac{B_{1}}{B_{0}} \frac{B_{2}}{B_{1}} \frac{B_{3}}{B_{2}} ⋯ \frac{B_{n}}{B_{n−1}}}}{\frac{B_{n}}{B_{n−1}}} = \frac{\sqrt[n]{B_{n}}}{\frac{B_{n}}{B_{n−1}}} → \frac{1}{e},

B_{n+1} ∼ e (B_{n})^{1+ \frac{1}{n}} .

Proof. It is an immediate consequence of Theorem 5 and Remark 6.

The following Theorem is well-known [4, Ex. 1(2), p. 291] [2, Corollary 5 ]. We give a short proof using equation (18).

Theorem 12. The sequence B_{n+1} − B_{n} is strictly increasing.

Proof. We have (see (18))

B_{n+2} − B_{n+1} = ∑_{k=0}^{n} \binom{n + 1}{k}B_{k}, B_{n+1} − B_{n} = ∑_{k=0}^{n−1} \binom{n}{k}B_{k}.

Consequently

(B_{n+2} − B_{n+1}) − (B_{n+1} − B_{n}) = ∑_{k=1}^{n−1} (\binom{n + 1}{k} − \binom{n}{k}) B_{k} + (n + 1)B_{n} > 0,

since

\binom{n + 1}{k} > \binom{n}{k} (k = 1, …, n).

In closing the article we give one more property of the Bell numbers but before prove the following general statement.

Theorem 13. Let F_{n} be a strictly increasing sequence of positive integers such that

log F_{n} ∼ Cn log n (C > 0).

Let ω(x) be the number of F_{n} that do not exceed x. The following asymptotic formula holds.

ω(x) ∼ \frac{log x}{C log log x}.

Proof. Let α_{n} be a strictly increasing sequence of positive numbers and let α(x) be the number of α_{n} that do not exceed x. It is well-known [3, p. 129] that

α_{n} ∼ Cn log n ⇔ α(x) ∼ \frac{x}{C log x}.

Now,

F_{n} ≤ x ⇔ α_{n} = log F_{n} ≤ log x.

Consequently

ω(x) = α(log x) ∼ \frac{log x}{C log log x}.

Example 14. If F_{n} = B_{n} is the n-th Bell number and ω(x) is the number of Bell numbers that do not exceed x then (see (19))

ω(x) ∼ \frac{log x}{log log x}.

4 Acknowledgements

The author would like to thank the anonymous referees for their valuable comments and suggestions for improving the original version of this manuscript. The author is also very grateful to Universidad Nacional de Luján.

References

[1] G. E. Andrews, The Theory of Partitions, Cambridge University Press, 1984.

[2] S. Bouroubi, Bell numbers and Engel’s conjecture, Rostock. Math. Kolloq. 62 (2007), 61–70.

[3] K. Chandrasekharan, Introduction to Analytic Number Theory, Springer, 1968.

[4] L. Comtet, Advances Combinatorics, D. Reidel Publishing Company, 1974.

[5] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, On the Lambert W function, Adv. Comput. Math. 5 (1996), 329–359.

[6] N. G. de Bruijn, Asymptotic Methods in Analysis, Dover, 1981.

[7] R. Jakimczuk, Functions of slow increase and integer sequences, J. Integer Seq. 13 (2010), Article 10.1.1.

[8] M. Klazar, Counting set systems by weight, Electron. J. Combin. 12 (2005), # R11.

[9] D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 3, Pearson Education, 2005.

[10] L. Lovász, Combinatorial Problems and Excercises, Second Edition, AMS Chelsea Publishing, 2007.

[11] L. Moser and M. Wyman, An asymptotic formula for the Bell numbers, Trans. Roy. Soc. Canada 49 (1955), 49–53.

[12] J. Rey Pastor, P. Pi Calleja, and C. Trejo, Análisis Matemático, Volumen I, Octava Edición, Editorial Kapelusz, 1969.

2000 Mathematics Subject Classification: Primary 11B99; Secondary 11B73. Keywords: functions of slow increase, integer sequences, Bell numbers.

(Concerned with sequence \underline{A000110}.)

Received December 9 2010; revised versions received March 28 2011; May 4 2011. Published in Journal of Integer Sequences, May 10 2011.

Return to Journal of Integer Sequences home page.