Sums, Approximations, and Asymptotics T blocks is (n-1)+(Xn-1+) X 1.1.1 We use the assumption P(n-1) in the last step. This proves P(n) The theorem follows by the principle of induction 1.1 Harmonic numbers Sums similar to the one in Theorem 1 come up all the time in computer science. In partic is called a harmonic sum. Its value is called the n-th harmonic number and is denoted Hn In these terms, the greatest possible offset of a stack of n blocks is Hn We can tabulate the maximum achievable overhang with n= 1, 2, 3 and 4 blocks by computing the first few harmonic numbers of blocks maximum overhang 2H2=是(+)= H3=是(+是+)= 是H4=是(+++1)=2 The last line reveals that we can suspend the fourth block beyond the edge of the table Here's the configuration that does the trickSums, Approximations, and Asymptotics II 3 blocks is: 1 2 ) 1· Xn = Xn−1 · (n − 1) + (Xn−1 + n 1 = Xn−1 + 2n 1 1 1 1 = + + + . . . + 2 4 6 2n We use the assumption P(n − 1) in the last step. This proves P(n). The theorem follows by the principle of induction. 1.1 Harmonic Numbers Sums similar to the one in Theorem 1 come up all the time in computer science. In partic￾ular, 1 1 1 1 + + + . . . + 1 2 3 n is called a harmonic sum. Its value is called the n­th harmonic number and is denoted Hn. In these terms, the greatest possible offset of a stack of n blocks is 1 2Hn. We can tabulate the maximum achievable overhang with n = 1, 2, 3 and 4 blocks by computing the first few harmonic numbers: # of blocks maximum overhang 1 1 2 1 1 1 2 1 H1 = ( ) = 2 1 1 2 1 1 3 4 2 H2 = ( + ) = 2 1 2 1 1 2 1 1 1 11 = 12 3 H3 = ( + + ) 2 1 2 3 1 1 2 1 1 1 1 25 4 H4 = ( + + + ) = > 1 2 1 2 3 4 24 1 2 1 4 1 6 1 8 The last line reveals that we can suspend the fourth block beyond the edge of the table! Here’s the configuration that does the trick: