3.

4 Estimates

Sometimes, computing an exact value of something is possible but laborious,

and sometimes, it is impossible.

Hence, heading for an estimate instead of the exact value save us lots of work
and considerably enlarge the range of problems we are able to cope with.
[Example 3.4.1] The following sum appears quite often in mathematics and computer
science:

n
1 1 1 1
n ∑
Hn = 1 + + + ⋯ + =
2 3 i=1
n

This Hn is called the n-th harmonic number.

It turns out that there is no way to simplify this sum (no closed form)

We want to get som idea about the behavior of Hn for n growing to ∞.

 { 2k−1 2k−1 + 1 2k − 1 }
1 1 1 k−1
Let Gk = , , …, . It contains 2 numbers.

k−1 1
∑
Observe that x ≤ | Gk | max Gk = 2 = 1 and
x∈Gk
2k−1

k−1 1 1
∑
x ≥ | Gk | min Gk > 2 = .
x∈G
2 k 2
k

n ⌊log2 n⌋+1
1
∑i ∑
Therefore, we get Hn = ≤ 1 ≤ log2 n + 1 and
i=1 k=1
⌊log2 n⌋+1
1 1
∑
Hn > ≥ ⌊log2 n⌋
k=1
2 2
We can conclude that Hn does grow to infinity but slowly as the logarithm function.
We can conclude that Hn does grow to infinity but slowly as the logarithm function.

Even for very large value of n, we can estimate the value of Hn

by computing the logarithm.
Asymptotic comparison of functions.

Functions defined on the natural numbers are usually compared

according to their behavior as n tends to infinity.
This approach is usually called the asymptotic analysis of the considered functions.

[Definition 3.4.2] Let f, g : ℕ → ℝ be functions.

We say that f(n) = O(g(n)) if there exist constant n0 and C such that
for all n ≥ n0, | f(n) | ≤ C ⋅ g(n) holds.

We say that ‘f is big-Oh of g’.

2 2
Ex) 10n + 5n = O(n )
2 3 8 5
(7n + 6n + 2)(n − 3n + 2 ) = O(n ).
After some practicing, one can write estimates without too much thinking,
by quickly spotting the ‘main terms’ in an expression. Such insight is usually
based on a use of the following simple rules.

[Fact 3.4.3] Let C, a, α, β > 0 be reals.

α β
(1) n = O(n ) whenever α ≤ β.

C n
(2) n = O(a ) for any a > 1.

C α
(3) (ln n) = O(n )
Using the symbol O(), we can also write a more exact comparison of two function.

For example,
f(n) = g(n) + O( n) means that
f is the same as g up to an ‘error’ of the order n

(2)
2
n n
Ex) = + O(n).
2
We define most common symbols below

- f(n) = Ω(g(n)) if g(n) = O( f(n)).

- f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n))

f(n)
- f(n) = o(g(n)) if lim =0
n→∞ g(n)

( f grows much more slowly than g )

f(n)
- f(n) ∼ g(n) if lim =1
n→∞ g(n)

( f and g are almost the same )

3.5 Estimates: the factorial function

We estimate the function n! = n ⋅ (n − 1) ⋅ ⋯ ⋅ 2 ⋅ 1.

For all small values of n, n! can be quickly evaluated by a computer.

But one might think that the values of the factorial are too large
to have any significance in the real world.

100
For example, 70! > 10 .

In various mathematical considerations, we often need to compare

the order of magnitude of n! to other functions, even for very large values of n.
A simple calculation:

n n−1
∏ ∏
n! ≤ n≤n n! ≥ 2≥2 .
1≤i≤n 2≤i≤n

( 2 )
n
n/2 n + 1
Gauss had a better idea : n ≤ n! ≤ (Theorem 3.5.2)

We may keep asking more and more questions, such as whether

( 2 )
n
n+1

goes to infinity when n → ∞.

n!
We use the Euler number e

x
[Fact 3.5.4] For every real x, 1 + x ≤ e .

(e) (e)
n n
n n
[Theorem 3.5.5] Let n ∈ ℕ. e ≤ n! ≤ en

(e)
n
n
More precisely , we know n! ∼ 2πn (right is called Stirling’s formula)

( 2 )
n
n+1

So, lim = 0.
n→∞ n!
 (e) (e)
n n
n n
[Theorem 3.5.5] Let n ∈ ℕ. e ≤ n! ≤ en

(e)
n
n
PF) First prove by induction on n that n! ≤ en . True when n = 1.

Assume n ≥ 2.

( e )
n−1
n−1
n! = n(n − 1)! ≤ ne(n − 1)

[ (e) ] ( n )
n n
n n−1
= en e

