Proof that when repeatedly splitting a heap of marbles into two and writing down the product of the two heap sizes, the total is ${x \choose 2}$

Question

Here is the problem in full:

A heap has $x$ marbles, where $x$ is a positive integer. The following process is repeated until the heap is broken down into single marbles: choose a heap with more than 1 marble and form two non-empty heaps from it. One will contain $n$ marbles and the other $m$ marbles. Each time this is done, record the product $nm$. Use induction to show the sum of your recorded products is $\binom{x}{2}$ no matter what the sequence of dividing the heap is.

So, using induction: We assume truth when there are $k$ marbles, where $k$ is a positive integer. We test the basis case $k = 1$, which is a one marble pile. $\binom{1}{2} = 0$, and splitting into a pile with 1 marble and a pile with 0 marbles also gives a product of 0, so the basis case is true. Next we demonstrate truth when $x=k+1$. We begin by making a pile of size 1 and a pile of size $k$. The product that we get from this split is $k$. The induction hypothesis says $k$ marbles ends up with a result of $\binom{k}{2}$. I can't prove it just yet (I need help here too) but I know $k + \binom{k}{2} = \binom{k+1}{2}$. Therefore the proof is shown.

Now, I need help here. I don't think this is right because of the part, "no matter what the sequence of dividing the heap is." I think I violated this when I make a pile of size 1 specifically during the induction step. Could strong induction somehow help me here? I just can't really see how.

Additionally, if anyone could point me to a proof for $k + \binom{k}{2} = \binom{k+1}{2}$ I would really appreciate being able to understand this one from an analytic standpoint too.

Thanks.

Answer 1

Let’s dispose of the technical point first. By straight algebra,

$$k+\binom{k}2=k+\frac{k(k-1)}2=\frac{2k+k^2-k}2=\frac{k(k+1)}2=\binom{k+1}2\;.$$

Alternatively,

$$k+\binom{k}2=\binom{k}1+\binom{k}2=\binom{k+1}2$$

by the Pascal’s triangle identity.

You’re quite right that it’s not sufficient to consider splitting your $k+1$ pile into piles of size $1$ and $k$. In fact, you want to use what’s often called strong induction: suppose that the result is true for piles of size less than $k$, and show that it’s then necessarily true for piles of size $k$. Now you split your pile of size $k$ into piles of sizes $m$ and $n$, where $m,n\ge 1$ and $m+n=k$, and your induction hypothesis tells you that the pile of size $m$ will contribute a total of $\binom{m}2$, while the pile of size $n$ will contribute a total of $\binom{n}2=\binom{k-m}2$. In addition, of course, this split will contribute $mn$. Thus, you’ll end up with

$$\binom{m}2+\binom{k-m}2+m(k-m)\;.$$

Now do some algebra, more or less along the lines of what I did at the top.

Answer 2

Hint: We give a part-solution, to give you an opportunity to do some of the details.

Yes, it is by strong induction.

Suppose that $x=m+n$, and we break the pile of $x$ into parts of size $m$ and $n$.

Then we write down $mn$, and proceed to break up the $m$-pile and the $n$-pile. By the induction hypothesis, the sum of the numbers we write down when breaking down the $m$-pile is $\binom{m}{2}$, and the sum for the $n$-pile is $\binom{n}{2}$. Thus the total sum is $$mn+\binom{m}{2}+\binom{n}{2}.$$ We need to check that this is $\binom{x}{2}$, that is, $\binom{m+n}{2}$. So we need to show that $$mn+\binom{m}{2}+\binom{n}{2}=\binom{m+n}{2}.\tag{1}$$ The left-hand side of (1) is $$mn+\frac{m(m-1)}{2}+\frac{n(n-1)}{2}.$$ Bring to a common denominator $2$ and simplify. We get $$\frac{m^2+2mn+n^2-m-n}{2}.\tag{2}$$ Now you can work with the right-hand side of (1) and show that it is equal to (2).

Remark: One probably should start the induction at $x=2$. Starting at $x=1$ involves the concept of an empty product, which by definition is $1$, and not the $0$ of your post.

Answer 3

this has a computation-lite intuitive solution. think of the marbles as a squadron of $K$ tiny space-craft. suppose craft belonging to the same pile can communicate by walkie-talkie, but if any two are separated a long-range communications link is set up between them.

so when a pile of $m+n$ craft is split into two piles of $m$ and $n$ respectively, this requires $mn$ new long-range communications links to be set up. by the stage when each craft occupies its own pile, all possible 2-way communication links will have been set up, numbering $\binom{K}{2}$