Sums and Approximations 5 5 2k-1 So the number of blocks in the k-th slab is +3+5+…+(2k-1)+….+5+3+1=(2k-1)+2.∑2i Plugging this into the previous sum gives the total number of blocks required by Pharaoh Aha blocks in n-th pyramid ∑ (2k-1)+ This sum is pretty nasty. And the bad news is that similar sums arise when analyzing the running time of a program with nested loops 2.1 Evaluating the Sum Sums of small powers are actually easy to handle, because there are simple closed-form equivalents Lemma 3(Sums of Powers) m(m+ 1+2+3+...+m 12+22+32+.+m2 m(m+o)(m+ m2(m+1) These formulas can all be proved by routine induction arguments. For now, let's apply hem toto find a closed-form expression for the number of blocks in a pyramid. First,� � � � � Sums and Approximations 7 . . . . . . 3 5 2k−1 5 3 1 1 So the number of blocks in the k­th slab is: k−1 1 + 3 + 5 + . . . + (2k − 1) + . . . + 5 + 3 + 1 = (2k − 1) + 2 · 2j − 1 j=1 Plugging this into the previous sum gives the total number of blocks required by Pharaoh Aha­n: n k−1 # blocks in n­th pyramid = (2k − 1) + 2 · 2j − 1 k=1 j=1 This sum is pretty nasty. And the bad news is that similar sums arise when analyzing the running time of a program with nested loops. 2.1 Evaluating the Sum Sums of small powers are actually easy to handle, because there are simple closed­form equivalents: Lemma 3 (Sums of Powers). m(m + 1) 1 + 2 + 3 + . . . + m = 2 1 2 2 12 + 22 + 3 + . . . + m = m(m + 2 )(m + 1) 3 m2 2 (m + 1) 3 3 13 + 23 + 3 + . . . + m = 4 These formulas can all be proved by routine induction arguments. For now, let’s apply them to to find a closed­form expression for the number of blocks in a pyramid. First