152
4 Approche combinatoire
Posons
u k = log(2
k
− 1);
nous obtenons
S 1 =
L
k=1
u k ν k = n
L
k=1
u k
2 k −
L
k=1
1 +
n
2 k−1
−
n
2 k
u k .
(4.24)
Notons que u 1 = 0 et que u k ≤ k pour k ≥ 2. Ceci nous permet de voir que
la somme
L
k=1
u k
2 k converge vers une constante lorsque n, et donc L, tend vers
l’infini. Soit
c :=
k≥2
u k
2 k =
k≥2
log(2 k − 1)
2 k
= 0,9457553022 . . .
La somme
L
k=1
u k
2 k vaut alors c−
k>L
u k
2 k , et
k>L
u k
2 k ≤
k>L
k
2 k =
L+2
2 L =
O(log n/n), ce qui montre que
L
k=1
u k
2 k = c + O(log n/n).
Pour traiter la deuxième somme du membre droit de (4.24), nous remarquons
que 0 ≤ 1 +
n
2 k−1
−
n
2 k
≤ 2, ce qui permet de montrer que cette
somme est bornée par 2
k≤L u k , et donne une contribution asymptotiquement
négligeable pour n → +∞ : en effet,
k≤L
u k ≤
k≤L
k = O(L
2 ) = O(log
2 n).
En regroupant le tout, nous arrivons à S 1 = c n + O(log
2 n) quand n → +∞.
(ii) Tournons-nous maintenant vers S 2 : chaque nombre s p est la taille du sous-arbre
spécial enraciné au niveau p, au plus égale à 2 L−p+1 − 1, et donc
log s p ≤ log(2
L−p+1
− 1) = u L−p+1 .
Nous avons donc une majoration pour S 2 :
S 2 =
L−1
p=0
log s p ≤
L−1
p=0
u L−p+1 =
L+1
q=2
u q = O(log
2 n),
par le même raisonnement que ci-dessus, lorsque n → +∞.
En rassemblant le tout, nous obtenons la proposition suivante.