 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 [1] 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, 1jk2. 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, nn TT 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 Ttp . Let 1,tkmax :qk T, and let 11 1, q . Having chosen n and n such that all positive in- tegers <n belong to one of the tiles 11 ,,t , ,tnn , let 1 xma:, withkjk 1 nn j k and tj T,k. Let n+1 = max{j: j n+1 and t[j, n+1] T}. Note that 1) n+1 > 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, nn Tt 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. n a (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. 1n n a 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 < 1 1 (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 < 1 1 (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) < 1 1 (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. * T If (1) holds, we can assume WLOG that N = 2, and so an increasing sequence of integers with and :1,2, n q 1 1q 1 nn qq a 21 aaMa . Therefore 1111 1 11 nn qq aa a 1 aa M , so the partial sums of 1 j a 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* T Observe that . We can subdivide the 11 n n q n nnkp a k a right-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* T The 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 11 1 1 1 j kk nn j q n kpqp jkp aaaaa M 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. 11 1 1 11 1 1 1 1 j kk nn j kn kknn q n kpqp jkp pq pqpq aaaaa M aa M aaaa q The sum in brackets consists of two components: the Copyright © 2011 SciRes. APM  J. D. STEIN JR. ET AL. 302 first term (1 kn q ) 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. p aa 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 1 n an 32 1 10 n an 33 1 10 n an Let and for n = 0,1,2, ··· 31 n pn 34 n qn Notice that each integer belongs to at least one and at most two intervals , nn pq. We want to ensure that . To show this, 11 nn nn pqp aaMaa q notice that 11112 11 10 10110110 101 13 2 10 1 130 20 10 1 nnnnn n n nn n nn So 11 130 20 100 1 n n pq n aann . Also 1111912 1 0.9 1010110 101 92212 10 101 198 108 100 1 nnnn nn n nn n nn So 198 108 100 1 n n pq n Ma ann . Therefore, . 11 nn nn pq p aaMa q a Since 313233 lim limlim0, nn n nn n aaa 0. so lim n na Note also that 1n n a 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 [2], 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 21 1 nM aa Mn M 1 a Then 11 1 n. nMa Ma 11 1 211 1 . nn nn naM ana aaMaa Notice that 11Mn MnnM1 11.nn a, and so aa Now let b, c > 0, and consider 1 lim x b ucx d . Taking natural logarithms of both sides yiel d s ln ln 1 ln limlnlim xx bcxd b uxcxd x , and ap- plying L’Hopital’s Rule we obtain ln lim0 1 c cx d x u , and so u = 1. Consequently we see that for any > 0, we can always find an integer N such that n > N 1 11. 1 n Ma MnM Copyright © 2011 SciRes. APM  J. D. STEIN JR. ET AL.303 We use this to construct a series of decreasing 1n n 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 1 11 1 1 2 n Ma MnM and 1 1 1 Ma MnM . Let 11 1 21 1 NMa bb NM . Having defined 1p N b, let 1b1 1p N ab and choose an integer 1 p NN such that 1p nN 1 11 1 1 2 n Ma MnMp and 11 1 Ma MnM . Let 21 1 1 1 1 pp NN p Ma bb . NM As constructed, the sequence satisfies the :1,2, n bn hypotheses of the theorem, and so converges. 1n n b However, by construction we also have limsup 1 nn n , and so the Root Test is inconclusive for this series. b b 6. 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] 1n n b 1n a n 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. 1n n a Proof: We can assume WLOG that N = 1. If an in- teger p sup {q: C[p, q] }= +, then converges 1n n a because if C[p, qk] for q1 < q2 < ···, then the partial sums 1 k q j a 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 22 jj nn jj nn kkj jjkjkj j aabb j b since each k appears in a maximum of two [ j, j]. So the partial sums of 1 j a form a bounded monotone se- quence, and so 1 j a converges. The second application uses Theorem 3.1 to obtain a different version of the Banach Contraction Principle. As mentioned earlier, [1] 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 ,, nn dTxTydTxTyMdxy , , nn Ty ,dxy dTx . 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. 2 Tx x Proof: Note first that . We assume WLOG 2 Tx x4 Copyright © 2011 SciRes. APM  J. D. STEIN JR. ET AL. Copyright © 2011 SciRes. APM 304 22 ,, 1. dTxTydxyyxy x yxyx yx yx yx that y in the rest of the proof. 22 , ,, dTxTyyxyxy x dxyy xdxy , since . 1xy Note that 22 , , dTxTyyx yx dxyy x 1 1 ,. . Since y and x So the question of the existence of M reduces, on divi- sion by x , to whether it is possible to find M with 0M1 and 22 11yx yxMyx . The constant M = 0.8 satisfies this inequality, because 1 x and 22 0.5 x 0.8 1yx . So 22 1yxy 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 22 x Ty ,dT Mdxy The 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 4422 22 22 ,, 1 dydTxTyyx y x yxyxyx yxyx yx yxyx 2 Tx T [1] 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 [2] W. Rudin, “Principles of Mathematical Analysis,” McGraw-Hill, New York, 1964.
|
