Copyright by Dr. Marek A. Suchenek 2012,2013,2014
This material is intended for future publication.
Absolutely positively no copying no printing no sharing no distributing of ANY kind, please.

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

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

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

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

Expand[%]

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

Plot[{(∫_0^n)x \[DifferentialD]x , (∑_(i=1)^n)i , (∫_1^(n+1))x \[DifferentialD]x},{n,1,20}]

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

Expand[%]

Plot[{(∫_0^n)(x^2) \[DifferentialD]x , (∑_(i=1)^n)(i^2) , (∫_1^(n+1))(x^2) \[DifferentialD]x},{n,1,20}]

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

Expand[%]

Plot[{(∫_0^n)(x^3) \[DifferentialD]x , (∑_(i=1)^n)(i^3) , (∫_1^(n+1))(x^3) \[DifferentialD]x},{n,1,20}]

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

((n^(1+k))/(1+k)) ≤ (∑_(i=1)^n)(i^k) ≤ (-1+(((1+n))^(1+k)))/(1+k)

((n^(k+1))/(k+1)) ≤ (∑_(i=1)^n)(i^k) ≤ ((((n+1))^(k+1))-1)/(k+1)

Theorem - part one

For every non-decreasing function f
(∫_(a-1)^b)f(x) \[DifferentialD]x ≤ (∑_(i=a)^b)f(i) ≤ (∫_a^(b+1))f(x) \[DifferentialD]x

Example

(∫_1^8)(Sqrt[x]) \[DifferentialD]x ≤ (∑_(i=2)^8)(Sqrt[i]) ≤ (∫_2^9)(Sqrt[x]) \[DifferentialD]x

Graphic proof of the second inequality
(∑_(i=2)^8)(Sqrt[i]) ≤ (∫_2^9)(Sqrt[x]) \[DifferentialD]x:

Graphic proof of the first inequality 
(∫_1^8)(Sqrt[x]) \[DifferentialD]x ≤ (∑_(i=2)^8)(Sqrt[i]):

(∫_1.50574838034444^8.50574838034444)(Sqrt[x]) \[DifferentialD]x ≈(∑_(i=2)^8)(Sqrt[i])

≈15.30600052603572

Theorem - part two

For every non-increasing function f
(∫_a^(b+1))f(x) \[DifferentialD]x ≤ (∑_(i=a)^b)f(i) ≤ (∫_(a-1)^b)f(x) \[DifferentialD]x

Anther usefull Theorem

For every non-decreasing function f and every 
1≤k≤n,
k×f(n-k+1)≤ (∑_(i=1)^n)f(i) ≤ n×f(n)

or, substituting n - k + 1 for k,

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

Example

k×(n-k+1)!≤ (∑_(i=1)^n)i! ≤ n×n!

Putting k =⌈ (n/2)⌉ yields:

⌈ (n/2)⌉×(n-⌈ (n/2)⌉+1)!≤ (∑_(i=1)^n)i! ≤ n×n!

By ⌈(n/2)⌉ +⌊(n/2)⌋=n we get:

⌈ (n/2)⌉×(⌊(n/2)⌋+1)!≤ (∑_(i=1)^n)i! ≤ n×n!

By ⌈(n/2)⌉ ≤ ⌊(n/2)⌋+1=n we get:

⌈ (n/2)⌉×⌈(n/2)⌉!≤ (∑_(i=1)^n)i! ≤ n×n!

By Stirling formula we get:

⌈ (n/2)⌉(((((⌈ (n/2)⌉)/E)))^(⌈ (n/2)⌉))(Sqrt[2π ⌈ (n/2)⌉])< (∑_(i=1)^n)i! < n((((n/E)))^n)(Sqrt[2π n])(1 + (1/(11n)))

By (n/2)≤ ⌈ (n/2)⌉ we get:

(n/2)(((((n/2)/E)))^(n/2))(Sqrt[2π (n/2)])< (∑_(i=1)^n)i! < n((((n/E)))^n)(Sqrt[2π n])(1 + (1/(11n)))

or

E((((n/(2E))))^((n/2)+1))(Sqrt[π n])< (∑_(i=1)^n)i! < E((((n/E)))^(n+1))(Sqrt[2π n])(1 + (1/(11n)))

Plot[{E((((n/(2E))))^((n/2)+1))(Sqrt[π n]), (∑_(i=1)^n)i! , E((((n/E)))^(n+1))(Sqrt[2π n])(1 + (1/(11n)))},{n,1,7}]

