Principles of Mathematics in Operations Research

1.3 The art of making proofs 7

of generality, we can fix an object with the property. If we can show that

something happens for this particular object, we can generalize the result for

all the objects with the same property.

Proposition 1.3.2 Let T C S C R, and u be an upper bound for S; i.e.

Va; £ S, x < u. Then, u is an upper bound for T.

Proof. Let u be an upper bound for S, so Vx £ S, x < u. Take any element

yoiT.TCS=>y£S=>y<u. Thus, Vy £ T, y < u. Then, u is an upper

bound for T. D

Uniqueness

When statement B has the word unique in it, the proposition is more re-

strictive. We should first show the existence then prove the uniqueness. The

standard way of showing uniqueness is to assume two different objects with

the property and to conclude that they are the same.

Proposition 1.3.

W £ R+, 3 unique i£R3i^3 = r.

Proof. Existence: Let y = r 3 , 1/6K.

Uniqueness: Let x, y £ M 3 x ^ y, x^3 = r = y^3 => x^3 — y^3 — 0 =>

(a; — y){x^2 + xy + y^2 ) = 0 => (x^2 + xy + y^2 ) = 0, since x ^ y. The roots of

the last equation (if we take y as parameter and solve for a;) are

-y ± \Jv^2 - V = -y ± \/-3y^2

2 2

Hence, y = 0 => y^3 — 0 = r g R+. Contradiction. Thus, x = y. •

1.3.2 Induction Method

Proofs of the form "for every integer n > 1, something happens" is made
by induction. Formally speaking, induction is used when B is true for each
integer beginning with an initial one (n 0 ). If the base case (n = n 0 ) is true,
it is assumed that something happens for a generic intermediate case (n =
nk). Consequently, the following case (n = n^+i) is shown, usually using the
properties of the induction hypothesis (n — nk). In some instances, one may
relate any previous case (nj, 0 < / < k). Let us give the following example.

Theorem 1.3.

1 + 2 + • • • + n — > k = —^ -.

r-f 2