Dr. J. Ramanathan, MTH 311: Problem Solving

Dr. J. Ramanathan, MTH 311: Problem Solving
1
Due: TBA
Handout 5
Notes and Problems
Stirling’s Formula
§ Discussions of asymptotic formulae, of which Stirling’s formula is an example, are greatly simplified by use of E. Landau’s big-O and little-o notation. We
introduce this in the special case of an positive integer variable tending to infinity.
Let sn , tn be a given sequences defined for n ∈ N. In addition, suppose
tn > 0 for all n ∈ N.
The sequence sn is big-O of tn (as n → ∞) if there is a constant C > 0 with
the property that
|sn | 6 Ctn
for all n ∈ N. This is denoted by the statement
sn = O(tn )
as n → ∞.
The sequence sn is little-O of tn as n → ∞ if
sn
= 0.
n→∞ tn
lim
This is denoted by the statement
sn = o(tn )
as n → ∞.
Question 1. Suppose tn is a positive sequence. Prove that the sequence sn is
big-O of tn if and only if there is a constant C > 0 and a positive integer N0 with
the property that
|sn | 6 Ctn
for all integers n > N0 .
Question 2. If sn is little-o of tn then sn is big-O of tn .
Question 3. Suppose αn and βn are both big-O of tn . Prove that αn + βn is
big-O of tn .
Dr. J. Ramanathan, MTH 311: Problem Solving
2
Question 4. Suppose tn and τn are positive sequences and that
αn = O(tn )
βn = O(τn ).
and
Prove that:
αn · βn = O(tn · τn ).
Question 5. Show that
ln(1 +
1
1
1
1
) = − 2 + O( 3 ).
n
n 2n
n
Question 6. Let
∞
X
1
.
L=
n2
n=1
Write δn for the error:
n
X
1
.
δn = L −
2
k
k=1
Prove that δn = O( n1 ).
P
Question 7. Suppose ∞
n=1 an is a series whose terms satisfy
|an | 6
C
n2
for some fixed constant C > 0 and all n ∈ N. Prove the following.
P
a. The series ∞
n=1 an converges absolutely.
P
b. Let L = ∞
n=1 an and
n
X
ǫn = L −
ak .
k=1
Prove that
c. What is limn→∞ ǫn ?
1
ǫn = O( )
n
Review
the Integral
Test and
p-series.
Dr. J. Ramanathan, MTH 311: Problem Solving
3
§ The proof of Stirling’s formula relies on applying the trapezoid rule to the logarithm function.
Question 8. What is the area of the trapezoid shown below?
H
h
w
§ From now on, let an denote the area of the shaded region in the diagram below:
y = ln(x)
x
n
n+1
Question 9. Show that:
1
1
an = (n + ) ln(1 + ) − 1.
2
n
Question 10. Prove:
an = O(1/n2 ).
§ Write
L=
∞
X
n=1
an
Dr. J. Ramanathan, MTH 311: Problem Solving
and
ǫn = L −
n
X
4
an .
k=1
Question 11. Show that
Zn
1
ln(x) dx = ln(n!) − ln(n) + L − ǫn .
2
1
Question 12. Prove that there is a constant κ > 0 that satisfies
1
1
ln(n!) = (n + ) ln(n) − n + κ + O( )
2
n
as n → ∞.
Question 13. Prove that there is a constant K > 0 that satisfies
Knn+1/2 e−n
−→ 1.
n!
as n → ∞.
Question 14. Prove that
24n (n!)4
(2n!!)2
=
.
((2n + 1)!!)((2n − 1)!!)
2n + 1 (2n!)2
Question 15. Show that the constant in Stirling’s formula K =
√
2π.
Question 16. Use Stirling’s formula and your favorite calculating device to get
an approximate value for 200!.
Question 17. In table form present n!, Stirling’s approximation and the percentage error for n = 1, . . . , 10.

Download Report