 Advances in Pure Mathematics, 2011, 1, 300-304 doi:10.4236/apm.2011.15055 Published Online September 2011 (http://www.SciRP.org/journal/apm) Copyright © 2011 SciRes. APM A Tiling Lemma and Its Application to the Ratio Test for Convergence of Series James D. Stein Jr., Linda Ho Department of Mathematics California State University Long Beach, CA Department of Mathematics El Camino College Torrance, CA E-mail: jimstein@csulb.edu, lho@elcamino.edu Received July 5, 2011; revised August 1, 2011; accepted August 12, 2011 Abstract We prove that any collection which tiles the positive integers must contain one of two types of sub-collec- tions. We then use this result to prove a variation of the Ratio Test for convergence of series. This version of the Ratio Test shows the convergence of certain series for which the Root Test (which is known to be more powerful than the conventional Ratio Test) fails. This version of the Ratio Test is also used to prove a ver- sion of the Banach Contraction Principle for self-maps of a complete metric space. Keywords: Tiling, Ratio Test, Banach Fixed-Point Theorem 1. Introduction It is shown in  that tiling results can be used in some fixed-point theorems to circumvent tedious and compu-tational analytic arguments. We show in this paper that tiling results can also be used to improve the Ratio Test for convergence of series. The classical Ratio Test is known to be dominated by the Root Test; if the Ratio Test demonstrates that a series converges, the Root Test would also yield this result. The improved Ratio Test presented in this paper can be used to demonstrate the convergence of some series for which the Root Test will not yield conclusive results. 2. A Simple Tiling Result On the real line, let , and let jk,tjk denote the tile extending from 12j to 12k; that is, the closed interval 12, 1jk2. Since we are only con-cerned with integers in this paper, notice that this tile covers all the integers from j through k inclusive. Lemma 2.1 Let T be a collection of distinct tiles of the above form such that every positive integer is covered by at least one tile in T. Then either 1) N such that sup :,ktNK T*T,, or 2) there is a sub-collection of T, *,:1,2,nnTT n such that for each n, 1nn, 1nnT , and each positive integer belongs to either one or two tiles in . *Proof: Suppose that 1) does not hold. We can there-fore assume that, for each n, only finitely many pairs ,pq with pnq and ,q Ttp . Let 1,tkmax :qk T, and let 111, q. Having chosen n and n such that all positive in-tegers n by construction, and all positive integers <n+1 belong to one of the tiles t[1, 1], ···, t[n+1 ,n+1] 2) n+1 > n: if n+1  n, then we should have chosen n+1 instead of n, since t[n , n] is a proper subset of t[n+1, n+1], contradicting the maximality of n . Notice that no three consecutiv e tiles of the form t[n, n] overlap. If k  t[n+j, n+j] for j = 0,1,2, then n+j  k  n+j for j = 0,1,2. But then k  n < n + 1 and n+2 > n+1  n + 1  t[n+2, n+2], contradicting the maximality of n+1. Therefore each integer k either belongs to a unique tile t[n, n] or to two consecutive tiles: t[n, n] and t[n+1, n+1]. The collection *,:1,2,nnTt n. 3. An Application of Lemma 2.1 to the Ratio Test We now use Lemma 2.1 to prove our version of the Ra-tio Test. Theorem 3.1 (Ratio Test)—Assume that a1 > a2 J. D. STEIN JR. ET AL.301 > ··· > 0 and x Assume further that  M lim 0.na (0,1) such that, for every integer n, there exist integers j, k with j < n < k and aj+1 + ··· + ak+1 < M(aj + ··· + ak). Then converges. 1nnaProof: Suppose that, for n > 1, b2 + ··· + bn+1 < M(b1 + ··· + bn). Then b2 + ··· + bn + bn+1 < Mb1 + M(b2 ··· +bn)  (1 – M) (b2 ··· +bn) < Mb1 – bn+1; adding (1 – M)b1 to both sides and dividing by (1 – M) yields b1 + ··· + bn < 11M (b1 – bn+1). This inequality also holds if n = 1, for then b2 < Mb1  b2 < Mb1 + b1 – b1  b2 < b1 + (M – 1)b1  (1 – M) b1 < b1 – b2  b1 < 11M (b1 – b2). If 1 < j < k, we say that the tile t[j, k] belongs to the collection T if aj + ··· + ak < M(aj–1 + ··· + ak–1) < 11M (aj–1 – ak). The hypothesis enables us to apply the Lemma, and we can conclude that either 1) N such that sup {k: t[N, k] T } = +, or 2) there is a sub-collection of T of the type de-scribed in the Lemma. *TIf (1) holds, we can assume WLOG that N = 2, and so  an increasing sequence of integers with and :1,2,nq11q1nnqqa21aaMa . Therefore 1111111nnqqaa a1aaMM  , so the partial sums of 1jjaform a bounded monotone se-quence. We can therefore assume from the Lemma that we have a sub-collection of T consisting of tiles t[pn, qn] such that each integer belongs to either one or two tiles in , and such that pn < pn+1 and qn < qn+1 for each in-teger n, so if an integer belongs to two tiles in , they are consecutive tiles. *T*T*TObserve that . We can subdivide the 11 nnqnnnkpakaright-hand side summation over the tiles t[pn, qn] into three parts: tiles of length 1, tiles of length longer than 1 which do not overlap other tiles in , and tiles of length longer than 1 which overlap other tiles in . *T*TThe summation over tiles of length 1(qn = pn): if there are only a finite number of such tiles, the sum of these terms is clearly finite. If there are infinitely many such terms, since the sequence {an: n = 1,2, ···} is decreasing, the summation over all such terms is dominated by the geometric series whose first term is a1 and whose ratio is M. Once the tiles of length 1 have been eliminated, we can renumber the remaining tiles as {t[pn, qn]: n = 1,2, ···} with pn < pn+1 and qn < qn+1. We look at two types of blocks consisting of consecutive tiles t[pk, qk], t[pk+1, qk+1], ···, t[pn, qn]. In the first type of block, consecutive tiles do not overlap; in the second, consecutive tiles overlap. The remaining tiles can be divided into alter-nating blocks of these two types simply by continuing to examine successive tiles to see whether they overlap or not. There are two cases: either there are infinitely many blocks of each of the two types, or there are only finitely many blocks of each of the two types; this last case oc-curs when all but finitely many tiles belong to a single block. We examine the first case, and then discuss how the analysis presented therein also handles the second case. If consecutive tiles t[pk, qk], t[pk+1, qk+1], ···, t[pn, qn] do not overlap, then pk < qk < pk+1 < qk+1 < ··· < pn < qn. The inequality pj < qj is strict because the tiles of length 1 were treated in the discussion above, and the inequality qj < pj+1 is strict because consecutive tiles do not overlap. Then 1111 1jkk nnjqnkpqpjkpaaaaaMq . This sum dominates the contribution from a typical block of consecutive non-overlapping tiles. Since pk < qk < pk+1 < qk+1 < ··· < pn < qn , the terms in the above sum decrease within a particular block, and since there is a gap between this block and the next block of consecutive non-overlapping tiles, the last term from the above sum is greater than the first term in the corresponding sum from the next block. Adding up the dominating sums from all such blocks and using the Alternating Series Test results in a convergent series. Finally, assume that consecutive tiles t[pk, qk], t[pk+1, qk+1], ···, t[pn, qn] overlap. Because t[pj, qj] and t[pj+1, qj+1] overlap, qj is common to both tiles, so pj < pj+1 < qj . No integer belongs to three tiles, so qj does not belong to t[pj+2, qj+2], and so qj < pj+2 . Therefore pk < pk+1 < qk < pk+2 < qk+1 < ··· < qn–2 < pn < qn–1 < qn. We use the same initial estimate as in the previous case, but permute the final dominating sum slightly.  1111111 111jkk nnjknkknnqnkpqpjkppqpqpqaaaaaMaaMaaaaq   The sum in brackets consists of two components: the Copyright © 2011 SciRes. APM J. D. STEIN JR. ET AL. 302 first term (1knq) and the sum [(apk – aqk) + ··· + (apn–1 – aqn–1)]. If we add up the first terms from all blocks of consecutive overlapping tiles, the sum con-verges by the Alternating Series Test, and the same can be said of all the bracketed sums of the form [(apk – aqk) + ··· + (apn–1 – aqn–1)]. This completes the proof in the case where there are infinitely many blocks of each of the two types. paaIf all but finitely many of the tiles belong to a single block, the dominating sum is a sum over infinitely many tiles. The identical analysis (with upper limit of  in-stead of n) shows that the dominating sum is an alternat-ing series which converges by the Alternating Series Test. The classical Ratio Test requires that the ratio of suc-cessive terms be dominated by a constant <1. In the Ra-tio Test presented in Theorem 1, the information is not necessarily obtainable about individual terms, but about blocks of consecutive terms. As a result, this ratio test might be useful in situations when the individual terms of the series are not known, but information about blocks of consecutive terms is available. 4. Necessity of the Contractivity Hypothesis In the classical Ratio Test, it is not required that succes-sive terms decrease, although that is a trivial conse-quence of the hypothesis that the ratio of successive terms be less than 1. The Root Test does not require that successive terms decrease, so one might wonder if this hypothesis is really need ed in Theorem 1. The following example addresses this question. Example 4.1. Let M = 0.9. For n = 0,1,2, ··· define 31 1nan 32 110nan 33 110nan Let and for n = 0,1,2, ··· 31npn 34nqnNotice that each integer belongs to at least one and at most two intervals,nnpq. We want to ensure that . To show this, 11 nnnnpqpaaMaa qnotice that  11112 1110 10110110 10113 210 1130 2010 1nnnnn nnnnnnn  So 11 130 20100 1nnpqnaann . Also 1111912 10.9 1010110 1019221210 101198 108100 1nnnn nnnnnnnn  So 198 108 100 1nnpqnMa ann . Therefore, . 11 nnnnpq paaMa qaSince 313233lim limlim0,nn nnn naaa  0. so lim nna Note also that 1nna diverges, since it dominates the harmonic series. 5. An Example for Which Theorem 3.1 Succeeds Where the Root Test Fails It is well known that, although the Ratio Test is easier to apply than the Root Test, the Root Test is more dis-criminating (see , Theorem 3.37). We now present a series for which the Ratio Test of Theorem 3.1 demon-strates convergence, but for which the Root Test is in-conclusive. Example 5.1 The basis of our example is the follow-ing: suppose M  (0,1), a1 and an integer n are given, and 211nMaa Mn M1a  Then 111 n.MnMa Ma  11 12111 .nnnnnaM anaaaMaa   Notice that 11Mn MnnM1 11.nna, and so aa Now let b, c > 0, and consider 1limxxbucx d. Taking natural logarithms of both sides yiel d s ln ln1ln limlnlimxxbcxdbuxcxd x  , and ap- plying L’Hopital’s Rule we obtain ln lim01ccx dxu, and so u = 1. Consequently we see that for any  > 0, we can always find an integer N such that n > N  111.1 nMaMnM Copyright © 2011 SciRes. APM J. D. STEIN JR. ET AL.303 We use this to construct a series of decreasing 1nn bterms which satisfies the hypotheses of the Theorem, but for which the Root Test is inconclusive. Let b1 = 1, let a1 = b1, and choose an integer N1 such that n > N1  11111 2nMaMnM and 1 11 MaMnM  . Let 11121 1 NMabbMNM . Having defined 1pNb, let 1b11pNab and choose an integer 1 ppNN such that 1pnN11111 2nMaMnMp  and 111 MaMnM . Let 211 11 1 ppNN pMabb .MNM   As constructed, the sequence satisfies the :1,2,nbnhypotheses of the theorem, and so converges. 1nnbHowever, by construction we also have limsup 1nnn , and so the Root Test is inconclusive for this series. bb6. Applications Our first application is that the tiling result of Lemma 2.1 also applies to the Comparison Test for convergence of series. Let be a convergent series of positive terms. Let be a series of positive terms. If k  n, let C[k, n] 1nnb1nanbe the statement: knkn. We will also let [p, q] = {k: k is an integer, p  k  q }. aab Theorem 6.1 Suppose N  n  N   p, q with p  n  q and C[p, q]. Then converges. 1nnaProof: We can assume WLOG that N = 1. If  an in-teger p  sup {q: C[p, q] }= +, then converges 1nnabecause if C[p, qk] for q1 < q2 < ···, then the partial sums 1kqjja form a bounded monotone increasing sequence. We can therefore assume that, for each n,  only finitely many pairs (p, q) with and C[p, q]. Applying the Lemma, we can find a sequence of tiles pnq{t[n , n]: n = 1,2, ···} such that C[n , n] for each n and each integer k either belongs to a unique interval [n , n] or to two consecutive intervals: [n , n] and [n+1, n+1]. Note that, for any n, 11111 22jjnnjjnnjkkjjjkjkj jaabb jb since each k appears in a maximum of two [j, j]. So the partial sums of 1jja form a bounded monotone se-quence, and so 1jjaconverges. The second application uses Theorem 3.1 to obtain a different version of the Banach Contraction Principle. As mentioned earlier,  shows the use of tiling arguments in fixed-point theorems; Theorem 6.2 represents another such application. There may well be similar applications to other fixed-point theorems than the one presented here, especially in light of the fact that convergent series are frequently used in demonstrating the existence of fixed points. Theorem 6.2 Let (X, d) be a complete metric space, and assume that T is a self-map of X satisfying d(Tx, Ty) < d(x, y). Suppose there is an M (0, 1) such that for each pair x, y  X, there is a positive integer n = n(x, y) such that d(Tx, Ty) + ··· + d(Tn+1x, Tn+1y) < M [d(x, y) + ··· + d(Tnx, Tny)]. Then T has a unique fixe d point. Proof: The proof of this corollary uses standard ideas, and will be abbreviated. Start with the pair (x, Tx), and use the hypothesis iteratively to obtain a convergent (by Theorem 1) series n1d(Tnx, Tn+1x). The convergence of this series implies that the sequence of iterates {Tnx: n = 1, 2, ···} is Cauchy, and its limit can be shown by the usual methods to be a fixed point of T. Note that the con-tractivity hypothesis d(Tx, Ty) < d(x, y) is needed to sat-isfy the requirement that the terms of the series decrease. To show that the fixed point is unique, suppose that x and y are two distinct fixed points. Let n be an integer such that 11,,nndTxTydTxTyMdxy , ,nnTy,dxydTx. Since both x and y are fixed points, each summand on both sides is , and the ine-quality reduces to nd(x, y) < Mnd(x, y) < nd(x, y). This is impossible unless x = y. We conclude by presenting an example for which the standard Banach Contraction Principle is inapplicable, but for which Theorem 6.2 demonstrates the existence of a fixed point. Example 6.3 Let X be the closed interval 0,1 2 with the usual metric. Define . Then the hy-potheses of Theorem 6.2 hold, but T is not a strict con-traction in the sense of the Banach Contraction Principle. 2Tx xProof: Note first that . We assume WLOG 2Tx x4Copyright © 2011 SciRes. APM J. D. STEIN JR. ET AL. Copyright © 2011 SciRes. APM 304 22,,1.dTxTydxyyxy xyxyx yxyx yx  that xy in the rest of the proof.   22,,,dTxTyyxyxy xdxyy xdxy , since . 1xyNote that 22,,dTxTyyx yxdxyy x11,.. Since y and x So the question of the existence of M reduces, on divi-sion by yx, to whether it is possible to find M with 0M1 and 2211yx yxMyx  . The constant M = 0.8 satisfies this inequality, because 1yx and 220.5yx0.8 1yx. So  221yxy xyx1.6 1.5yx, complet-ing the proof. can be chosen so that is arbitrarily close to 1, there cannot be a constant M with and . So the standard Banach Contrac-tion Principle does not apply to this example. yx,0MxTy0M22x Ty,dT MdxyThe authors would like to thank Prof. Jacek Jachymski, Mr. Merrick Sterling, and the referee for suggestions related to this paper. However, we can show that there exists a constant M with such that  ,, ,d Td TxTyMdTxTydxy  7. References 2 44222222,,1dydTxTyyx y xyxyxyxyxyxyx yxyx  2Tx T J. R. Jachymski, Schroder, Bernd; Stein, D., James Jr. , “A connection between fixed-point theorems and tiling prob-lems,” Journal of Combinatorial Theory, Series A, Vol. 87, No. 2, 1999, pp. 273-286. doi:10.1006/jcta.1998.2960  W. Rudin, “Principles of Mathematical Analysis,” McGraw-Hill, New York, 1964.