Page 36 - MATINF Nr. 7

36 C. B˘alc˘au

pentru orice k ∈ {1, 2, . . . , n}, deci


0, dac˘a n ∈ {0, 1},


n

P
N med (n) = (N med (k − 1) + N med (n − k) + n − 1)
 k=1

 , dac˘a n ≥ 2.
n
Pentru orice n ≥ 2 avem
n n
P P
N med (k − 1) + N med (n − k) + n(n − 1)
k=1 k=1
N med (n) =
n
n
P
2 N med (k − 1) + n(n − 1)
= k=1 ,
n
deci num˘arul mediu de comparat , ii de chei verific˘a relat , ia de recurent , ˘a

0, dac˘a n ∈ {0, 1},


 n
P
N med (n) = 2 N med (k − 1) + n(n − 1)
k=1

 , dac˘a n ≥ 2.

n
Formula dat˘a de a doua ramur˘a este valabil˘a s , i pentru n = 1. Pentru n ≥ 2 avem
n
X 2
nN med (n) = 2 N med (k − 1) + n − n,
k=1
n−1
X
2
(n − 1)N med (n − 1) = 2 N med (k − 1) + (n − 1) − (n − 1),
k=1
deci prin sc˘adere obt , inem
nN med (n) − (n − 1)N med (n − 1) = 2N med (n − 1) + 2n − 2,

adic˘a

nN med (n) = (n + 1)N med (n − 1) + 2n − 2.
Aceast˘a egalitate poate fi rescris˘a sub forma

n(N med (n) − 2) = (n + 1)(N med (n − 1) − 2) + 2n.

ˆ
Imp˘art , ind prin n(n + 1) obt , inem
N med (n) − 2 N med (n − 1) − 2 2
= + .
n + 1 n n + 1
Aplicˆand succesiv aceast˘a relat , ie avem
N med (n) − 2 N med (n − 1) − 2 2
= +
n + 1 n n + 1
N med (n − 2) − 2 2 2
= + +
n − 1 n n + 1
. . .
N med (1) − 2 2 2 2
= + + . . . + + .
2 3 n n + 1