A CONVERGENCE CRITERION FOR RECURRENT SEQUENCES WITH APPLICATION TO THE PARTITION LATTICE

László Babai and Tamás Lengyel

Received:

\underline{Abstract.} We prove a fairly general convergence criterion for sequences satisfying a linear recurrence (defined by an infinite triangular matrix). We prove that every sequence of positive numbers satisfying a nearly convex linear recurrence with finite retardation and active predecessors converges to a positive limit. – Informally, near convexity means the coefficients are nonnegative and the sum of coefficients in each equation is approximately 1; finite retardation means low order terms have little weight; and active predecessors mean that the immediate predecessor carries a weight greater than a fixed positive constant. – We present an application to the asymptotic number of not necessarily maximal chains in the partition lattice. The coefficients of the corresponding recurrence are the Stirling numbers of the second kind. AMS 1980 classification numbers: 40A05, 11B37, 05A15, 06C10, 11B73

1. Introduction

The use of recurrence relations is one of the classical methods in combinatorial enumeration. Some general techniques, such as the generating function method, are commonly used, and ad hoc methods are known to handle specific recurrences. For general background, we refer the reader to [15], [6], [11], and [2]. Combinatorial applications can be found e.g. in [1], [3], [4], [10], and [16]. An important application area of these methods is the analysis of algorithms (cf. e.g., [5], [6], [7], [8], [11], [15], and [17]). Very seldom does one find explicit closed formula solutions to enumeration problems. It is more common that the generating function can be determined on the basis of functional equations derived from a recurrence relation. There are remarkable examples where these methods, in combination with complex function techniques, lead to asymptotic estimation of the coefficients of the generating function ( [13], [14]). In some cases, however, generating function techniques do not seem to be particularly helpful. One case in point may be the number Z(n) of (not necessarily maximal) chains in the partition lattice. Lengyel [9] found an explicit function f(n) such that c_{1}f(n) < Z(n) < c_{2}f(n) holds for every n (c_{1}, c_{2} are positive constants). In this paper we give a fairly general convergence criterion for sequences defined by a linear recurrence. As an application we deduce that the quotient Z(n)/f(n) tends to a positive limit. (However, we are not able to tell the value of that limit.)

2. The convergence criterion

We shall consider infinite sequences of real numbers x(n) satisfying the linear recurrence given by a (truncated) infinite triangular matrix C = {c(n, k)} of coefficients:

(2.1)  ∑_{k=1}^{n−1} c(n, k)x(n − k) = x(n)  (n ≥ N).

This recurrence is thus assumed to hold for sufficiently large n only. For convenience we shall set c(n, k) = 0 for k ≥ n. Throughout this paper, c(n, k) will be non-negative. Theorem 1 below gives a fairly general convergence criterion for sequences satisfying this linear recurrence. First we have to introduce some additional terminology. We call the recurrence (2.1) convex if its coefficients are non-negative and its row sums are equal to 1. We call the recurrence (2.1) nearly convex if its coefficients are non-negative and its row sums are approximately equal to 1 in the sense of ℓ_{1}-norm. More precisely, for sufficiently large n, let

(2.2)  γ_{n} = −1 + ∑_{k=1}^{∞} c(n, k)  (n = N, N + 1, …).

We call (2.1) nearly convex, if

(2.3)  ∑_{n=N}^{∞} |γ_{n}| < ∞.

\underline{LEMMA 1.} Let x(n) be a sequence of positive reals, satisfying a nearly convex recurrence. Then there exist positive constants c_{1}, c_{2} such that 0 < c_{1} < x(n) < c_{2} for every n.

\underline{PROOF.} Let a^{+} and a^{−} be the positive and negative parts of the real a, i.e. a^{+} = (a + |a|)/2 and a^{−} = (a − |a|)/2, respectively. Let A = max{x(n) : 1 ≤ n < N}. Then an induction shows that

