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!

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}$
