310
7 Arbres digitaux
déjà exprimé L n dans l’équation (7.15) sous la forme
L n = n
k≥0
1 −
1 −
1
2 k
n−1
.
Nous commençons par approximer cette somme en montrant que lorsque n → +∞,
L n = n
k≥0
1 − e
−n/2 k
+ o(n).
(7.24)
En effet, posons
u k = 1 −
1 −
1
2 k
n
,
v k = 1 − e
−n/2 k
.
Nous avons à montrer que
k≥0 u k =
k≥0 v k + o(1). Regardons la différence
u k − v k = f (1/2 k ), avec f (x) = e −nx − (1 − x) n . Sur [0, 1/2], f (x) ≥ 0 et atteint
son maximum en un point x 0 ∼ 2/n, avec f (x 0 ) = O(1/n), lorsque n → +∞.
Cette majoration permet de traiter les premiers termes de la somme, par exemple
jusqu’à k de l’ordre de log 2 n. Nous avons
0≤k≤≤log 2 n
u k =
0≤k≤≤log 2 n
v k + O
log 2 n
n
.
Lorsque k > log 2 n, posons k = =log 2 n + p, de sorte que 1/2 k = O(1/n) et
1 −
1
2 k
n
= e
−n/2 k
e
O
n
2 2k
,
et donc
u k = v k + e
−1/2 p
O
1
n
.
Nous obtenons
k>log 2 n
u k =
k>log 2 n
v k + O
1
n
.
En rassemblant le tout, nous obtenons bien l’approximation (7.24). Dans un second
temps, nous montrons que
k≥0
1 − e
−n/2 k
= log 2 n + ψ(n) + O
e
−n
,
(7.25)