The cost of a class of optimal binary trees

While algorithms exist which produce optimal binary trees, there are no direct formulas for the cost of such trees. In this note, we give a formula for the cost of the optimal binary tree built on m nodes with weights 1, 2, 3,..., m. The simplicity of this proof suggests that one can try to compute the cost of optimal trees for other special classes of weights.