# Proof Methods

What is a proof?

Proofing as a social process, a communication art.

Theoretically, a proof of a mathematical statement is no
different than a logically valid argument starting with
some premises and ending with the statement. However,
in the real world such logically valid arguments can get so
long and involved that they lose their "punch" and require
too much time to verify.

In mathematics, the purpose of a proof is to convince
the reader of the proof that there is a logically valid
argument in the background. Both the writer and the
reader must be convinced that such an argument can be
produced – if needed.

Writing mathematical proofs is therefore an art form (the
art of convincing) and a social process since it is directed

A mathematical proof of a statement strongly depends
on who the proof is written for. Proofs for a research
audience are quite different from those found in
textbooks. And even textbook proofs look different
depending on the level of the audience (high school vs.

To simplify our task in this course, you will write all of
your proofs with a specific audience in mind:

ME!

That is, you are writing to convince me that you could
drop down to the logic level and provide all the details, if I

Rigor in proofs.

The above remarks should not be construed to mean that
requires clarity, precision and, above all, correctness.

Phrases such as "clearly" or "it is easy to see that" are
neither clear nor easy for this audience.

When you say something follows from a definition, I
want to know "the definition of what?"

General Hints

The importance of definitions.

It can not be overemphasized how important definitions
are. Without a clear and crisp understanding of a
definition, you will not be able to use it in a proof. You
have to be able to recall a definition precisely when it is
needed – vague familiarity will not work for you.

Working backwards.

There is a big difference between discovering a proof
and presenting a proof. In presenting a proof you must be
convincing, and things need to follow in a logical order .
To discover a proof, you are under no such restrictions
and often the best procedure is to work the problem
backwards.

Methods of Proof

We will survey the basic proof methods. In doing so, our
examples to illustrate the techniques should not be very
complicated ... so we will restrict them to fairly simple
statements which do not need a great deal of background
to understand.

The Theory of Numbers provides an excellent source
for such examples ... so most of our examples will deal
with numbers in this section. Remember that our aim is
the examples will be statements that you know are true,
rather we are interested in the way that the proofs are
constructed... so, concentrate on the techniques.

Direct Proof

 In a direct proof one starts with the premise (hypothesis) and proceed directly to the conclusion with a chain of implications. Most simple proofs are of this kind.

Definitions:
An integer n is odd iff there exists an integer k so that n = 2k+1.
An integer n is even iff there exists an integer k so that n = 2k.

Example of a direct proof:
If n is an odd integer then n2 is odd.

Pf: Let n be an odd integer.
There exists an integer k so that n = 2k+1.

Since 2k2 + 2k is an integer, n2 is odd.

Contrapositive Proof

 When proving a conditional, one can prove the contrapositive statement instead of the original – this is called a contrapositive proof.

Example:
If n2 is an odd integer, then n is odd.

Pf: Suppose n is an even integer.
There exists an integer k so that n = 2k.

Since 2k2 is an integer, n2 is even.

This proof method is based on the Law of the Excluded Middle.
Essentially, if you can show that a statement can not be false, then
it must be true. In practice, you assume that the statement you are
trying to prove is false and then show that this leads to a

This method can be applied to any type of statement, not just
conditional statements.

There is no way to predict what the contradiction will be.

The method is wide-spread and is often found in short segments
of larger proofs. For example, ...

Another Contrapositive Proof

Definition: An integer n divides an integer m, written n|m, iff there exists an
integer k so that m = nk.

Example:
If A and B are integers and B ≠ 0. Show that if A
divides B then |A| ≤ |B|.

Pf: Suppose that |A| > |B|. (Note that A ≠ 0.)
Then 1 > |B|/|A| > 0.
If A | B then there is an integer k so that B = Ak.
k = B/A and the integer |k| = |B|/|A|.
But, there is no integer 1 > |k| > 0.
So A does not divide B.

Definition: A real number r is rational iff it can be written as r = a/b with a
and b integers and b ≠ 0. A real number is irrational if it is not rational.

Example:
The is irrational.

Pf: BWOC assume that is rational .
There exist integers p and q so that = p/q.
We may assume that the fraction is reduced ,
i.e. no integer divides both p and q.
, so p2 is even.
Thus, p is even.

is irrational

There exists an integer k so that p = 2k.

So, q2 is even and therefore q is even.
Since 2 divides both p and q we have a contradiction

So, is not rational.

This proof is due to Euclid, but the theorem dates back to
Pythagoras and the Pythagoreans.

Proofs of Biconditionals

 proof of a statement usually uses the tautology That is, we prove an iff statement by seperately proving the "if" part and the "only if" part.

Example:
Integer a is odd if and only if a+1 is even.

Pf: (Sufficiency, if a is odd then a+1 is even)
Suppose a is an odd integer.
There exists an integer k so that a = 2k + 1.
a+1 = (2k+1) + 1 = 2k+2 = 2(k+1)
Since k+1 is an integer, a+1 is even.

Example:
Integer a is odd if and only if a+1 is even.

Pf: (Necessity, if a+1 is even then a is odd)
Suppose a+1 is an even integer.
There exists an integer k so that a+1 = 2k.
a = a + 1 – 1 = (2k) - 1 = (2(k-1) + 2) – 1 = 2(k-1) + 1
Since k-1 is an integer, a is odd.

Uniqueness Proofs

Proofs of existentially quantified statements () can be
constructive – in which case you produce an x which makes P(x)
true, or non-constructive – when you use contradiction to show
that ~() is false.

Definition: To say that there is one and only one x which makes
the predicate P(x) true, we write () (there exists a unique
x such that P(x)).

 To prove a () statement, we first prove () and then show that if P(x) and P(y) are both true, we must have x = y.

Definition: Let a and b be two positive integers. If n is a positive integer and a|n
and b|n, then we call n a common multiple of a and b. If n is a common multiple
of a and b, and if for every other common multiple , m, of a and b we have that
n|m, we say that n is a least common multiple of a and b. In this case, we write
n = LCM(a,b).

Example:
For all positive integers a and b, LCM(a,b) is unique.

Pf: (We shall omit the proof of the existence of the LCM and just show it's
uniqueness, assuming that it exists.)
Let a and b be positive integers.
Suppose m1 and m2 are two LCM's for a and b.

Since m1 is an LCM and m2 is a common multiple, m1|m2, so m1 ≤ m2.
Since m2 is an LCM and m1 is a common multiple, m2|m1, so m2≤ m1.
Therefore, m1 = m2.

 Prev Next

Start solving your Algebra Problems in next 5 minutes!

2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of June 13th you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:

Step 2 : Let Algebra Helper solve it:

Step 3 : Ask for an explanation for the steps you don't understand:

Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!