- Thread starter
- #1

#### Joystar1977

##### Active member

- Jul 24, 2013

- 119

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.

- Thread starter Joystar1977
- Start date

- Thread starter
- #1

- Jul 24, 2013

- 119

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.

- Admin
- #2

- Thread starter
- #3

- Jul 24, 2013

- 119

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.

- Jan 30, 2012

- 2,541

First you have to do the work. Here are all ways (up to permutation) to split a pile of four objects.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.

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.

- Thread starter
- #5

- Jul 24, 2013

- 119

- Thread starter
- #6

- Jul 24, 2013

- 119

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.

- Jan 30, 2012

- 2,541

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.Is what you just showed me the discrete math question or a differential equation question?

I am not sure if you meant "

- Thread starter
- #8

- Jul 24, 2013

- 119

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 "differenceequations" because one may use them for guessing the formula for $n$, but they are also studied in discrete math.

- Thread starter
- #9

- Jul 24, 2013

- 119

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.

- Jan 30, 2012

- 2,541

Yes, but only when the initial pile has 4 objects.Isn't the sum of all the products equal to 6?

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

- Thread starter
- #11

- Jul 24, 2013

- 119

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.

- Jan 30, 2012

- 2,541

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.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?

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