x(n) ≤ A ∏_{i=N}^{n}(1 + γ_{i}^{+}) (n ≥ N)

and the right hand side is bounded according to condition (2.3). Let B = min{x(n) : 1 ≤ n < N}. An analogous argument shows that

\underline{lim}_{n→∞} x(n) ≥ B ∏_{i=N}^{∞}(1 + γ_{i}^{−}) > 0.

The following quantity measures the degree of retardation of the recurrence (2.1), i.e. the direct effect of low index terms x(i) on x(n) in (2.1):

(2.4)  ϵ_{n,k} = 1 + γ_{n} − ∑_{i=1}^{k} c(n, i) = ∑_{i=k+1}^{∞} c(n, i).

We say that the recurrence (2.1) has finite retardation if there exists a constant K such that

(2.5)  ∑_{k=0}^{∞} ϵ_{m+k,k} < K

holds for all sufficiently large values of m. We say that the recurrence (2.1) has active predecessors if there exists a positive constant c such that c(n, 1) ≥ c for every sufficiently large n.

\underline{THEOREM 1.} Let x(n) be a sequence of positive reals, satisfying a nearly convex recurrence with finite retardation and active predecessors. Then the sequence x(n) converges to a positive limit. \underline{DISCUSSION.} We have to comment on the assumptions. The finite retardation condition is quite natural. For instance, it is automatically satisfied, if the coefficients are bounded and each x(n) is expressed in terms of a bounded number of its predecessors. Consider now the divergent sequence given by the recurrence x(1) = 1, x(2) = 2, x(n) = x(n − 2) (n ≥ 3). This recurrence is convex and has finite retardation; it demonstrates that the condition of active predecessors cannot be omitted. The necessity of the near-convexity assumption under certain conditions is the content of the following partial converse to the Theorem.

\underline{PROPOSITION.} Assume the monotone sequence \{x(n)\} converges to a positive limit. If {x(n)} satisfies a recurrence with nonnegative coefficients and finite retardation, then the recurrence must be nearly convex.

\underline{PROOF.} By definition,

x(n)γ_{n} = −x(n) + ∑_{i=1}^{∞} x(n)c(n, i) = ∑_{i=1}^{∞}(x(n) − x(n − i))c(n, i).

(Recall that c(n, i) = 0 for i ≥ n.) This implies that γ_{n} has constant sign (positive if x(n) increases). Furthermore, slightly rearranging, we find

x(n)γ_{n} = ∑_{i=1}^{∞} ∑_{j=0}^{i−1}(x(n − j) − x(n − j − 1))c(n, i) = ∑_{j=0}^{∞}(x(n − j) − x(n − j − 1))ϵ_{n,j}.

Consequently

∑_{n=N}^{∞} x(n)γ_{n} = ∑_{m=1}^{∞}(x(m) − x(m − 1)) · ∑_{j=max{0,N−m}}^{∞} ϵ_{m+j,j}.

The right hand side converges because of the finite retardation condition and the monotonicity of the x(n). Consequently, the series ∑_{n=N}^{∞} x(n)γ_{n} is convergent; and therefore the series ∑_{n=N}^{∞} γ_{n} is also convergent. We conclude this discussion with the observation that every monotone sequence x(n) of reals, converging to a positive limit, satisfies a nearly convex recurrence with finite retardation and active predecessors. Indeed, set c(n, 1) = x(n)/x(n − 1), and c(n, i) = 0 for i ≠ 1. The conditions are easily verified. A more significant example of a recurrence satisfying these conditions will be given in Section 3. In view of these comments, the following question seems natural. Does every sequence of positive reals, converging to a positive limit, satisfy a nearly convex recurrence with finite retardation and active predecessors?

\underline{PROOF OF THEOREM 1.} First we observe that for every n, 0 < c_{1} < x(n) < c_{2} for some constants c_{1} and c_{2}, according to Lemma 1. Another preliminary observation is the following. \underline{CLAIM 1.} There exists a positive constant K_{1} such that for every sufficiently large m,

