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, 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,
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,tkmax :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
M
(b1bn+1).
This inequality also holds if n = 1, for then b2 < Mb1
b2 < Mb1 + b1b1 b2 < b1 + (M – 1)b1 (1 – M)
b1 < b1b2 b1 < 1
1
M
(b1b2).
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
M
(aj–1ak).
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
M
 
 , so the
partial sums of 1
j
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.
M
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
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
M
NM
 
.
Having defined 1p
N
b, let
1b1
1p
N
ab
and
choose an integer 1
p
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 .
M
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
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
j
kkj
jjkjkj j
aabb



 

j
b

since each k appears in a maximum of two [
j,
j]. So the
partial sums of 1
j
j
a
form a bounded monotone se-
quence, and so 1
j
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
x
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
y
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
y
x and 22
0.5
y
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.