Pertains to Section  1.5.4  The Asymptotic Order of Commonly Occurring Sums

Polynimial series

(∑_(i=1)^n)(i^19)

(∑_(i=1)^n)(i^d)

(∫_0^n)(x^d) \[DifferentialD]x ≤ (∑_(i=1)^n)(i^d) ≤ (∫_1^(n+1))(x^d) \[DifferentialD]x

(∫_0^n)(x^d) \[DifferentialD]x

(∫_1^(n+1))(x^d) \[DifferentialD]x

(∑_(i=1)^n)(i^d) ∈ Θ((n^(d+1)))

Another trick (relates to figure 1.7)

For any non-decreasing function f,

(∑_(i=1)^n)f(i)≤ n×f(n)

and

(∑_(i=(n/2))^n)f(i)≤ (∑_(i=1)^n)f(i)

Since

(∑_(i=(n/2))^n)f(i)≥ (n/2)×f((n/2))

we conclude

(n/2)×f((n/2)) ≤ (∑_(i=1)^n)f(i)≤ n×f(n)

Hence

((((n/2)))^(d+1))=(n/2)×((((n/2)))^d) ≤ (∑_(i=1)^n)(i^d)≤ n×(n^d) = (n^(d+1))

((((n/2)))^(d+1))∈ Θ((n^(d+1))) and  (n^(d+1))∈ Θ((n^(d+1))),
 
so

(∑_(i=1)^n)(i^d)∈ Θ((n^(d+1))).

Geometric series

(∑_(i=0)^n)(2^i)

(∑_(i=0)^n)(1/(2^i))

(∑_(i=0)^n)(r^i)

(∑_(i=0)^n)(r^i)∈ Θ((r^n))  if  r > 1

(∑_(i=0)^n)(r^i)∈ Θ(1)  if  0<r < 1

Harmonic series (done before, quoted here for your convenience)

(∑_(i=1)^n)(1/i)

Plot[Tooltip[{(∑_(i=1)^n)(1/i), Log[n]+.577}],{n, 1, 20}]

(∫_2^(n+1))(1/x)\[DifferentialD]x≤ (∑_(i=2)^n)(1/i)≤ (∫_1^n)(1/x)\[DifferentialD]x

(∫_2^(n+1))(1/x)\[DifferentialD]x

Log[n+1]-Log[2]

N[Log[2]]

(∫_1^n)(1/x)\[DifferentialD]x

Log[n]

So,

Log[n+1] - 0.694 ≤ (∑_(i=2)^n)(1/i)≤ Log[n]

Plot[Tooltip[{Log[n],(∑_(i=2)^n)(1/i), Log[n+1]- 0.694}],{n, 2, 20}]

(∑_(i=1)^n)(1/i)∈ Θ(log n)

Logarithmic series

(n/2)(Log2[n]-1)=  (n/2)Log2[(n/2)]≤ (∑_(i=1)^n)Log2[i]≤ n Log2[n]

Since

(n/2)(Log2[n]-1)∈ Θ(n log n)

and

n Log2[n]∈ Θ(n log n)

we conclude

 (∑_(i=1)^n)Log2[i]∈ Θ(n log n)

Exercise

Show that

(∑_(i=1)^n)(i^d)Log2[i]∈Θ((n^(d+1))log n)