Page 20 - REVISTA MATINF Nr. 5

20 C. B˘alc˘au

deci
f(n) = k − 1 + 1 = k = dlog (n + 1)e,
2
ceea ce ˆıncheie demonstrat , ia prin induct , ie a relat , iei (9).
Din (7) s , i (9) rezult˘a c˘a

+
+
∗
N (n + 1) − N (n) = dlog (n + 1)e, ∀n ∈ N .
c
c
2
Aplicˆand succesiv aceast˘a relat , ie avem
+
+
N (n) = N (n − 1) + dlog ne
c c 2
+
= N (n − 2) + dlog (n − 1)e + dlog ne
2
c
2
. . .
+
= N (1) + dlog 2e + dlog 3e + . . . + dlog ne.
c 2 2 2
+
Cum N (1) = 0, obt , inem c˘a
c
∗
+
N (n) = dlog 1e + dlog 2e + . . . + dlog ne, ∀n ∈ N . (10)
2
2
c
2
Dar
n
X dlog ne ∗
dlog ie = ndlog ne − 2 2 + 1, ∀n ∈ N .
2
2
i=1
ˆ 2
Intr-adev˘ar, egalitatea este evident valabil˘a pentru n = 1, iar pentru n ≥ 2 notˆand s = dlog ne
∗
s
avem s ∈ N s , i s − 1 < log n ≤ s, deci 2 s−1 < n ≤ 2 , iar pentru orice i ∈ {2, 3, . . . , n} avem
2
echivalent , ele
j
j
dlog ie = j ⇔ j − 1 < log i ≤ j ⇔ 2 j−1 < i ≤ 2 ⇔ 2 j−1 + 1 ≤ i ≤ 2 ;
2 2
astfel avem
n n s−1 2 j n
X X X X X
dlog ie = dlog ie = dlog ie + dlog ie
2
2
2
2
i=1 i=2 j=1 i=2 j−1 +1 i=2 s−1 +1
s−1 2 j n s−1
X X X X
j
= j + s = j(2 − 2 j−1 ) + s(n − 2 s−1 )
j=1 i=2 j−1 +1 i=2 s−1 +1 j=1
s−1
X
s
= j · 2 j−1 + s(n − 2 s−1 ) = s · 2 s−1 − 2 + 1 + s(n − 2 s−1 )
j=1
s
= ns − 2 + 1 = ndlog ne − 2 dlog ne + 1.
2
2
Rezult˘a c˘a
n
X
+
∗
N (n) = dlog ie = ndlog ne − 2 dlog ne + 1, ∀n ∈ N .
2
2
2
c
i=1
Dar
log n ≤ dlog ne < log n + 1,
2 2 2
deci
n ≤ 2 dlog ne < 2n.
2