Page 34 - MATINF Nr. 7
P. 34
34 C. B˘alc˘au
deci
v(n) = r − 1 = dlog (n + 2)e − 1,
2
ceea ce ˆıncheie demonstrat , ia prin induct , ie a relat , iei (6).
Din (4) s , i (6) rezult˘a c˘a
−
−
N (n + 1) − N (n) = dlog (n + 2)e − 1, ∀n ∈ N.
2
Aplicˆand succesiv aceast˘a relat , ie avem
−
−
N (n) = N (n − 1) + dlog (n + 1)e − 1
2
−
= N (n − 2) + dlog ne + dlog (n + 1)e − 2
2 2
. . .
−
= N (0) + dlog 2e + dlog 3e + . . . + dlog (n + 1)e − n.
2 2 2
−
Cum N (0) = 0 obt , inem c˘a
−
N (n) = dlog 1e + dlog 2e + . . . + dlog (n + 1)e − n, ∀n ∈ N. (7)
2
2
2
Dar
n+1
X
dlog ie = (n + 1)dlog (n + 1)e − 2 dlog (n+1)e + 1
2
2
2
i=1
(a se vedea demonstrat , ia Teoremei 1 din [4]), deci
−
N (n) = (n + 1)dlog (n + 1)e − 2 dlog (n+1)e − (n − 1), ∀n ∈ N. (8)
2
2
Demonstr˘am c˘a
−
N(n) ≥ N (n), ∀ n ∈ N (9)
prin induct , ie.
−
Pentru n ∈ {0, 1} avem N(n) = N (n) = 0.
Presupunem inegalitatea adev˘arat˘a pentru orice i ∈ {0, 1, . . . , n−1} s , i o demonstr˘am pentru
ˆ
n (n ≥ 2). Intr-adev˘ar, folosind relat , iile de recurent , ˘a (1) s , i (3) s , i ipoteza de induct , ie pentru
k − 1 s , i n − k avem
¡ ¤
−
N(n) − N (n) = N(k − 1) + N(n − k) − N − n − 1 − N − n − 1
2 2
≥ ϕ(k), (10)
unde ¡ ¤
−
−
ϕ(k) = N (k − 1) + N (n − k) − N − n − 1 − N − n − 1 .
2 2
Deoarece ϕ(k) = ϕ(n + 1 − k), rezult˘a c˘a putem presupune c˘a avem k ≤ n + 1 − k, adic˘a
n − 1
k ≤ + 1
2
§ ª
n − 1
0
0
0
(ˆın caz contrar, notˆand k = n + 1 − k obt , inem ϕ(k) = ϕ(k ) s , i k ∈ 1, 2, . . . , + 1 ).
2
