solution ENS, meilleure que la mienne, mais moins intuitive.

1: on montre que dans l'arbre d'un code optimal, les 2 lettres les moins fréquentes seront automatiquement "tout en bas" et dépendantes du même noeud.
preuve assez facile, si c'est pas le cas, on fait l'échange de position et on montre qu'il y a un gain net en taille

2: on montre que si un arbre correspond à un code optimal pour un alphabet à n lettres, alors en changeant les 2 lettres les moins courantes (en bas, donc) en une seule, de fréquence somme (x de fréquence fx, y de fréquence fy, devient "x ou y" de fréquence fx+fy), on obtient un arbre (pour l'alphabet de (n-1) lettres) correspondant à un code optimal. bref, on passe de opt(n) à opt(n-1) en coupant 2 feuilles**

concernant la fameuse somme "fréquence*taille de lettre", la différence entre les 2 arbres (ou code, c pareil) est fx+fy

3:on montre le résultat par recurrence sur la taille de l'alphabet
---alphabet de taille 1: évident

---si c'est vrai pour la taille n-1
on prend l'arbre de huffman et un arbre optimal pour n
on remonte d'une lettre par le procédé ci dessus
on voit que la différence dans notre super somme est à chaque fois fx+fy

or, pour un alphabet n-1, hufman est optimal, donc les sommes sont égales à n-1. comme la différence entre n et n-1 est la même pour Huffman et l'arbre optimal, donc au rang n, les sommes sont aussi les memes
Huff (n) = Huff (n-1) + fx + fy
Huff(n-1) = opt(n-1)
Opt(n) = opt(n-1) + fx + fy

donc Huff (n) = Opt (n), CQFD

**
dans l'arbre, ça revient à changer ce noeud à 2 fils-feuilles par une feuille:

|--x
-|
|--y

devient

-(x ou y)