PROBLEM SOLVING EPISODE

The Problem:

The list of positive whole numbers that add up to 1 is simply (1), and you might think of the product of this list as being 1.

There are several lists of positive whole numbers that add up to 2, and the lists (1,1) and (2) have different products if you multiply the list elements: 1 and 2. The lists of positive whole numbers that add up to 3 yield products 1, 2 and 3, corresponding to the lists (1,1,1), (1,2) and (3).

If n represents a positive whole number, what is the largest product that can be formed by multiplying the elements of a list of positive whole numbers that sum to n?


Devising a Plan:

The first thing to do is to create a table with three columns with the first column being the value of n, the second column being the lists of whole numbers that sum to n, and the third column being the list from the second column with the highest product. In my opinion, we should fill this table at least until n=7 so that there is enough solid data to work from. This, in a way, would be the base case of the proof. Then the conclusions made from this table should be used in order to generate the predicate that will be proved.


Carrying out the Plan:

After creating the table for the first few values of n, we see the pattern that the list with the maximum product is always the one that consists of either 2s or 3s or both. From this observation we can assume this fact for P(0)/\.../\P(n-1) and using the method of complete induction we can prove that P(n) is also true. This is possible since any whole number, larger than a certain whole number c, can be produced from the sum of previous whole numbers, which have been assumed true by the Induction Hypothesis.


Conclusion:

The above was a summary of the processes that need to be executed in order to end up with a complete induction proof for the problem. The table could be used in the place of a base case and as a clue to the formation of a predicate. From that point the proof becomes very straightforward and intuitive.