Advanced book on Mathematics Olympiad

5.1 Integer-Valued Sequences and Functions 251

Our second example is a general identity discovered by the second author and D. An-
drica. Note the similarity with Young’s inequality for integrals (problem 480).

Theorem.Leta<bandc<dbe positive real numbers and letf:[a, b]→[c, d]be
a continuous, bijective, and increasing function. Then
∑

a≤k≤b

f(k)+

∑

c≤k≤d

f−^1 (k)−n(Gf)=bd−α(a)α(c),

wherekis an integer,n(Gf)is the number of points with nonnegative integer coordinates
on the graph off, andα:R→Zis defined by

α(x)=

⎧

⎪⎨

⎪⎩

x ifx∈R\Z,

0 ifx= 0 ,

x− 1 ifx∈Z\{ 0 }.

Proof.The proof is by counting. For a regionMof the plane, we denote byn(M)the
number of points with nonnegative integer coordinates inM. For our theorem, consider
the sets

M 1 ={(x, y)∈R^2 |a≤x≤b, 0 ≤y≤f(x)},

M 2 ={(x, y)∈R^2 |c≤y≤d, 0 ≤x≤f−^1 (y)},

M 3 ={(x, y)∈R^2 | 0 <x≤b, 0 <y≤d},

M 4 ={(x, y)∈R^2 | 0 <x<a, 0 <y<c}.

Then

n(M 1 )=

∑

a≤k≤b

f(k), n(M 2 )=

∑

c≤k≤d

f−^1 (k),

n(M 3 )=bd, n(M 4 )=α(a)α(c).

By the inclusion–exclusion principle,

n(M 1 ∪M 2 )=n(M 1 )+n(M 2 )−n(M 1 ∩M 2 ).

Note thatn(M 1 ∩M 2 )=n(Gf)andN(M 1 ∪M 2 )=n(M 3 )−n(M 4 ). The identity
follows. 

714.For a positive integernand a real numberx, prove the identity

x+

⌊

x+

1

n

⌋

+···+

⌊

x+

n− 1

n

⌋

=nx.