Mathematics for Computer Science

13.7. Asymptotic Notation 545

(c)

Xn

iD 0

2 2iC^1

(d)

ln.n^2 Š/

(e)

Xn

kD 1

k



1

1

2 k



Problem 13.26. (a)Either prove or disprove each of the following statements.

nŠDO..nC1/Š/

.nC1/ŠDO.nŠ/

nŠD‚..nC1/Š/

nŠDo..nC1/Š/

.nC1/ŠDo.nŠ/

(b)Show that

n

3

nCe

Do.nŠ/.

Problem 13.27.
Prove that n
X

kD 1

k^6 D‚.n^7 /:

Hint:One solution uses the Integral Method, and there are other workable ap-
proaches that avoid calculus.

Class Problems

Problem 13.28.
Give an elementary proof (without appealing to Stirling’s formula) that log.nŠ/D
‚.nlogn/.

Problem 13.29.
Supposef;gWNC!NCandf g.