Suppose you begin with a pile of n stones and split this pile into n piles of on

Question

Suppose you begin with a pile of n stones and split this pile into n piles of one stone each by repeatedly splitting a pile of stones (of size two or more) into two piles. Each time you split a pile, you multiply the number of stones in each of the resulting piles -- for example, if I split a pile of 10 stones into a pile of size 3 and a pile of size 7, then I compute 21. During this process, you keep track of the sum of all of these products. We claim that no matter how you split the piles, the sum of the products computed is n(n-1)/2 (a) show this is true for n=5 by brute force: enumerate all possible ways in which the 5 stones can be partitioned and evaluate each sum of products. (b) Prove that the claim is true for all n1. What kind of induction did you use?

Explanation / Answer

Proof by induction as stated. If you have one stone, you do no splitting, and 1*0/2 = 0, which is correct. If you have two stones, you have to split into two piles of size 1. 1 * 1 = 1. n(n-1)/2 = 2(2-1)/2 = 2*1/2 = 2/2 = 1. Correct. Assume for n = k. Show for n = k + 1. When you split the pile of size k+1, you split this into 2 piles of size x and k+1-x, where 1

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.