( n )
n
n−1
It suffices to show that e ⋅ ≤1
 (e) (e)
n n
n n
[Theorem 3.5.5] Let n ∈ ℕ. e ≤ n! ≤ en

( n )
n
n−1
PF) Claim that e ⋅ ≤1

1 − 1n
We know 1 − ≤ e
n

( n)
n
1
≤ e (e ) = 1, as required.
1
n
−n
Thus, e 1 −

(e)
n
n
We conclude n! ≤ en .
 (e) (e)
n n
n n
[Theorem 3.5.5] Let n ∈ ℕ. e ≤ n! ≤ en

(e)
n
n
PF) We prove by induction on n that e ≤ n! . True when n = 1.

Assume that n ≥ 2.

( e ) [ (e) ] ( n )
n−1 n n−1
n−1 n n−1
n! = n(n − 1)! ≥ n ⋅ e = e e

( n )
n−1
n−1
It suffices to show that e ≥ 1.
 ( n )
n−1
n−1
Claim that e ≥ 1.

n−1
n−1

(e )
n−1

( )
1 1 1 1
e n =e ≥e = e ⋅ = 1.
n−1 1+ 1 1
n−1 e
n−1

(e)
n
n
We conclude that e ≤ n!.
3.6 Estimates: binomial coefficients

(k) (k)
n n k
From the definition of , we have ≤n .

For many applications, this estimate is still good.

(k) ( k )
k
n n n−i n
A lower bound is ≥ , as ≥ .
k−i k

Quite good lower and upper bounds can be obtained from Stirling’s formula.
But these bounds are somewhat cumbersome for calculation, and
we have not proved Stirling’s formula.

We prove a good but less accurate estimates by a simpler method.

 (k) ( k )
k
n en
[Theorem 3.6.1] Let n, k ∈ ℕ with 1 ≤ k ≤ n. Then ≤ .

(0) (1) (k) ( k )

k
n n n en
PF) We prove a stronger inequality: + +⋯+ ≤

(0) (1) (k)

n n n k n
From the binomial theorem, we get + x+⋯+ x ≤ (1 + x) .

Assume 0 < x < 1.

x k ( 0 ) x k−1 ( 1 ) (k)
n
k 1 n 1 n n (1 + x)
Dividing by x , we get + + ⋯ + ≤
xk
Replacing the coefficients by 1, we get a smaller value. So,

(0) (1) (k)

n
n n n (1 + x)
+ +⋯+ ≤
xk

We choose x properly so that the right-hand side is smalle.

(0) (1) (k)
n
n n n (1 + x)
+ +⋯+ ≤
xk

(0) (1) (k) ( n) (k)

n k
k n n n k n
Put x = . Then + +⋯+ ≤ 1+
n

( n)
n
k
By Fact 3.5.4, we get 1 + ≤ (e ) = e .
k/n n k

So, the result follows.

Here we used the idea of ‘generating functions’.

We will explore more in Chapter 12.
3.7 Inclusion-exclusion principle

The town has 3 clubs.

The lawn-tennis club (T) has 20 members,
the chandelier collector club (C) has 15 members, and
the Egyptology club (E) has 8 members.

There are 2 tennis players and 3 chandelier collectors among Egyptologists,

6 people both playing tennis and collect chandeliers, and
there is even one especially eager person participating in all three clubs.

How many people are engaged in the club?

|C ∪ T ∪ E| = |C| + |T| + |E| − |C ∩ T| − |C ∩ E| − |T ∩ E| + |C ∩ T ∩ E|

This idea woks for n sets.

| A1 ∪ ⋯ ∪ An | = | A1 | + . . . − | A1 ∩ A2 | − . . .

There is a clear way of expressing such a simple rule.

[Theorem 3.7.2 (Inclusion-exclusion principle)]

Let A1, …, An be a collection of finite sets.
n n
k−1
⋃ ∑ ∑ ⋂
Then Ai = (−1) Ai
i=1 k=1 I⊆( k )
{1,…, n} i∈I
[Theorem 3.7.2 (Inclusion-exclusion principle)]
Let A1, …, An be a collection of finite sets.
n n
k−1
⋃ ∑ ∑ ⋂
Then Ai = (−1) Ai .
i=1 k=1 I⊆( k )
{1,…, n} i∈I

PF) Let x ∈ A1 ∪ ⋯ ∪ An.

It contributes exactly 1 to the left-hand side.
Let j be the number of sets containing x.
For convenience, let B1, …, Bj be the sets containing x among A1, …, An.

x appears in the intersection of every k-tuple of sets among B1, …, Bj.

(2) (3) ( j)
j j j−1 j
x contributes : j − + ⋯ + (−1) . By the binomial coefficient, this is 1.