4
5) On s'intéresse maintenant à un arbre complet de hauteur h quelconque (h est un entier
strictement positif), C'est-à-dire un arbre dans lequel chaque nœud a exactement 2 fils.
a) On appelle (un) la suite dans laquelle un contient le nombre de nœuds se trouvant à
la hauteur n, donc uo = 1 par exemple. Déterminer la relation de récurrence liant deux
termes successifs de cette suite
b) En déduire l'expression de un en fonction de n, et donner alors le nombre total de
feuilles d'un arbre de hauteur h
c) En utilisant l'expression explicite de un. donner l'expression de S en fonction de h.
S étant la taille d'un arbre complet de hauteur h ?