Plot[{Log[E((((n/(2E))))^((n/2)+1))(Sqrt[π n])], Log[(∑_(i=1)^n)i! ], Log[E((((n/E)))^(n+1))(Sqrt[2π n])(1 + (1/(11n)))]},{n,1,30}]

If non-decreasing f is non-negative then for every 
1≤k≤n,
 
f(((n-k+1))^k)≤ (∏_(i=1)^n)f(i) ≤ f(((n))^n)

Example

 (((n-k+1))^k)≤ (∏_(i=1)^n)i ≤ (n^n)
where (∏_(i=1)^n)i = n!

So,
(((n-k+1))^k)≤ n! ≤ (n^n)

If n is even then putting k = (n/2) yields:

((((n/2)+1))^(n/2))≤ n! ≤ (n^n)

Putting k = ⌈(n/2)⌉ in (((n-k+1))^k)≤ n! ≤ (n^n)
we get
(((n-⌈(n/2)⌉+1))^(⌈(n/2)⌉))≤ n! ≤ (n^n)

or, by ⌈(n/2)⌉+⌊(n/2)⌋=n,

(((⌊(n/2)⌋+1))^(⌈(n/2)⌉))≤ n! ≤ (n^n)

By ⌈(n/2)⌉<⌊(n/2)⌋+1 we get:

(((⌈(n/2)⌉))^(⌈(n/2)⌉))≤ n! ≤ (n^n)

and by (n/2)≤ ⌈(n/2)⌉ we conclude

((((n/2)))^(n/2))≤ n! ≤ (n^n)

Plot[{((((n/2)))^(n/2)), n! , (n^n)},{n,1,8}]

Plot[{Log[((((n/2)))^(n/2))], Log[n!] ,Log[ (n^n)]},{n,1,50}]

** ** ** ** ** ** ** ****
Undergraduate students:skip until ##

Proof of ∑ part

There are m-n elements anfter m in an n-element sequence. So, since f is non-decreasing,in the sequence 
f(1), f(2),...,f(m),...,f(n) 
there are at least n-m+1 
elements greater of equal to f(m). 

Therefore,
 (n-m+1)×f(m)≤ (∑_(i=1)^n)f(i) 

Puting k = n-m+1, that is, m = n - k + 1, yields

k×f(n-k+1)≤ (∑_(i=1)^n)f(i).

The inequality

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

is easy to proof and is left as an exercise.

Proof of the ∏ part from the ∑ part

k×(Subscript[log, 2])f(n-k+1)≤ (∑_(i=1)^n)(Subscript[log, 2])f(i) ≤ n×(Subscript[log, 2])f(n)

(Subscript[log, 2])f(((n-k+1))^k)≤ (Subscript[log, 2])(∏_(i=1)^n)f(i) ≤ (Subscript[log, 2])f(((n))^n)

f(((n-k+1))^k)≤ (∏_(i=1)^n)f(i) ≤ f(((n))^n)

##############################

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

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

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

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

Euler's approximation of harmonic number

(∑_(i=1)^n)(1/i) ≈ Log[n]+.577

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

A glance at the above graph yields the following improvement

Plot[Tooltip[{(∑_(i=1)^n)(1/i),Log[n+0.5]+0.577}],{n,1,20},PlotTheme->"Classic"]

But it's not so good for larger n

Plot[Tooltip[{(∑_(i=1)^n)(1/i),Log[n+0.5]+0.577}],{n,10000,10020},PlotTheme->"Classic"]

A more precise traditional approximation

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

Ever better approximation, if you are a perfectionist:

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

Still not so good for larger n

