326
7 Arbres digitaux
Posons H (n) = =2 log 2 n. Nous partageons la somme (7.37) en trois en considérant
les intervalles d’entiers
I 1 = [1 . . H (n) − −log 2 log n
I 2 =]H (n) − −log 2 log n . . H (n) + +log 2 log n
I 3 = [H (n) + +log 2 log n . . ∞],
et nous considérons les sommes pour j ∈ {1, 2, 3}
S j =
k∈I j
1 − q n,k
.
(i) Nous évaluons
S 1 = H (n) − −log 2 log n −
k∈I 1
q n,k ,
et puisque la suite (q n,k ) n,k est croissante selon k, et posant
k 1 = H (n) − −log 2 log n = max(I 1 ),
nous obtenons
|S 1 − H (n) + +log 2 log n ≤ k 1 q n,k 1 .
D’après l’expression
q n,k =
n−1
j =0
1 −
j
2 k
,
puisque pour 0 ≤ x < 1, log(1 − x) ≤ −x, nous avons pour n ≤ 2 k
log q n,k ≤ −
n−1
j =1
j
2 k = −
n(n − 1)
2 k
.
(7.38)
Utilisant l’encadrement de k 1 , log 2 n ≤ k 1 ≤ 2 log 2 n − log 2 log n, nous
obtenons n ≤ 2 k 1 ≤
n 2
log n et
log q n,k 1 ≤ − log n + 1.