Minimize cost of recursive pairwise sums: how to prove the greedy solution works?

The problem is in this other question.

Why does this always work? It's not clear to me how one would use induction.

For $$n = 3$$, a quick calculation shows it works, however, I don't think it generalizes well.

• Please make your questions self-contained. – orlp Aug 11 at 2:51

Each summing approach can be represented by a binary tree: the leaves represent the original elements and each internal node (including the root) represents the result element of the addition of the elements represented by its two children. For example,

Input: [1, 5, 3, 7]
Adding 1 and 3 together (Cost 1+3 = 4)
State: [5, 7, 4]
Adding 4 and 5 together (Cost 4+5 = 9)
State: [7, 9]
Adding 7 and 9 together (Cost 7+9 = 16)
State: 

Total cost: 4 + 9 + 16 = 29

... can be regarded as the following tree:

16
/  \
9    \
/ \    \
4   \    \
/ \   \    \
1   3   5    7

Then we rewrite the cost of each addition as the sum of original elements. For example, the costs in the example above are:

4 = 1+3
9 = 4+5 = 1+3+5
16 = 7+9 = 1+3+5+7

Total cost: 4 + 9 + 16 = 29

We can see each number corresponding to a leaf is contributed to the total cost in the additions corresponding to its ascendants. For a leaf $$e$$, If we denote by $$h(e)$$ the height of $$e$$, and by $$f(e)$$ the number corresponding to $$e$$, then the total cost is exactly $$\sum_{e\ :\ \text{leaves}}f(e)\cdot h(e)$$.

Note each tree represents a prefix code of the leaves. In the example above, the tree represents the prefix code:

1: 000
3: 001
5: 01
7: 1

If we regard $$f(e)$$ as the frequency of $$e$$, then $$\sum_{e\ :\ \text{leaves}}f(e)\cdot h(e)$$ is the average length of the code, which is optimized by Huffman coding. Note the answer in your link describes exactly how Huffman coding works.