Suppose you begin with a pile of n stones and split this pil

Suppose you begin with a pile of n stones and split this pile into n piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile you multiply the number of stones in each of the two smaller piles you form, so that if these piles have r and s stones in them, respectively, you compute rs. Show that no matter how you split the piles, the sum of the products computed at each step equals n(n - l)/2.

Solution

Let’s Prove Using Induction:-

Case-1:-

If you have two stones, you have to split into two piles of size 1.
1 * 1 = 1. n(n-1)/2 = 2(2-1)/2 = 2*1/2 = 2/2 = 1. Which is True!!

Case-2:-

Assume it to be true for n = k.

Case-3:-

Now we need to Show, it to be true for n + 1.

When you split the pile of size n+1, you split this into 2 piles of size r and s where r+s= n+1
Thus, your first product is rs.

By assumption, the pile of size r, when broken up, will yield a product of
r(r-1)/2 and the pile of size s will yield a pile of size (s)(s-1)/2

Adding the three yields:-

rs + r(r 1)/2 + s(s 1)/2 = (2rs + r^2 r + s^2 s)/ 2 = (r + s)(r + s 1)/2= n(n+1)/2

which is what we were supposed to prove to prove.

Hence sum of the products computed at each step would be n(n-1)/2