2 Sums, Approximations, and Asymptotics Il The offset determines precisely how far that configuration can extend beyond the desk since at best the center of mass lies right above the desks edge. So hereafter we can focus on maximizing the offset of a stack of n blocks rather than the overhang. As a result, we need only be concerned with whether the stack is internally stable and not with whether the whole configuration is too far to the right and falls off the table We can establish the greatest possible offset of a stack of n blocks with an inductive argument. This is an instance where induction not only serves as a proof technique, but lso turns out to be a nice tool for reasoning about the problem Theorem 1. The greatest possible offset of a stack of n> 1 blocks 246 Proof. We use induction on n, the number of blocks. Let P(n) be the proposition that the greatest possible offset of a stack of n> 1 blocks is 1/2+1/4+..+1/(2n) Base case: For a single block, the center of mass is distance X1= 1/2 from its rightmost edge. So the offset is 1/2 and P(1)is true Inductive step: For n> 2, we assume that P(n-1) is true in order to prove P(n). A stack of n blocks consists of the bottom block together with a stack of n-1 blocks on top In order to acheive the greatest possible offset with n blocks the top n-1 blocks should themselves have the greatest possible offset, which is Xn-i; otherwise, we could do better by replacing the top n- l blocks with a different configuration that has greater offset Furthermore, the center of mass of the top n-1 blocks should lie directly above the right edge of the bottom block; otherwise, we could do better by sliding the top n-1 blocks farther to the right n-1 blocks Weve now identified the configuration of n blocks with the greatest possible offset What remains is to determine what that offset is. To that end, we'll apply Fact 1 where positions are measured relative to the rightmost edge of the n-block stack. In particular, 1 blocks with center of mass at position Xn-I, and 1 block wit at position Xn-1+2. So Fact 1 implies that the maximum possible offset of a stack of n2 Sums, Approximations, and Asymptotics II The offset determines precisely how far that configuration can extend beyond the desk since at best the center of mass lies right above the desk’s edge. So hereafter we can focus on maximizing the offset of a stack of n blocks rather than the overhang. As a result, we need only be concerned with whether the stack is internally stable and not with whether the whole configuration is too far to the right and falls off the table. We can establish the greatest possible offset of a stack of n blocks with an inductive argument. This is an instance where induction not only serves as a proof technique, but also turns out to be a nice tool for reasoning about the problem. Theorem 1. The greatest possible offset of a stack of n ≥ 1 blocks is: 1 1 1 1 Xn = + + + . . . + 2 4 6 2n Proof. We use induction on n, the number of blocks. Let P(n) be the proposition that the greatest possible offset of a stack of n ≥ 1 blocks is 1/2 + 1/4 + . . . + 1/(2n). Base case: For a single block, the center of mass is distance X1 = 1/2 from its rightmost edge. So the offset is 1/2 and P(1) is true. Inductive step: For n ≥ 2, we assume that P(n − 1) is true in order to prove P(n). A stack of n blocks consists of the bottom block together with a stack of n − 1 blocks on top. In order to acheive the greatest possible offset with n blocks, the top n−1 blocks should themselves have the greatest possible offset, which is Xn−1; otherwise, we could do better by replacing the top n − 1 blocks with a different configuration that has greater offset. Furthermore, the center of mass of the top n − 1 blocks should lie directly above the right edge of the bottom block; otherwise, we could do better by sliding the top n − 1 blocks farther to the right. n − 1 blocks s Xn−1 - s Xn−1 + 1 - 2 We’ve now identified the configuration of n blocks with the greatest possible offset. What remains is to determine what that offset is. To that end, we’ll apply Fact 1 where positions are measured relative to the rightmost edge of the n­block stack. In particular, we have n−1 blocks with center of mass at position Xn−1, and 1 block with center of mass at position Xn−1 + 1 . So Fact 1 implies that the maximum possible offset of a stack of n 2