Start with 100. Sum = 0.- Split it into two parts: x and 100-x, multiply them and add to sum. - Now split x into 2 parts; y and x-y, multiply it and add to sum. Do the same to 100-x, i.e. multiply (100-x-z) and z, and add it to sum.- Keep on doing this till you get 1 at the end of each node.Prove that the sum that you get is independent of the way you split. What is the sum ?

Here is a boring solution. Let S(n) be the sum you get starting from n. We claim that S(n)=n(n-1)/2. Proof is by induction: S(2)=1 is obvious and for any larger n and 0<m<n, S(n)=m(n-m)+S(m)+S(n-m) if we break n into m and n-m on the first step. But a simple calculation shows that the right hand side is actually independent of m, so we are done.There should be a more elegant solution, hope someone finds it.

You are right; proofs by induction are sometimes boring. But if they are that short, it is hard to find a more elegant proof. For the present problem one can try a "proof without words". Here is the idea (unfortunately given by words...):Do not imagine a tree; imagine building rectangles of 1x1 boxes, corresponding to the multiplications. For each rectangle created, build the next two (its child nodes in the tree picture) on the top and on the right. The rectangles will be getting smaller and smaller, and you will end up with a triangle of side length n, consisting of n(n-1)/2 1x1 boxes.

Nice solution cm! Here is another, more combinatorial argument: Let C(n) be the number of ways of choosing 2 things out of a set of n. Of course, C(n)=n(n-1)/2. But we can also calculate C(n) thusly: partition the set into two subsets, say A and B, of sizes m and n-m resp. Then we can pick 2 elements in 3 different ways: both from A, both from B or one from A and one from B. This gives C(n)=C(m)+C(n-m)+m(n-m). Same recursive relation as earlier, same initial condition, so we must have the same solution! Ergo, sum=C(n)=n(n-1)/2.