(2.6)  E(m) := ∏_{j=m+1}^{∞}(1 − \frac{ϵ_{j,j−m}}{1 + γ_{j}} ) ≥ K_{1}.

\underline{PROOF.} We may assume that 1 > γ_{j} > −1/2 for j ≥ m + 1. By the “active predecessors” condition, we may assume c(j, 1) ≥ c > 0 for all j ≥ m + 1. It follows that

1 − \frac{ϵ_{j,j−m}}{1 + γ_{j}} = \frac{1}{1 + γ_{j}} ∑_{i=1}^{j−m} c(j, i) ≥ \frac{c(j, 1)}{1 + γ_{j}} > c/2.

Noting that 1 ≥ 1 − x ≥ c/2 > 0 implies 1 − x ≥ exp (−c′x) for some constant c′ > 0, we infer that

E(m) ≥ exp(−c′ · ∑_{j=m+1}^{∞} \frac{ϵ_{j,j−m}}{1 + γ_{j}} ) ≥ exp(−2c′ · ∑_{j=m+1}^{∞} ϵ_{j,j−m}) ≥ exp(−2c′K) =: K_{1}.

In the last inequality we made use of the “finite retardation” condition (2.5). This concludes the proof of Claim 1.

Next we outline the strategy of the proof of Theorem 1. Let M be an arbitrary positive real such that

0 < M < \overline{lim}_{n→∞} x(n).

We shall define an increasing sequence of integers n_{i} and an increasing sequence of nonnegative reals β_{i} such that n_{i} → ∞ and β_{i} → 1 (as i → ∞) and for every i ≥ 0 and n > n_{i}

(2.7)  x(n) ≥ β_{i}M.

This will imply \underline{lim}_{n→∞} x(n) ≥ M. Since this will hold for any M < \overline{lim}_{n→∞} x(n), we shall have

\underline{lim}_{n→∞} x(n) = \overline{lim}_{n→∞} x(n) = lim_{n→∞} x(n)

proving Theorem 1. We define β_{i} as follows. Since we are at liberty to increase the value of N a finite number of times, let N be an integer greater than all the bounds implied by previous “sufficiently large” statements, including Claim 1. Let Γ = ∏_{j=N}^{∞}(1 + γ_{k}^{−}) > 0. Set

β_{i} = 1 − (1 − K_{1}Γ/2)^{i},

where the (small) positive value K_{1} is taken from Claim 1. We set n_{0} = 0 and define the n_{i} inductively for i ≥ 1. For n ≥ k, set Δ(n, k) = ϵ_{n,n−k} − γ_{n}^{−}. For every k, the non-negative series ∑_{n=k}^{∞} Δ(n, k) converges by the conditions of near convexity and finite retardation. Given n_{i}, let us select n_{i+1} > n_{i} such that

(2.8)  x(n_{i+1}) ≥ M,

and

(2.9)  ∑_{n=n_{i+1}}^{∞} Δ(n, n_{i}) < (1 − β_{i})K_{1}Γ/2.

In addition, we select n_{1} such that n_{1} > N.

\underline{CLAIM 2.} With these choices of the sequences n_{i} and β_{i}, inequality (2.7) holds for every i ≥ 0 and n ≥ n_{i}.

\underline{PROOF.} Observe that β_{0} = 0, so for i = 0, inequality (2.7) holds vacuously for every n. We proceed by induction on i. Suppose inequality (2.7) holds for a particular i; we prove it for i + 1. For m ≥ n let us set

x_{m}^{n} = min{x(n), …, x(m)}.

The inductive step is based on the following observation. For n ≥ n_{i+1}, the recurrence (2.1) implies

