How Does Strong Induction Prove Consistency in the Pile Splitting Problem?

[Joystar77]

To give you a sense of strong induction and the relationship between mathematical induction and recursion (next session), 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?

Is this correct:

I would use strong induction for this problem because of the splitting of the piles and multiplying the sizes. If this isn't right, then please someone help me.

 

[MarkFL]

I am assuming you have tried it for a few cases and come up with an induction hypothesis. What is your hypothesis?

What is the difference between strong and weak induction?

 

[Joystar77]

Isn't the role of the induction variable is to use the letters n versus k. I would use the letter n for the variable statement of the formula (or proposition, etc.) that I am seeking to prove (and which, as pointed out above, I should have repeat at the beginning of every induction proof. I would use the letter k ( or some other letter) for the variable appearing in the induction step. The reason for this distinction is that one can then say something like the following: Let k e Z+, be given, and suppose (1) is true for n=k... Is it true that the proof of induction step goes here? Therefore (1) is true for n = k + 1.

Isn't the role of the induction hypothesis is the case n = k of the statement we seek to prove ("P (k)") and something we assume at the start of the induction step? I am suppose to come up with this hypothesis and it comes into play at some point during the proof of the induction step, if not then am I doing something wrong? The place where the induction hypothesis is used is the most important/crucial step in the induction argument and I am suppose to clearly state the appropriate place when I am using the induction hypothesis. Isn't the induction hypothesis a chain of equations?

Is my induction hypothesis in this case as follows:
n
i = n (n+1)/2
i=1

Isn't the only difference between weak and strong induction is that it appears in the induction hypothesis? Isn't the weak induction only that I am supposed to assume that a particular statement holds at k-th step? Isn't the strong induction only that I am supposed to assume that a particular statement holds at all the steps from the base case to the k-th step?

If this isn't right, then please correct this for me.

 

[Evgeny.Makarov]

Is this correct:

I would use strong induction for this problem because of the splitting of the piles and multiplying the sizes. If this isn't right, then please someone help me.

First you have to do the work. Here are all ways (up to permutation) to split a pile of four objects.

As you see, after each splitting we multiply the number of objects in the two smaller piles. The products are shown in red. In the end, we sum up all red products. In this case, the sum is 6 for both ways of splitting.

I suggest you draw all possible similar trees that start on the top with 3, 5 and 6 and possibly bigger numbers. In fact, you don't have to draw complete trees. For example, 6 can be split into 4 and 2, but we have already verified that any way of splitting 4 gives 6 as the result (the sum of red numbers), so there is no need to draw the trees for 4 again.

After you convince yourself that the result does not depend on the way of splitting and calculate the result for top number 3, 4, 5, 6 and so on, it's time to guess the general formula for the result. Since the way of splitting does not matter, we can split $n$ into $n - 1$ and 1. The product of $n - 1$ and 1 is $n - 1$. Then you split $n - 1$ into $n-2$ and 1. The product is $n-2$. Continuing this way, what do you get as the sum of all products?

Finally, to understand why strong induction is necessary, you should try proving your hypothesis (the formula for the sum of all products after splitting $n$ objects) using regular induction and see where it does not work. Of course, you should feel comfortable with regular induction to do this.

 

[Joystar77]

I just wanted to add a quick note before I get deeper into this problem that my instructor says that this is a discrete math question and not a differential equation question.

 

[Joystar77]

Is what you just showed me the discrete math question or a differential equation question?

First you have to do the work. Here are all ways (up to permutation) to split a pile of four objects.

As you see, after each splitting we multiply the number of objects in the two smaller piles. The products are shown in red. In the end, we sum up all red products. In this case, the sum is 6 for both ways of splitting.

I suggest you draw all possible similar trees that start on the top with 3, 5 and 6 and possibly bigger numbers. In fact, you don't have to draw complete trees. For example, 6 can be split into 4 and 2, but we have already verified that any way of splitting 4 gives 6 as the result (the sum of red numbers), so there is no need to draw the trees for 4 again.

After you convince yourself that the result does not depend on the way of splitting and calculate the result for top number 3, 4, 5, 6 and so on, it's time to guess the general formula for the result. Since the way of splitting does not matter, we can split $n$ into $n - 1$ and 1. The product of $n - 1$ and 1 is $n - 1$. Then you split $n - 1$ into $n-2$ and 1. The product is $n-2$. Continuing this way, what do you get as the sum of all products?

Finally, to understand why strong induction is necessary, you should try proving your hypothesis (the formula for the sum of all products after splitting $n$ objects) using regular induction and see where it does not work. Of course, you should feel comfortable with regular induction to do this.

 

[Evgeny.Makarov]

Is what you just showed me the discrete math question or a differential equation question?

Why did you bring up differential equations? That subjects deals with quantities that change smoothly. In contrast, discrete mathematics is about quantities that change in steps: 1, 2, 3, ... Here the number of objects in a pile does not change smoothly from, say, 6 to 1; instead, it remains an integer. Therefore, yes, this is discrete mathematics.

