Discrete Math: Strong Induction

[phoenixwhiterose]

Suppose you begin with a pile of n stones and split this pile into n piles 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-1)/2.

Please, I would appreciate any help. I'm pretty sure strong induction is the right way to go, but I don't know how.

 

[marcmtlca]

Assume true for all \(\displaystyle n \le k\).

Now suppose you have k+1 stones. You split them into 2 groups of s and k + 1 - s. The product at the first splitting is \(\displaystyle sk\, +\, s\, -\, s^2\)

Now, we have two smaller groups that we are splitting. We apply the induction hypothesis to conclude that the remaining products sum to:

. . .\(\displaystyle \frac{(k\, +\, 1\, -\, s)(k\, +\, 2\, -\, s)}{2}\, +\, \frac{s(s\, +\, 1)}{2}\)

Our total sum is then:

. . .\(\displaystyle \frac{(k\, +\, 1\, -\, s)(k\, +\, 2\, -\, s)}{2}\, +\, \frac{s(s\, +\, 1)}{2}\, +\, sk\, +\, s\, -\, s^2\)

This can be simplified to:

. . .\(\displaystyle \frac{k^2\, +\, 2k\, -\, sk\, +\, k\, +\, 2\, -\, s\, -\, sk\, -\, 2s\, +\, s^2\, +\, s^2\, +\, s}{2}\, +\, sk\, +\, s\, -\, s^2\)

Some things here cancel and we are left with:

. . .\(\displaystyle \frac{k^2}{2}\, +\, \frac{3k}{2}\, +\, \frac{2}{2}\)

What is left is to show that this is \(\displaystyle \frac{(k\, +\, 1)(k\, +\, 2)}{2}\)