From Reduction to InductionDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/