x(n) ≥ {c(n, 1)x(n − 1) + … + c(n, n − n_{i+1})x(n_{i+1})}+
+ {c(n, n − n_{i+1} + 1)x(n_{i+1} − 1) + … + c(n, n − n_{i})x(n_{i})}

and therefore

x(n) ≥ (1 + γ_{n} − ϵ_{n,n−n_{i+1}})x_{n−1}^{n_{i+1}} + (ϵ_{n,n−n_{i+1}} − ϵ_{n,n−n_{i}})β_{i}M.

A simple rearrangement yields

x(n) − β_{i}M ≥ (x_{n−1}^{n_{i+1}} − β_{i}M)(1 + γ_{n} − ϵ_{n,n−n_{i+1}}) + β_{i}M(γ_{n} − ϵ_{n,n−n_{i}})

≥ (x_{n−1}^{n_{i+1}} − β_{i}M)(1 + γ_{n}^{−})(1 − \frac{ϵ_{n,n−n_{i+1}}}{1 + γ_{n}} ) − β_{i}M(ϵ_{n,n−n_{i}} − γ_{n}^{−})

= (x_{n−1}^{n_{i+1}} − β_{i}M)Γ(n, n_{i+1}) − β_{i}MΔ(n, n_{i}),

where for k ≥ j

(2.10)  Γ(k, j) = (1 + γ_{k}^{−})(1 − \frac{ϵ_{k,k−j}}{1 + γ_{k}} ).

From this we obtain for n ≥ n_{i+1} by induction on n that

(2.11) x(n) − β_{i}M ≥ (x(n_{i+1}) − β_{i}M) ∏_{k=n_{i+1}+1}^{n} Γ(k, n_{i+1}) − β_{i}M · ∑_{k=n_{i+1}+1}^{n} Δ(k, n_{i}).

Consequently, for n ≥ n_{i+1} we have (noting that n_{i+1} > N hence Claim 1 applies)

x(n) − β_{i}M ≥ (M − β_{i}M)ΓE(n_{i+1}) − β_{i}M · ∑_{k=n_{i+1}+1}^{∞} Δ(k, n_{i})
≥ M(1 − β_{i})ΓK_{1} − M(1 − β_{i})ΓK_{1}/2
= M(1 − β_{i})ΓK_{1}/2 = M(β_{i+1} − β_{i});

hence x(n) ≥ β_{i+1}M, as required. This completes the proof of Claim 2 and thereby the proof of Theorem 1. It would be of interest to know how fast the sequence x(n) converges. If x(n) converges rapidly then one can get an estimate on the unknown limit by numerical calculations.

3. An application

In this section we present an application of Theorem 1 to the partition lattice. In [9] we studied the number Z(n) of the not necessarily maximal chains from 0 to 1 in the partition lattice Eq(n) of an n-set. The lattice Eq(n) has minimal element {{1}, {2}, …, {n}} and maximal element {{1, 2, …, n}}. It is easy to see [9] that Z(n) satisfies the recurrence

(3.1)  Z(n) = ∑_{k=1}^{n−1} S(n, k)Z(k),  n ≥ 2,

where S(n, k) denotes the Stirling number of the second kind, i.e. the number of partitions into k nonempty parts of a set of n elements.

One can easily derive the functional equation

(3.2)  2Z(x) = Z(e^{x} − 1) + x

for the (divergent) exponential generating function

(3.3)  Z(x) = ∑_{n=1}^{∞} Z(n)\frac{x^{n}}{n!} ,

but we were unable to make use of this formula. We list the values of Z(n) for n ≤ 12 :

\begin{matrix}n = & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ Z(n) = & 1 & 1 & 4 & 32 & 436 & 9012 & 262760 & 10270696 \end{matrix}

\begin{matrix}n = & 9 & 10 & 11 & 12 \\ Z(n) = & 518277560 & 32795928016 & 2542945605432 & 237106822506952 \end{matrix}

