16

GENERALIZATIONS OF THE PERRON-FROBENIUS THEOREM

such that fovjkfi equation (3.22) holds. Since

k k

1 y^fi

+

Sfc+1

_ y^ H-ih ~ a ,

sfc+i

k k

3 = 1

J

3 = \

J

^

=

1 _ It. +

g/c+1

Tk rk+i'

it follows that Sk+i lk+ilk So we can choose 7^+1 0 such that s/e+i =

7 ^ + 1 — 7^+1 and this proves (3.22). Recall also that for j = 1, 2,... , //

r^s for every s € Sj.

With this information we can use rule B to prove that lcm(S') € P(n).

Define integers q^ 1 i /i, by

o7 = 1cm (lcm(5M _i+i),lcm(SM_i+2),... ,lcm(5A,)J.

We shall use rule B to prove that there exist integers

qJ

i+1, 1 j 7/x-i, such

that & = lcm(^_

i + 1

,.. . , ^ + 1 ) and

r„-«l«Ui and ^ ± l

e P

( [ J L ] )

for 1 j 7M_i and 1 i fi. Here [x] denotes the largest integer less than or

equal to x. In particular, this implies that lcm(S') = q^ G P(ri).

For i = 1, we have #i = lcm(S^). Since

|#MI = 5M 7M_i/M,

we can divide S^ into 7^-1 disjoint sets of size at most l^. So

By definition, for every s G 5M7-, 1 j 7^-1,

r , |

S

a n d A

e P

(

[

^

]

)

So an application of rule B yields

-i-lcm(S

w

. ) = *

M

lcm(ls,, ) € ^ f l ) C P ( [ -

! L

- ] ) , 1 J 7„-i-

' / L I — 1 ' £ 4

X

' H '

X

' / L i — 1

7

(Here for a set i? = {61,62,... , 6S}, /c£? = {/c6i, ^62,... , fc6s}.)

If we define

q^ = lcm(S,Mi) for 1 j 7 ^ 1 ,

we have proved the claim for i = 1.

Assume next that the claim holds for i = k. So there exist integers q^_fc+15

1 j 7/u-fc, such that

^ - l c m ( ^ _ ,

+ 1

, . . . , ^

+ 1

) ,