[Math] Making sense of word problem

algorithmsinduction

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, by strong induction, that no matter how you split the
piles, the sum of the products computed at each step equals
$n(n-1)/2$.

I'm not sure how to make sense of this question. Am I supposed to prove that $\Sigma rs = n(n-1)/2$? What of instances where $n \% 2 = 1$? I can't split 3 stones into piles $r$ and $s$ of equal size.

PS: I don't want the answer, I just can't comprehend how to begin.

Best Answer

The Strong Induction you use will probably be on $n$, the number of stones you start with.

You will be assuming that the statement is true for all values of $n$ less than, let's say, $m+1$. This means when you have $k$ stones so that $1 \leq k \leq m$ the sum of the $rs$ values, for all of the split piles, is $\frac{k(k-1)}{2}$.

Then you should be able to prove that the sum of the $rs$ values when you start with $m+1$ stones is $$\displaystyle\sum rs = \frac{(m+1)(m+2)}{2}$$

Good luck!

Related Question