Page 172 - Discrete Mathematics and Its Applications

2.3 Functions 151

1
We first consider the case when 0 ≤ < . In this case, 2x = 2n + 2 and 2x = 2n
2
1 1 1 1
because 0 ≤ 2 < 1. Similarly, x + = n + ( + ),so x + = n, because 0 < + < 1.
2 2 2 2
1
Consequently, 2x = 2n and x + x + = n + n = 2n.
2
Next, we consider the case when 1 ≤ < 1. In this case, 2x = 2n + 2 =
2
(2n + 1) + (2 − 1). Because 0 ≤ 2 − 1 < 1, it follows that 2x = 2n + 1. Because
1 1 1 1 1
x + = n + ( + ) = n + 1 + ( − ) and 0 ≤ − < 1, it follows that x + =
2 2 2 2 2
1
n + 1. Consequently, 2x = 2n + 1 and x + x + = n + (n + 1) = 2n + 1. This con-
2
cludes the proof. ▲
EXAMPLE 30 Prove or disprove that x + y = x + y for all real numbers x and y.
Solution: Although this statement may appear reasonable, it is false. A counterexample is sup-
1 1 1 1
plied by x = and y = . With these values we find that x + y = + = 1 = 1, but
2 2 2 2
1
1
x + y = + = 1 + 1 = 2. ▲
2 2
There are certain types of functions that will be used throughout the text. These include
polynomial, logarithmic, and exponential functions. A brief review of the properties of these
functions needed in this text is given in Appendix 2. In this book the notation log x will be used
to denote the logarithm to the base 2 of x, because 2 is the base that we will usually use for
logarithms. We will denote logarithms to the base b, where b is any real number greater than 1,
by log x, and the natural logarithm by ln x.
b
Another function we will use throughout this text is the factorial function f : N → Z ,
+
denoted by f (n) = n!. The value of f (n) = n! is the product of the first n positive integers, so
f (n) = 1 · 2 ··· (n − 1) · n [and f(0) = 0!= 1].
EXAMPLE 31 We have f(1) = 1!= 1, f(2) = 2!= 1 · 2 = 2, f(6) = 6!= 1 · 2 · 3 · 4 · 5 · 6 = 720,
and f(20) = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 · 10 · 11 · 12 · 13 · 14 · 15 · 16 · 17 · 18 · 19 · 20 =
2,432,902,008,176,640,000. ▲
Example 31 illustrates that the factorial function grows extremely rapidly as n grows.
The rapid growth of the factorial function is made clearer by Stirling’s formula, a result from
√
n
higher mathematics that tell us that n!∼ 2πn(n/e) . Here, we have used the notation f (n) ∼
g(n), which means that the ratio f (n)/g(n) approaches 1 as n grows without bound (that is,
lim n→∞ f (n)/g(n) = 1). The symbol ∼ is read “is asymptotic to.” Stirling’s formula is named
after James Stirling, a Scottish mathematician of the eighteenth century.

JAMES STIRLING (1692–1770) James Stirling was born near the town of Stirling, Scotland. His family strongly supported the
Jacobite cause of the Stuarts as an alternative to the British crown. The first information known about James is that he entered Balliol
College, Oxford, on a scholarship in 1711. However, he later lost his scholarship when he refused to pledge his allegiance to the
British crown. The first Jacobean rebellion took place in 1715, and Stirling was accused of communicating with rebels. He was
charged with cursing King George, but he was acquitted of these charges. Even though he could not graduate from Oxford because
of his politics, he remained there for several years. Stirling published his first work, which extended Newton’s work on plane curves,
in 1717. He traveled to Venice, where a chair of mathematics had been promised to him, an appointment that unfortunately fell
through. Nevertheless, Stirling stayed in Venice, continuing his mathematical work. He attended the University of Padua in 1721,
and in 1722 he returned to Glasgow. Stirling apparently fled Italy after learning the secrets of the Italian glass industry, avoiding the
efforts of Italian glass makers to assassinate him to protect their secrets.
In late 1724 Stirling moved to London, staying there 10 years teaching mathematics and actively engaging in research. In 1730
he published Methodus Differentialis, his most important work, presenting results on infinite series, summations, interpolation, and
quadrature. It is in this book that his asymptotic formula for n! appears. Stirling also worked on gravitation and the shape of the
earth; he stated, but did not prove, that the earth is an oblate spheroid. Stirling returned to Scotland in 1735, when he was appointed
manager of a Scottish mining company. He was very successful in this role and even published a paper on the ventilation of mine
shafts. He continued his mathematical research, but at a reduced pace, during his years in the mining industry. Stirling is also noted
for surveying the River Clyde with the goal of creating a series of locks to make it navigable. In 1752 the citizens of Glasgow
presented him with a silver teakettle as a reward for this work.