Separating a pile of n stones 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 generate a number that is the result of multiplying the number of stones in each of the two smaller piles you form.
For example, if these piles have r and s stones in them, respectively, you compute r⋅s.
For example, you may start with 4 rocks then separate them into one pile of one and one pile of three rocks; this three rock pile is then separated into one pile of one and one pile of two where the pile of two is then separated.
This sum is 3⋅1+2⋅1+1⋅1=6.
Show that no matter how you split the piles, the sum of these products from every split of n rocks to n piles of one rock always equals n(n−1)/2.
Work:
So I wrote it out as n+n-1+n-2+…+r*s=n(n−1)/2
and broke it down into LHS and RHS where;
LHS:
??
RHS:
k:
k(k-1)/2
K+1:
k+1(k)/2
=(k^2+k)/2
How do I determine what to calculate on LHS and is the purpose to make it equal to RHS?
I've looked at links below but don't understand their method of interpreting and solving.
Pile splitting problem (Proof by induction)
Use induction.
If splitting $k \le n$ rocks always gives you $a_k=\frac {k(k-1)}2$ then
splitting $n+1$ rocks into $r$ and $s$ piles where $r+s = n+1$ will give you $a_r + a_s = r*s + \frac {r(r-1)}2 + \frac {s(s-1)}2=$
$\frac {2rs + r^2 - r + s^2 - x}2=$
Replace $s$ with $n+1 - r$ and you have
$\frac {2r(n+1-r) + r^2 - r +([n+1]-r)^2 - (n+1-r)}2=$
$\frac {2r(n+1)-2r^2 + r^2 - r +[n+1]^2-2r[n+1] + r^2 - [n+1]+r)}2=$
$\frac {[n+1]^2 - [n+1])}2=$
$\frac {(n+1)([n+1]-1)}2$.
So induction steps works.
Just need to show in works for $n = 1,2$.
If you start with $1$ you can't split them so you have $0$ and $0 = \frac {1(1-1)}2$.
And for $n= 2$ you can only split to $1$ and $1$ and $1*1 =1$. And $1 = \frac {2(2-1)}2$.