Associated Topics || Dr. Math Home || Search Dr. Math

### From Reduction to Induction

```Date: 02/03/2011 at 01:04:34
From: Katie
Subject: I found a pattern but I don;t understand how the pattern

Consider the following game.

You begin with the numbers 1, 2, 3, ..., n written on the board.

At each step, you can pick any two numbers x and y on the board, erase
them, and replace them with the number x + y + xy.

Continue until there is only a single number left.

Call P(n) the smallest possible number you can get from playing this game
starting with the numbers 1, 2, ..., n.

Find and prove a formula for P(n).

I've spent a great deal of time on this and can't seem to figure it out.
The lowest possible first combination is

1 + 2 + 1(2) = 5

The next lowest possible combination is

3 + 4 + 3(4) = 19

Then

5 + 6 + 5(6) = 41

Then

7 + 8 + 56 = 71

So the first four parts of the sequence are 5, 19, 41, 71.

But I don't understand how this pattern goes with the question, or how it
tells us the lowest formula.

```

```
Date: 02/03/2011 at 07:59:16
From: Doctor Jacques
Subject: Re: I found a pattern but I don;t understand how the pattern

Hi Katie,

You overlooked the fact that you must repeat the process until there is
only one number left.

For example, with n = 3, we could have the following sequence:

* We start with 1 and 2, giving 1 + 2 + 1*2 = 5; we remove the
numbers 1 and 2 and replace them by the number 5, leaving 5 and 3.
* We compute 5 + 3 + 5*3 = 23, and this is the final result.

From now on, let us write [a,b] for a + b + ab. The above sequence can be
written as:

[[1,2],3] = [5,3] = 23

Of course, at each step, you may have many different choices for the two
numbers to pick. We could also have chosen 2 and 3 first, giving:

[1,[2,3]] = [1,11] = 23

The result is the same! Could this be true in general?

Let us assume that we have three numbers left; call them a, b, and c. We
compute:

[[a,b],c] = [a + b + ab,c]
= a + b + c + ab + ac + bc + abc                       [1]

There is no need to compute [a,[b,c]] or [[a,c],b], because the expression
[1] remains the same whenever you permute a, b, and c in any way. If we
want to use a different order of evaluation, we only need to assign the
letters a, b, and c differently to the given numbers. We have seen that
this does not change the result.

So far, we have proved that the final result does not depend on the
evaluation order IF we have only three numbers. We would like to use a
simple induction argument to prove that this is true in general (and it
is...); but with more than three numbers, things are a little more
complicated.

For example, with four numbers, we could have ...

[[[a,b],c],d]

... or

[[a,b],[c,d]]

In the first case, we add one number at a time; in the second case, we
take first two sets of two numbers, and combine both results. It is not
immediately obvious that the result will be the same.

This calls for some abstract thinking.

Given a list of numbers A, we write ...

S(A,k)

... for the sum of all the products of k distinct elements from A. (You
must imagine that the numbers are indeterminates; if the same number
appears twice, you must consider the two appearances as distinct numbers.)

By definition, we have:

S((a),1) = a
S((a,b),1) = a + b
S((a,b),2) = ab

And

[a,b] = a + b + ab
= S((a,b),1) + S((a,b),2)

We have also seen that, with a list of three elements, A = (a,b,c) we have:

[[a,b],c] = S(A,1) + S(A,2) + S(A,3)

The nice thing about such an expression is that, if you permute the
elements of the list, the terms S(A,k) remain the same, and so does the
final result.

We would like to prove that, if A is a set of n elements, and we execute
the operation in any order until one element is left, the final result
will be:

P(A) = S(A,1) + S(A,2) + ... + S(A,n)                             [2]

As said before, we cannot assume that we include the numbers one at a
time. We must consider the general case where we merge together two
intermediate results.

If A and B are two lists of numbers, we write A#B for the 'disjoint union'
of A and B, i.e., if the same number appears in A and B, we count these
occurrences as two distinct numbers (as before, you can think that A and B
are lists of variables, and that all variables are different). We write
P(X) as the final result of the game with the set X, with operations
executed in an unspecified order. We assume, by induction, that P(A) (and
P(B)) are given by [2], which implies that the order of operations does
not change the result.

Assume that we have sets A and B, with m and n elements respectively.
Write C = A#B. We want to prove ...

[P(A),P(B)] = S(C,1) + ... + S(C,m + n)                          [3]

... under the induction hypotheses:

P(A) = S(A,1) + ... + S(A,m)
P(B) = S(B,1) + ... + S(B,n)

We have, by the rules of the game ...

[P(A),P(B)] =    P(A) + P(B) + P(A)P(B)
=  S(A,1) + ...  + S(A,m) + S(B,1) + ... + S(B,n) +
(S(A,1) + ...  + S(A,m))(S(B,1) + ...  + S(B,n))     [4]

... where we have used the induction hypotheses.

The idea is to collect together the terms of the same degree. We write
T(k) for the sum of the products of k factors appearing in [4]. To prove
[3], we must prove that T(k) = S(C,k), i.e., that all the products of k
factors from C appear in T(k), and each such product appears only once.

This is easy to see for k = 1: the last product in [4] will only give
terms of degree at least 2, and we have:

T(1) = S(A,1) + S(B,1)

This is simply the sum of the elements of A#B = C, i.e., S(C,1).

For k > 1, we have:

T(k) = S(A,k) + S(B,k) + SUM{S(A,i)S(B,j)}                       [5]

This sum ranges over the values of i and j such that:

1 <= i <= m
1 <= j <= n
i + j = k

If x is any product of k elements from A#B = C, we have three possible
cases:

* All elements come from A. In that case, x is an element of
the sum S(A,k)
* All elements come from B. In that case, x is an element of
the sum S(B,k)
* i elements come from A, and j elements come from B. In that case,
x is an element of the last sum in [5]

This shows that T(k) contains all the products of k elements from C, each
element once, which means that T(k) = S(C,k). If we take the sum for all
values of k, this proves [3].

The important point is that the RHS of [3] only depends on C, not on the
particular lists A and B. If we choose a different order of operations,
i.e., if we partition C into two other lists A' and B', we will get the
same result.

To summarize, we have proved that P(X) only depends on the list X, not on
the order of evaluation. This will allow us to choose a particular order
of evaluation that will make things (relatively) easier.

For the problem at hand, we must compute P(n) = P(A) where A is the list
(1, ..., n). As we may choose the order of evaluation, we evaluate from
left to right, i.e., we start with [1,2], combine the result with 3, and
so on. This gives the recurrence relation:

P(n) = [P(n - 1),n] = P(n - 1) + n + nP(n - 1)                   [6]

This could lead to an induction proof.

Note that, if we had a recurrence relation ...

f(n) = nf(n - 1)

... with f(1) = 1, the answer would be easy: we would have f(n) = n!. The
main problem is the term n in [6]. To try to remove it, we write:

P(n) = Q(n) - 1                                                  [7]

Substituting in [6], we get:

Q(n) - 1 = Q(n - 1) - 1 + n + n(Q(n - 1) - 1)

This simplifies to:

Q(n) = Q(n - 1) + nQ(n - 1)
= (n + 1)Q(n - 1)

This is the factorial formula, with n replaced by n + 1, the solution of
which is Q(n) = (n + 1)!, provided that the base case (n = 1) holds. We
check ...

Q(1) = 1 + P(1) = (1 + 1)!

... and [7] gives P(n) = (n + 1)! - 1.

You can check that P(2) = 5 = 3! - 1, P(3) = 23 = 4! - 1, as we have seen
before.

Please feel free to write back if you require further assistance.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
High School Sequences, Series
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search