Tricky induction proof: pile of stones split into n groups So I understand setting up this proof and the basis step just fine, however, it is the induction step where I am completely lost. I went and asked the math tutors at my school, the the tutor that spoke with me even had a tough time with this problem... it is supposed to be tricky, any help would be appreciated, thank you!
Suppose you begin with a pile of n stones (n ≥ 2) 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 p and q stones
in them, respectively, you compute pq. Show that no matter how you split the piles (eventually into n
piles of one stone each), the sum of the products computed at each step equals n(n − 1)/2. (Hint: use
strong induction on n.)
My attempt at this question makes no sense, and I just couldn't make sense of the tutors words in the time I had with her. Again, any help would be much appreciated!
 A: I am sure your instructor will want an algebraic proof, so don't turn this in as your proof, but here's a 'Proof by Picture' for the inductive step:

Explanation:
The claim is that $n$ stones you will eventually end up with $\frac{n(n-1)}{2}$ stones, which is the sum of all numbers $1$ through $n-1$ ... which is the number of little squares in the figure above.
Now, if you divide your pile into two piles of $k$ and $n-k$, you gain $k(n-k)$ points (the number of blue squares), plus whatever points you can get by dividing the pile with $k$ stones and the pile with $n-k$ stones. By inductive hypothesis, however, the $k$ stones will give you the sum of $1$ through $k-1$ (the white squares above the blue squares), and the $n-k$ stones will give you the sum of $1$ through $n-k-1$ (the white squares to the right of the blue squares), and so we see that indeed this all adds up to $\frac{n(n-1)}{2}$
A: At the first step you have piles of size $a$ and $n-a$, and write down the product $a(n-a)$.  Now you will handle the pile of size $a$; by the strong inductive hypothesis the sum of all the products you write down (as you break this sub-pile down all the way) will be $\frac{a(a-1)}{2}$.  Next, you handle the pile of size $n-a$; by the strong inductive hypothesis the sum of all the products you write down will be $\frac{(n-a)(n-a-1)}{2}$.  The total will be
$$a(n-a)+\frac{a(a-1)}{2}+\frac{(n-a)(n-a-1)}{2}$$
Adding these and simplifying yields $\frac{n(n-1)}{2}$.
The only thing left is the base case of $n=1$, where there is nothing to do, and you write down nothing.  This equals $\frac{1(0)}{2}$, so all is well.
A: You could start by trying some small examples to make sure you understand what is going on.  If you start with $n=2$ stones the only thing you can do is split into $1+1$.  Multiplying those gives $1=\frac 12\cdot 2 (2-1)$.  If you start with $n=3$ you can split into $2+1$ with product $2$, then split the $2$ with product (we just found) $1$, for a sum of $3=\frac 12\cdot 3(3-1)$.  If you split $4$ into $2+2$ with product $4$ you get two more $1$s from splitting the $2$s for a total of $6$.  Similarly if you split $4$ into $3+1$ with product $3$ you get $3$ more from splitting the $3$ for a total $6$ again.  It clearly works for small numbers.  
Now we proceed by strong induction.  We assume that splitting any number $n$ up to and including $k$ is known to give a total of $\frac 12n(n-1)$ no matter how we split it.  We want to prove that splitting $k+1$ will give a total of $\frac 12(k+1)k$.  We split $k+1$ into $p$ and $k+1-p$, which contributes $p(k+1-p)$ to our sum.  Splitting $p$ will give $\frac 12p(p-1)$ and splitting $k+1-p$ will give $\frac 12(k+1-p)(k-p)$  The grand total will then be 
$$p(k+1-p)+\frac 12p(p-1)+\frac 12(k+1-p)(k-p)\\
=pk+p-p^2+\frac 12(p^2-p+k^2+k-2pk-p+p^2)\\
=\frac 12(k^2+k)\\=\frac 12(k+1)k$$
as desired.  
A combinatorial proof of the formula is to imagine a complete graph linking the stones in each pile.  Each time you split a pile you break the number of edges in the product.  You start with $\frac 12n(n-1)$ edges and finish with none.  This justifies the formula without induction.
A: 
Use the strong inductive hypothesis that a heap of size $m$ will give a contribution of $\frac{m(m-1)}{2}$ for $m<n$. Then prove it for $n$ by verifing that
\begin{eqnarray*}
\color{red}{\frac{(n-k)(n-k-1)}{2}}+\color{blue}{\frac{k(k-1)}{2}} +(n-k)k=\frac{n(n-1)}{2}.
\end{eqnarray*}
