1.6. Combinatorial results 9

number ρ such that, for each positive real number c 0,

lim

x→∞

R(cx)

R(x)

=

cρ,

in which case we say that the function R is of index ρ.

One can prove that any regularly varying function of index ρ can be

written in the form

R(x) =

xρL(x),

where L is a slowly oscillating function.

A nice result concerning slowly oscillating functions is the following.

Proposition 1.9. Let L : [M, +∞) → R+, where M 0. Assume that

L ∈

C1[M,

+∞). Then

L ∈ L ⇐⇒

x

M

dt

L(t)

= (1 + o(1))

x

L(x)

(x → ∞).

(See Problem 1.12.) Various examples and applications are provided in the

problems at the end of this chapter.

1.6. Combinatorial results

Of frequent use in several arguments is the Pigeon Hole principle, which can

be stated as follows:

Proposition 1.10. (Pigeon Hole principle) Given n objects which are to

be inserted in n − 1 distinct boxes, one can always find one particular box

containing at least two of these objects.

The other frequently used combinatorial tool is the Inclusion-Exclusion

principle, which can be stated as follows:

Proposition 1.11. (Inclusion-Exclusion principle) Denoting by P (A) the

probability that an event A occurs, by P (A ∪ B) the probability that A or

B occurs and by P (A ∩ B) the probability that A and B occur, and letting

A1,A2,...,An be events, then

P (A1 ∪ A2 ∪ . . . ∪ An) =

1≤i≤n

P (Ai) −

1≤ij≤n

P (Ai ∩ Aj)

+

1≤ijk≤n

P (Ai ∩ Aj ∩ Ak) − · · · +

(−1)n+1P

(A1 ∩ A2 ∩ . . . ∩ An).