To give you a sense of strong induction and the relationship between mathematica

Question

To give you a sense of strong induction and the relationship between mathematical induction and recursion, let's do the pile splitting problem:

Take a bunch of beads, rocks, coins, or any kind of chips. Ten is a good number. Split the pile into 2 smaller piles and multiply their sizes. Continue splitting each pile you create and multiply the sizes of the 2 smaller piles until all the piles are of size 1. Then, add those products together. No matter how you split the piles, you will always obtain the same number. This number is a function of the number of chips in the pile which can be proven using strong induction.

Do it for different numbers of chips. Can you see a pattern emerge?

In your own words, why should you use strong induction for this problem as opposed to weak induction?

Explanation / Answer

We will show that it is n(n-1)/2
For n = 1, it is 0 and 1*0/2=0
For n = 2,
you break the pile into 2 piles of size 1 and 1
1 * 1 = 1
(n)(n-1)/2 = 2(2-1)/2 = 2*1/2 = 1
Assume for n=k (i.e.,2-k)
Then, for n=k+1
Split this into 2 piles of size m and k+1-m
The product is m(k+1-m) = km + m - m2

From strong induction, we can assume the results for 1 - k

In particular,

the pile from size m can be broken into m(m-1)/2 =

1/2 m2 - 1/2m

The pile from size k+1-m can be broken into 1/2(k+1-m)(k+1-m-1)=

1/2(k+1-m)(k-m) =

1/2 k 2 + 1/2k - 1/2km -1/2km -1/2m + 1/2m2 =

1/2 k 2 + 1/2k -1/2m - km + 1/2m2

Now, we add the three together

km + m - m2 + 1/2 m2 - 1/2m + 1/2 k 2 + 1/2k -1/2m - km + 1/2m2 =

km - km + m - 1/2m -1/2m - m2 + 1/2 m2 + 1/2m2 + 1/2 k 2 + 1/2k =

1/2 k 2 + 1/2k =

(k+1)(k)/2

This is what we were trying to prove for n=k+1

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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