j'essaie de prouver ce qui suit par induction:Preuve par induction de la somme des hauteurs des noeuds dans un arbre binaire complet
sum(k*2^(H-k), k = 0 .. H) = N-H-1
il est un problème pour une classe d'algorithmes. Je pensais pouvoir faire ce que je fais normalement pour les sommations, c'est-à-dire supposer que cela fonctionne pour P (m) puis incrémenter la somme pour P (m + 1) et revenir en arrière en ajoutant du côté droit la sommation sur le côté gauche produit. Mais, ce problème est différent car la substitution de H + 1 change chaque terme à l'intérieur de la sommation ... donc je ne pense pas que cette technique fonctionnera.
Ceci est un problème de devoirs ... donc je ne m'attends évidemment pas à une solution complète. Mais, je ne suis pas vraiment sûr de savoir où prendre la somme donc je cherche d'autres façons de faire l'induction.
qu'est-ce que N dans l'équation donnée? –
mon mauvais! N est le nombre de nœuds dans l'arbre (donné par l'équation N = 2^(H + 1) -1). H est la hauteur de l'arbre (en supposant qu'un arbre qui est juste la racine est la hauteur 0. –