I am not sure if you meant "difference equations" because one may use them for guessing the formula for $n$, but they are also studied in discrete math.

 

[Joystar77]

Sorry I didn't mean to bring it up. My instructor just sent me an email since I am taking this course online and told me that just as a side note this is a discrete math question and not a differential equation question. I just wanted to make sure to stick with the topic of Discrete Mathematics. As you already know, I am still trying to grasp the concepts of this material and so far I have a D in my class. I only have until the end of October when my class ends and if I don't at least get a C, then I will have to end up repeating this course. Again, I appreciate your help Evgeny.Makarov, MarkFL, and Caffeine Maker. Your explanations have really helped me through these problems.

Why did you bring up differential equations? That subjects deals with quantities that change smoothly. In contrast, discrete mathematics is about quantities that change in steps: 1, 2, 3, ... Here the number of objects in a pile does not change smoothly from, say, 6 to 1; instead, it remains an integer. Therefore, yes, this is discrete mathematics.

I am not sure if you meant "difference equations" because one may use them for guessing the formula for $n$, but they are also studied in discrete math.

 

[Joystar77]

Isn't the sum of all the products equal to 6? What do you mean by regular induction? I thought there was only weak induction and strong induction.

First you have to do the work. Here are all ways (up to permutation) to split a pile of four objects.

As you see, after each splitting we multiply the number of objects in the two smaller piles. The products are shown in red. In the end, we sum up all red products. In this case, the sum is 6 for both ways of splitting.

I suggest you draw all possible similar trees that start on the top with 3, 5 and 6 and possibly bigger numbers. In fact, you don't have to draw complete trees. For example, 6 can be split into 4 and 2, but we have already verified that any way of splitting 4 gives 6 as the result (the sum of red numbers), so there is no need to draw the trees for 4 again.

After you convince yourself that the result does not depend on the way of splitting and calculate the result for top number 3, 4, 5, 6 and so on, it's time to guess the general formula for the result. Since the way of splitting does not matter, we can split $n$ into $n - 1$ and 1. The product of $n - 1$ and 1 is $n - 1$. Then you split $n - 1$ into $n-2$ and 1. The product is $n-2$. Continuing this way, what do you get as the sum of all products?

Finally, to understand why strong induction is necessary, you should try proving your hypothesis (the formula for the sum of all products after splitting $n$ objects) using regular induction and see where it does not work. Of course, you should feel comfortable with regular induction to do this.

 

[Evgeny.Makarov]

Isn't the sum of all the products equal to 6?

Yes, but only when the initial pile has 4 objects.

What do you mean by regular induction? I thought there was only weak induction and strong induction.

By regular I mean weak.

 

[Joystar77]

Evgeny: Please let me understand you correctly. You are stating that I should understand why strong induction is necessary for this problem when I am trying to prove what my hypothesis is. In this problem, could I use weak induction (Also known as regular induction) in certain cases throughout this problem? Can I use weak and strong induction when trying to work this problem out?

First you have to do the work. Here are all ways (up to permutation) to split a pile of four objects.

As you see, after each splitting we multiply the number of objects in the two smaller piles. The products are shown in red. In the end, we sum up all red products. In this case, the sum is 6 for both ways of splitting.

I suggest you draw all possible similar trees that start on the top with 3, 5 and 6 and possibly bigger numbers. In fact, you don't have to draw complete trees. For example, 6 can be split into 4 and 2, but we have already verified that any way of splitting 4 gives 6 as the result (the sum of red numbers), so there is no need to draw the trees for 4 again.

After you convince yourself that the result does not depend on the way of splitting and calculate the result for top number 3, 4, 5, 6 and so on, it's time to guess the general formula for the result. Since the way of splitting does not matter, we can split $n$ into $n - 1$ and 1. The product of $n - 1$ and 1 is $n - 1$. Then you split $n - 1$ into $n-2$ and 1. The product is $n-2$. Continuing this way, what do you get as the sum of all products?

Finally, to understand why strong induction is necessary, you should try proving your hypothesis (the formula for the sum of all products after splitting $n$ objects) using regular induction and see where it does not work. Of course, you should feel comfortable with regular induction to do this.

 

[Evgeny.Makarov]

You are stating that I should understand why strong induction is necessary for this problem when I am trying to prove what my hypothesis is. In this problem, could I use weak induction (Also known as regular induction) in certain cases throughout this problem? Can I use weak and strong induction when trying to work this problem out?

A proof should work for all cases. In this problem, the sum of products is $n(n-1)/2$ when one starts with a heap of $n$ objects, regardless of the way this heap is split. If you split the heap only in certain ways, then you can use weak induction to prove that the result is $n(n-1)/2$. But if you split the heap in all possible ways, a proof must use strong induction.

Why don't you try to figure out the sum of products for the initial heap of 5 or 6 objects?