Plot[Tooltip[{(∑_(i=1)^n)(1/i),Log[n]+0.577` +(1/(2 n))-(1/(12 (n^2)))}],{n,10000,10020},PlotTheme->"Classic"]

You can use the constant EulerGamma =

N[EulerGamma]

0.5772156649015329`

in lieu of .577

N[(E^EulerGamma)]

End of Euler' s approximation of harmonic number

Here is another (less accurate) way of approximating the harmonic series  (∑_(i=1)^n)(1/i). It's a good exercise.

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

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

N[Log[2]]

So,

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

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

(∑_(i=1)^k)i×(2^i)

Expand[%]

2+(2^(1+k)) (k-1)

(2^(k+1)) (k-1)+2

Log2[n!] = (∑_(i=1)^n)Log2[i]

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

Textbook's approximation:

(∑_(i=1)^n)Log2[i] ≈ n Log2[n] - 1.443n + 2.9

Plot[Tooltip[{(∑_(i=1)^n)Log2[i], n Log2[n] - 1.443n + 2.9}], {n, 1, 20}]

Even more accurate approximation is in the Mathematica/Log_of_factorial.nb :
(∑_(i=1)^n)Log2[i] ≈ n Log2[n]-(1/(Log[2]))n +(1/2)Log2[n]+Log[2 π]/Log[4]+1/(Log[4096]n)-1/(360 Log[2](n^3))

This yields:
(∑_(i=1)^n)Log2[i] ≈ 
(n+(1/2)) Log2[n]-1.4426950408889634`n +1.3257480647361592`
or

(∑_(i=1)^n)Log2[i] ≈ 
(n+(1/2)) Log2[n]-1.443n +1.326

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

Sterling formula (see file Mathematica/Stirling_formula.nb) would yield this:
(∑_(i=1)^n)Log2[i] = Log2[n!] >Log2[((((n/E)))^n)(Sqrt[2π n])]>(n+(1/2))Log2[n]-(n/(Log[2]))+(1/2)Log2[2 π]≈
(n+(1/2))Log2[n]-1.4426950408889634`n+1.3257480647361592`≈
(n+(1/2))Log2[n]-1.443n+1.325

and

(∑_(i=1)^n)Log2[i] = Log2[n!] <Log2[((((n/E)))^n)(Sqrt[2π n])(1 + (1/(11n)))]<(n+(1/2))Log2[n]-(n/(Log[2]))+(1/2)Log2[2 π]+Log2[1 + (1/(11n))].
Since Log2[x] is a convex function of x (its derivative, (1/x)Log2[E] is a decreasing function of x), 
Log2[x+y]<Log2[x]+((Log2[E])/x)(y-x).
Hence, 
Log2[1 + (1/(11n))]<Log2[1]+((Log2[E])/1)(1+(1/(11n))-1)=
=((Log2[E])/(11n)).

N[((Log2[E])/(11n))]

0.1311540946262694`/n

So,
(n+(1/2))Log2[n]-1.4426950408889634`n+1.3257480647361592`+Log2[1 + (1/(11n))]<
(n+(1/2))Log2[n]-1.4426950408889634`n+1.3257480647361592`+((Log2[E])/(11n))=
=(n+(1/2))Log2[n]-1.4426950408889634`n+1.3257480647361592`+0.1311540946262694`/n<
<(n+(1/2))Log2[n]-1.442n+1.326+(0.132/n)

More tricky sums

(∑_(i=1)^n)⌊Log2[i]⌋

Important approximation:

(∑_(i=1)^n)⌊Log2[i]⌋≈n Log2[n] - 1.9n  +4.7

Plot[Tooltip[{(∑_(i=1)^n)⌊Log2[i]⌋,n Log2[n] - 1.9n  +4.7}], {n, 1, 20}]

The exact value:

(∑_(i=1)^n)⌊Log2[i]⌋=(n+1)⌊Log2[n]⌋-(2^(⌊Log2[n]⌋+1))+2

Plot[Tooltip[{(∑_(i=1)^n)⌊Log2[i]⌋,(n+1)⌊Log2[n]⌋-(2^(⌊Log2[n]⌋+1))+2}], {n, 1, 20}]

Also,

(∑_(i=1)^n)⌊Log2[i]⌋=(n+1)⌊Log2[n+1]⌋-(2^(⌊Log2[n+1]⌋+1))+2=

[The above is Knuth's formula]

=(n+1) (Log2[n+1]+ϵ[n+1])-2 n

where

β[x_]:=1+x-(2^x)

θ[x_]:=⌈x⌉-x

ϵ[x_]:=β[θ[Log2[x]]]

Plot[Tooltip[{(∑_(i=1)^n)⌊Log2[i]⌋,(n+1)⌊Log2[n+1]⌋-(2^(⌊Log2[n+1]⌋+1))+2+.5 (* + .5 added to see separate lines*), (n+1) (Log2[n+1]+ϵ[n+1])-2 n}], {n, 1, 20}]

Plot[Tooltip[{(∑_(i=1)^n)⌊Log2[i]⌋,(n+1)⌊Log2[n+1]⌋-(2^(⌊Log2[n+1]⌋+1))+2+1.5 (* + 1.5 added to see separate lines*), (n+1) (Log2[n+1]+ϵ[n+1])-2 n}], {n, 1000, 1020}]

Here is a plot of function ϵ[n]

Plot[{ϵ[n],.0860,.5},{n,1,1000},AspectRatio->.13]

The rest of this file is optional

Approximation of sums of ceilings of logs:

(∑_(i=1)^n)⌈Log2[i]⌉≈n Log2[n] - 0.94n - 0.5

Plot[Tooltip[{(∑_(i=1)^n)⌈Log2[i]⌉, n Log2[n] - 0.94n - 0.5}], {n, 1, 20}]

The exact value:

(∑_(i=1)^n)⌈Log2[i]⌉ = (∑_(i=2)^n)⌈Log2[i]⌉ =(* by ⌊(Subscript[log, 2])k⌋+1=⌈(Subscript[log, 2])(k+1)⌉ *) (∑_(i=2)^n)(⌊Log2[i-1]⌋+1)=
(∑_(i=1)^(n-1))⌊Log2[i]⌋+n-1 =n⌊Log2[n-1]⌋-(2^(⌊Log2[n-1]⌋+1))+2+n-1 =n(⌊Log2[n-1]⌋+1)-(2^(⌊Log2[n-1]⌋+1))+1 =n(⌈Log2[n]⌉)-(2^(⌈Log2[n]⌉))+1

Also,

(∑_(i=1)^n)⌈Log2[i]⌉=(∑_(i=1)^(n-1))⌊Log2[i]⌋+n-1=
=n (Log2[n]+ϵ[n])-2 (n-1) +(n-1)=
=n (Log2[n]+ϵ[n])-n+1

So,

(∑_(i=1)^n)⌈Log2[i]⌉ = n(⌈Log2[n]⌉)-(2^(⌈Log2[n]⌉))+1

Plot[Tooltip[{(∑_(i=1)^n)⌈Log2[i]⌉,n(⌈Log2[n]⌉)-(2^(⌈Log2[n]⌉))+1}], {n, 1, 20}]

Also,

(∑_(i=1)^n)⌈Log2[i]⌉ = n(⌈Log2[n+1]⌉)-(2^(⌈Log2[n+1]⌉))+1

Plot[Tooltip[{(∑_(i=1)^n)⌈Log2[i]⌉,n(⌈Log2[n+1]⌉)-(2^(⌈Log2[n+1]⌉))+1}], {n, 1, 20}]

And

(∑_(i=1)^n)⌈Log2[i]⌉=n (Log2[n]+ϵ[n])-n+1

Plot[Tooltip[{(∑_(i=1)^n)⌈Log2[i]⌉,n (Log2[n]+ϵ[n])-n+1}], {n, 1, 20}]

Sum of floors of logs and sum of ceilings of logs plotted together:

Plot[Tooltip[{(∑_(i=1)^n)⌊Log2[i]⌋,(∑_(i=1)^n)⌈Log2[i]⌉}], {n, 1, 100},PlotPoints-> 200]

Their closed-form formulas plotted together:

Plot[Tooltip[{(n+1)⌊Log2[n+1]⌋-(2^(⌊Log2[n+1]⌋+1))+2,n(⌈Log2[n]⌉)-(2^(⌈Log2[n]⌉))+1}], {n, 1, 100},PlotPoints-> 200]

It follows from the above that

(∑_(i=1)^n)(⌈Log2[i]⌉-⌊Log2[i]⌋) = n-⌈Log2[n+1]⌉=n-⌊Log2[n]⌋-1

Plot[Tooltip[{(∑_(i=1)^n)(⌈Log2[i]⌉-⌊Log2[i]⌋),n-⌊Log2[n]⌋-1}], {n, 1, 50},PlotPoints-> 200]

DiscretePlot[n-⌊Log2[n]⌋-1,{n,1,50}]

The same using continuous functions:

Plot[Tooltip[{(∑_(i=1)^n)(⌈Log2[i]⌉-⌊Log2[i]⌋),-((n+1)⌊Log2[n+1]⌋-(2^(⌊Log2[n+1]⌋+1))+2)+(n(⌈Log2[n]⌉)-(2^(⌈Log2[n]⌉))+1)}], {n, 1, 50},PlotPoints-> 200]

Plot[Tooltip[{(∑_(i=1)^n)(⌈Log2[i]⌉-⌊Log2[i]⌋),-((n+1)⌊Log2[n+1]⌋-(2^(⌊Log2[n+1]⌋+1))+2)+(n(⌈Log2[n]⌉)-(2^(⌈Log2[n]⌉))+1)}], {n, 1, 150},PlotPoints-> 400]

Plot[Tooltip[{(∑_(i=1)^n)(⌈Log2[i]⌉-⌊Log2[i]⌋),n-Log2[n]-1}], {n, 1, 150},PlotPoints-> 300]