• Non ci sono risultati.

# Prove that for each positive integer n, n(n + 1) 3 ≤ n X k=1 n − k + 1 k α(k

N/A
N/A
Protected

Condividi "Prove that for each positive integer n, n(n + 1) 3 ≤ n X k=1 n − k + 1 k α(k"

Copied!
1
0
0

Testo completo

(1)

Problem 11553

(American Mathematical Monthly, Vol.118, February 2011) Proposed by Mihaly Bencze (Romania).

For a positive integer k, let α(k) be the largest odd divisor of k. Prove that for each positive integer n,

n(n + 1)

3 ≤

n

X

k=1

n − k + 1

k α(k) ≤ n(n + 3)

3 .

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

Let

S0(n) =

n

X

k=1

α(k) and S1(n) =

n

X

k=1

α(k) k . Since α(2k − 1) = 2k − 1 and α(2k) = α(k) it follows that for n ≥ 1

S0(n) =

bn/2c

X

k=1

α(2k) +

dn/2e

X

k=1

α(2k − 1) = S0(bn/2c) + dn/2e2,

and in a similar way we have that

S1(n) =

bn/2c

X

k=1

α(2k) 2k +

dn/2e

X

k=1

α(2k − 1) 2k − 1 = 1

2S1(bn/2c) + dn/2e.

Therefore

T (n) :=

n

X

k=1

n − k + 1

k α(k) = (n + 1)S1(n) − S0(n)

= T (bn/2c) + dn/2e(bn/2c + 1) −[2 | n]

2 S1(bn/2c) where [2 | n] is equal to 1 if n is even and it is 0 otherwise.

By using the recurrence for S1(n), it is easy to verify by induction that

S1(n) ≤ 2dn/2e + n + 1

3 .

Hence, since 0 ≤ S1(bn/2c) = 2(S1(n) − dn/2e) and n = bn/2c + dn/2e,

T (bn/2c) + dn/2e(bn/2c + 1) −[2 | n]

3 (bn/2c + 1) ≤ T (n) ≤ T (bn/2c) + dn/2e(bn/2c + 1).

The upper bound follows by induction by verifying that

bn/2c(bn/2c + 3) + 3dn/2e(bn/2c + 1) ≤ n(n + 3).

Similarly the lower bound follows by induction by verifying that

n(n + 1) ≤ bn/2c(bn/2c + 1) + 3dn/2e(bn/2c + 1) − [2 | n] (bn/2c + 1).



Riferimenti

Documenti correlati