Prove the following using a non-inductive argument: Suppose that you begin with

Question

Prove the following using a non-inductive argument:

Suppose that you begin with a pile of n stones and split the 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 smaller piles you form, so that if the smaller piles have r and s stones in them, you compute rs. Show that no matter how you split the piles, the sum of the products computed at each step equals to n(n-1)/2.

Hint: Consider the Cartesian product of two sets (extra hint: set r and set s and arbitrary elements that belong to them) and how you might be able to relate this to the binomial coefficient

Explanation / Answer

sol: Consider the case when n = 2. It is easy to observe that there will be only one step resulting in two piles of one stone each. The sum of the products will be 1 = 2 (2-1)=2. Assume (strong induction hypothesis) that if the number of stones is less than or equal to n, the sum of products computed at each step is n(n - 1)=2. We will compute, no matter how you split the piles, the sum for n + 1 stones is (n + 1)n=2. Consider the rst split is done so that r+s = n+ 1. The product at this step is rs, the sum of the products for the pile with r stones is r(r -1)=2, and the sum of the products for the pile with s stones is s(s - 1)=2. Sum of these sums will yield the result.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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