Exercise 3-2, page 58, of the second edition of Cormen, Leiserson and Rivest. This is the same as exercise 2-2, page 38, of the first edition. It will help if you draw a rough estimate of what the graph of each function looks like.
What is the value of the following sum? SUM is the summation sign.
n
SUM (2k+1)
k = 0
You can use the following properties of summations.
(linearity-1)
n n
SUM cf(k) = c( SUM f(k))
k = 0 k = 0
whenever c does not depend on k.
(linearity-2)
n n n
SUM (A + B) = ( SUM A) +( SUM B)
k = 0 k = 0 k = 0
(counting)
n
SUM 1 = n + 1
k = 0
since there are n+1 terms being added up, and each is 1.