These values have been obtained using equation (3.1) and the MACSYMA system. Equation (3.2), however, has led us nowhere, therefore we have chosen another approach in [9] to analyze the asymptotic order of magnitude of Z(n). Let

(3.4)  f(n) = (n!)^{2}(2 ln 2)^{−n}n^{−1−(ln 2)/3}.

In [9] (Theorem 1.1) we have shown that there exist positive constants C_{1} and C_{2} such that

(3.5)  C_{1} ≤ Z(n)/f(n) ≤ C_{2}.

Here we prove the following stronger version.

\underline{THEOREM 2.} The following limit exists:

(3.6)  lim_{n→∞} Z(n)/f(n) = C,

where C is a positive constant. \underline{REMARK.} Although our proof of Theorem 2 does not suggest any value for the limit, we note that numerical evidence appears to suggest that it is slightly greater than 1.

\begin{matrix}n = & 1 & 2 & 3 & 4 & 5 \\ Z(n)/f(n) = & 1.38629 & 1.12780 & 1.14468 & 1.13061 & 1.12426 \end{matrix}

\begin{matrix}n = & 10 & 50 & 100 & 150 & 200 \\ Z(n)/f(n) = & 1.11147 & 1.10123 & 1.09996 & 1.09953 & 1.09932 \end{matrix}

We propose, as an open problem, the approximate calculation of the limit.

\underline{PROOF.} We will use Theorem 1. Let us consider the normalized form Z^{∗}(n) = Z(n)2^{n}/(n!)^{2} instead of the rapidly growing Z(n). The function Z^{∗}(n) satisfies the recurrence

(3.7)  Z^{∗}(n) = ∑_{k=1}^{n−1} a(n, k)Z^{∗}(n − k),

where a(n, k) = S(n, n − k)2^{k}/[n]_{k}^{2} and [n]_{k} = n(n − 1) … (n − k + 1). We set y(n) = (ln 2)^{−n}n^{−1−(ln 2)/3}, x(n) = Z^{∗}(n)/y(n) = Z(n)/f(n) and c(n, k) = a(n, k)y(n−k)/y(n). With this notation, the positive sequence x(n) satisfies the recurrence (2.1) for n ≥ 2 (so we may set N = 2). We shall verify that the recurrence (2.1) given by these coefficients satisfies the conditions of Theorem 1. This will guarantee that a positive limit lim_{n→∞} Z(n)/f(n) = lim_{n→∞} = Z^{∗}(n)/y(n) exists, as required. We shall need three lemmas from [9]:

\underline{LEMMA A.} (Lemma 2.2, [9])

(3.8)  ∑_{k=1}^{n−1} a(n, k) y(n − k) = y(n)(1 + O(1/n^{2})).

\underline{LEMMA B.} (Lemma 3.1’, [9]) There is an absolute constant C′′ such that for k^{4} < n

(3.9)  |a(n, k) − \frac{1}{k!}| < C′′ \frac{1}{k!} \frac{k^{2}}{n} .

(Actually, Lemma 3.1’ in [9] states a stronger result, which includes the second term of the asymptotic expansion. We shall not need this finer estimate here, but it should be pointed out that we use it implicitly through Lemma A, the proof of which depends on it.)

\underline{LEMMA C.} (Lemma 3.2’, [9]) For each k in the interval 3 ln n/ ln ln n < k ≤ n − 1, we have

(3.10)  a(n, k) < 1/n^{2}.

We can easily check condition (2.3) of Theorem 1. Clearly,

(3.11)  x(n) = ∑_{k=1}^{n−1} c(n, k)x(n − k).

From Lemma A we have

∑_{k=1}^{n−1} c(n, k) = 1 + γ_{n}

where γ_{n} = O(1/n^{2}). The coefficients being non-negative, this proves that our recurrence is nearly convex. Using the definition of y(n), we can express c(n, k) as

