Advanced book on Mathematics Olympiad

Number Theory 681

and, according to Hermite’s identity,

Sn−Sn− 1 =

⌊

n

x

n

⌋

=x.

BecauseS 1 =x, it follows thatSn=nxfor alln≥1.
(S. Savchev, T. Andreescu,Mathematical Miniatures, MAA, 2002)

716.Setk=

√

n. We want to prove that

k=

⌊

√

n+

1

√

n+

√

n+ 2

⌋

,

which amounts to proving the double inequality

k≤

√

n+

1

√

n+

√

n+ 2

<k+ 1.

The inequality on the left is obvious. For the other, note thatk≤

√

n<k+1, which
impliesk^2 ≤n≤(k+ 1 )^2 −1. Using this we can write

√

n+

1

√

n+

√

n+ 2

=

√

n+

√

n+ 2 −

√

n

2

=

√

n+ 2 +

√

n

2

≤

√

(k+ 1 )^2 + 1 +

√

(k+ 1 )^2 − 1

2

<k+ 1.

The last inequality in this sequence needs to be explained. Rewriting it as

1

2

√

(k+ 1 )^2 + 1 +

1

2

√

(k+ 1 )^2 − 1 <

√

(k+ 1 )^2 ,

we recognize Jensen’s inequality for the (strictly) concave functionf(x)=

√

x. This
completes the solution.
(Gh. Eckstein)

717.We apply the identity proved in the introduction to the functionf:[ 1 ,n]→[ 1 ,

√

n],
f(x)=

√

x. Becausen(Gf)=

√

n, the identity reads

∑n

k= 1



√

k+

∑√n

k= 1

k^2 −

√

n=n

√

n.

Hence the desired formula is

∑n

k= 1



√

k=(n+ 1 )a−

a(a+ 1 )( 2 a+ 1 )

6

.