# Math Camp Notes: Basic Proof Techniques

Basic notation:

• A => B . A implies B.

• A B. B implies A. Note that A=> B does
not imply B=> A. Example: If (A) a person eats two

hot dogs, she also (B) eats one hot dog. However, if (B) a person eats one hot
dog, that does not

implie that she also (A) eats two hot dogs.

• A B. A implies B and B implies A. Another
way of saying this is that A holds if and only if (iff )

B holds, or that A is equivalent to B .

• ¬A. Not A, or the negation of A. Example: If A is the event that x ≤ 10,
then ¬A is the event that

x > 10.

We seek for ways to prove that A=> B.

**Direct Proofs
Deductive Reasoning**

A direct proof by deductive reasoning is a sequence of accepted axioms or theorems such that

, where and . The difficulty is finding a sequence of theorems or

axioms to fill the gaps.

Example:

Prove the number three is an odd number.

Proof: Any number q is odd if there exists an integer m such that q = 2m+1. Let m = 1. Then three is an

odd number.

**Contrapositive**

A contrapositive proof is just a direct proof of the negation. If we want to prove that A => B, then we can

prove that ¬B => ¬A. For example, if (A) all people with driver's licenses are (B) at least 16 years old, then

if you are not (¬B) 16 years old, then you do not (¬A) have a driver's license. Or at least we hope .

Example:

Prove that is xy > 9, then either x > 3 or y > 3.

Proof: Suppose that both x ≤ 3 and y ≤3. Then xy ≤9.

**Indirect Proofs**

Contradiction

Contradiction

Suppose that we are trying to prove a proposition A, and we cannot prove it directly. However, we can

show that all other alternatives to A are impossible. Then we have indirectly proved that A must be true.

Therefore, the we can prove A => B by first assuming that and finding a contradiction.

In other words, we start o by assuming that A is true but B is not. If this leads to a contradiction, then

either B was actually true all along, or A was actually false. But since we assume A is true, then it must be

that B is true, and we have a proof by contradiction.

Example: Prove that is an irrational number.

Proof: Suppose not. Then is a rational number , so it can be expressed in the form , where p and q are

integers which are not both even. This implies that

which implies that p^{2} is even, which in turn implies that
q^{2} is not even. The fact that p^{2} is even also implies

that p is even, so there exists a integer m such that 2m = p. This implies

which means that q is even, a contradiction.

**Induction**

Induction can only be used for propositions about integers or indexed by
integers. Consider a list of state-

ments indexed by the integers. Call the first statement P(1), the second P(2),
and the nth statement P(n).

If we can prove the following two statements about the sequence, then every
statement in the entire sequence

must be true:

1. P(1) is true.

2. If P(k) is true, then P(k + 1) is true.

Induction works because by 1., P(1) is true. By 2., P(2) is true since P(1) is
true. Then P(3) is true by 2.

again, and so is P(4) and P(5) and P(6), until we show that all the P's are
true. Notice that the number

of propositions need not be finite.

Example:

Prove that the sum of the first n natural numbers is
.

Proof: Let n = 1. Then . Now let n = k, and
assume that .

We add k + 1 to both sides to get

**Proof Notation**

It is common to use mathematical symbols for words while writing proofs in order
to write faster. The

following are commonly used symbols :

For all, for any

There exists

Is contained in, includes as an element

Such that, is contained in (other way)

Is a subset of

**Homework**

Prove the following by direct proof.

1. n(n + 1) is an even number.

2. The sum of the first n natural numbers is .

3. If 6x + 9y = 101, then either x or y is not an integer.

Prove the following by contrapositive.

1. n(n + 1) is an even number.

2. If x + y > 100, then either x > 50 or y > 50.

Prove the following by contradiction.

1. n(n + 1) is an even number.

2. is an irrational number.

3. There are in finitely many prime numbers.

Prove the following by induction.

1. n(n + 1) is an even number.

2. 2n ≤ 2^{n}.

3. .

4. The sum of the first n odd integers is n^{2} (This is the first known proof by
mathematical induction,

attributed to Francesco Maurolico. Just in case you were interested.)

Find the error in the following argument, supposedly by induction:

If there is only one horse, then all the horses are of the same color. Now
suppose that within any set of n

horses, they are all of the same color. Now look at any set of n+1 horses.
Number them 1, 2, 3, . . . , n, n+1.

Consider the sets {1, 2, 3, . . . , n} and {2, 3, 4, . . . , n + 1}. Each set is
a set of n horses, therefore they are all

of the same color. But these sets overlap, therefore all horses are the same
color.

In first semester micro you will be introduced to preference relations . We say
that , (read x is weakly

preferred to y ) if x is at least as good as y to the agent. From this, we can
derive two important relations:

• The strict preference relation , , defined by
but not . The strict
preference

relation is read x is strictly preferred to y .

• The indifference relation, ~ , defined by
and . The indifference
relation is read x

is indifferent to y .

We say that a preference relation is rational if :

• x, y, either
or .

• x, y, z, if
and , then
.

Prove the following two statements given that preferences are rational:

1. If and , then
.

2. If x ~ y and y ~ z, then x ~ z.

Prev | Next |