Problem: James has a pile of n stones for some positive integer n ≥ 2. At each step, he
chooses one pile of stones and splits it into two smaller piles and writes the product
of the new pile sizes on the board. He repeats this process until every pile is exactly
one stone.For example, if James has n = 12 stones, he could split that pile into a pile of size
4 and another pile of size 8. James would then write the number 4 · 8 = 32 on the
board. He then decides to split the pile of 4 stones into a pile with 1 stone and a
pile with 3 stones and writes 1 · 3 = 3 on the board. He continues this way until he
has 12 piles with one stone each.Prove that no matter how James splits the piles (starting with a single pile of n
stones), the sum of the numbers on the blackboard at the end of the procedure is
always the same.
Hint: First figure out what the formula for the final sum will be. Then prove it
using strong induction.
The formula I came up with is $n(n-1) / $2. It could be totally wrong…
My (Partial) Solution:
1) Base Case: (n=2) James has one pile of 2 stones. Suppose he takes the top-most stone and puts in one pile A, which now has size 1. He takes the remaining stone and places it into another pile B, which now has size 1. Then the product of the sizes is 1. The sum of all the products on his board is 1. Now, if he were to start again, and take the bottom stone first and put it in pile A, he has a pile of size 1, and then takes the top stone and puts it in pile B, he has a pile of size 1, and the product is 1, with sum of all products on the board is 1.
2) Inductive Hypothesis (Strong Induction): Suppose for some $k \geq 2$, $n$ stones can be split in $ 2 \leq n \leq k $ stones and $k-n$ stones.
3) Inductive Step: Consider $n=k+1$. What do I do now?
Best Answer
First, a couple of comments on how you think about, and write/present this proof.
When doing induction, it is always a good idea to get very clear on exactly what the claim is that you are trying to prove, and thus what the property is that you want to show all natural numbers have. So in this case, that would be the claim that for any number $n$: if you start with a pile of $n$ stones, then no matter how you keep splitting it, the eventual sum of products will be the same and in fact will be $\frac{n(n-1)}{2}$.
It is also a good idea to try to conceptually understand why you would want to use some specific induction method to prove your claim. In this case, you want to prove your formula by strong induction, since you can split any pile anywhere, and you want to show that no matter what smaller size piles you end up with, the formula always holds.
Now, as a base case you can in fact just use $n=1$, in which case there is noting to do, and so the sum of the products is $0$, which is indeed what you get when plugging in $n=1$ for your formula.
For the inductive 'step', again get clear on what exactly the inductive hypothesis is (indeed, you make it seem like the step is separated, and comes only after the inductive hypothesis, but the inductive hypotheses is part of the step, so I strongly discourage the way you do this in your post). Now, you write: $n$ stones can eb split into $n$ and $k-n$ stones. OK, so first of all, that first $n$ should be $k$, but I understand that was just a typo. But far more importantly, this is not the inductive assumption. In fact, it is not even an interesting claim: of course a pile of $k$ stones can be split in two! The inductive assumption is that the earlier claim is true for all piles of size $n<k$. IN sum, what you should say after the base cases is:
Step: Let $k$ be some arbitrary number greater than the base case (i.e. $k>1$). The inductive hypothesis is that for any $n<k$ we have that no matter how you split a pile of $n$ stones, the eventual sum of products equals $\frac{n(n-1)}{2}$ (and yes, I very much encourage for strong induction to use $n<k$ rather than $n \le k$, for that allows you to proceed using $k$ instead of $k+1$, which often means that your proof and formulas will become a little easier, and also avoids making it look like you are doing weak induction)
OK, so now we try to show that under that assumption it would follow that the claim is true for a pile of size $k$. Ok, so let's consider a pile of size $k$. Does it matter where we split it? No. Let's split it into piles of size $m$ and $k-m$. By the inductive hypothesis, these two piles will end up with a sum of products of $\frac{m(m-1)}{2}$ and $\frac{(k-m)(k-m-1)}{2}$ respectively, but you also obtained a product of $m(k-m)$ by this very split. Hence, the eventual sum of products will be:
$$\frac{m(m-1)}{2}+\frac{(k-m)(k-m-1)}{2}+m(k-m)=$$
$$\frac{m(m-1)+(k-m)(k-m-1)+2m(k-m)}{2}=$$
$$\frac{m^2-m+k^2-mk-k-mk+m^2+m+2mk-2m^2}{2}=$$
$$\frac{k^2-k}{2}=\frac{k(k-1)}{2}$$
And thus we find the formula is true for any pile of size $k$ as well, no matter where you split it.
Finally, you may want to wrap things up, and say something like:
Since we have proven the base and the step, we have completed the proof by strong induction, and hence the claim is proven.