(3.12)  c(n, k) = \begin{cases}a(n, k)(ln 2)^{k}(1 − k/n)^{f}, & for k : 1 ≤ k ≤ n − 1 \\ 0, & for k ≥ n \end{cases}

where f = −1 − (ln 2)/3 = −1.231 . . .. In particular, lim_{n→∞} c(n, 1) = ln 2 > 0, verifying the active predecessors. To complete the proof, we have to verify the finite retardation condition (equation (2.5)). We have to prove that the sums

S_{m} := ∑_{k=0}^{∞} ϵ_{m+k,k} = ∑_{k=0}^{∞} ∑_{i=k+1}^{∞} c(m + k, i)

10 Babai–Lengyel (m ≥ N) are uniformly bounded. We observe that for some constant C_{1} we have a(n, k) < C_{1} for every n, k; furthermore f > −2; hence c(n, i) ≤ C_{1}(ln 2)^{i}(1 − i/n)^{−2} ≤ C_{1}(ln 2)^{i}(i + 1)^{2} (because either n ≥ i + 1 or c(n, i) = 0). Consequently,

S_{m} = ∑_{i=1}^{∞} ∑_{k=0}^{i−1} c(m + k, i) ≤ ∑_{i=1}^{∞} C_{1}(ln 2)^{i}i(i + 1)^{2}.

The right hand side of the last equation is finite and independent of m.

\underline{References}

1. Bender, E. A.: Asymptotic methods in enumeration, SIAM Review 16(1974), 485-515 2. Brualdi, R. A.: Introductory Combinatorics, North-Holland, New York, 1977

3. Comtet, L.: Advanced Combinatorics, D. Reidel, Dordrecht, 1974

4. Goulden, I. P., Jackson, D. M.: Combinatorial Enumeration, Wiley, New York, 1983 5. Graham, R. L., Knuth, D. E., Patashnik,O.: Concrete Mathematics, Addison-Wesley,

Reading, MA, 1988

6. Greene, D. H., Knuth, D. E.: Mathematics for the Analysis of Algorithms, second edition, Asymptotic Methods, Birkhäuser, Boston, 1982

7. Knuth, D. E.: The Art of Computer Programming, Vol. 1: Fundamental Algorithms, second edition, Addison-Wesley, Reading, MA, 1973

8. Knuth, D. E.: The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, MA, 1975

9. Lengyel, T.: On a recurrence involving Stirling numbers, European Journal of Combinatorics 5(1984), 313-321

10. Lovász, L.: Combinatorial Problems and Exercises, North Holland, New York and Akadémiai Kiadó, Budapest, 1979

11. Lueker, G. S.: Some techniques for solving recurrences, Computing Surveys, 12(1980), 419-436

12. Page, E., Wilson, L.: An Introduction to Computational Combinatorics, Cambridge University Press, 1979 13. Pólya, G.: Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische

Verbindungen, Acta Mathematica 68(1937), 145-254

14. Pólya, G., C. Read, R.: Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds, Springer, 1987

15. Purdom, Jr., P. W., Brown, C. A.: The Analysis of Algorithms, CBS Publishing, Holt, Rinehart and Winston, New York, 1985

16. Roberts, F. S.: Applied Combinatorics, second edition, Prentice-Hall,Englewood Cliffs, 1984

17. Sedgewick, R.: Algorithms, second edition, Addison-Wesley, Reading, MA, 1988

László Babai  Tamás Lengyel
Department of Computer Science  Department of Mathematics
University of Chicago  Occidental College
1100 E 58th St.  1600 Campus Dr.
Chicago, IL 60637, U.S.A.  Los Angeles, CA 90041, U.S.A.
and  and
Department of Algebra  Computer and Automation Institute,
Eötvös University  Hungarian Academy of Sciences
Budapest, Hungary H-1088  Budapest, Hungary H-1502
e-mail: laci@cs.uchicago.edu  e-mail: lengyel@oxy.edu