# Proofs

This entire course requires you to write proper mathematical proofs . All proofs should
be written elegantly in a formal mathematical style. Complete sentences of explanation
are required. Do not simply write an equation; you must explain what the equation is
giving
and/or why it is being used. Moreover, all equations must be properly aligned
with no scratch outs. Always give a conclusion.

We will begin by reviewing several standard methods of proof using the following
basic definitions and using the facts that the sum and product of integers are integers.

Divisibility: We say that a divides b if there exists an integer k such that b = ka . For
example, 6 divides 18 because 18 = 3 × 6 , where k = 3 is an integer.

Even Number: An integer n is said to be even if it has the form n = 2k for some integer
k . That is, n is even if and only if n divisible by 2.

Odd Number: An integer n is called odd if it has the form n = 2 k +1 for some integer k .

Prime Number: A natural number n > 1 is said to be prime if its only positive divisors are
1 and n . If n has other positive divisors, then n is called composite.

Rational Number : A real number x is called rational if x can be written as a fraction
m / n , where m and n are integers with n ≠ 0. Otherwise, x is called irrational.

Direct Proof

Consider the statements p , then q , and   At times we may try to
prove that these types of statements are true. To prove S1 directly, we assume p is
true and then argue that q must also be true. To prove S2 is true, we pick an arbitrary
x and argue that property p (x) must hold.

Example 1. Prove the following results directly:

(a) If n is an odd integer, then n2 +1 is even.
(b) If a divides b and b divides c , then a divides c .
(c) For all rational numbers x and y , the product x y is also a rational number.

Proof. (a) Assume n is an odd integer. Then n = 2 k +1 for some integer k . We then
have

n2 +1
= (2 k +1)2 + 1
= 4k2 + 4k + 2
= 2(2k 2 + 2k + 1)
= 2l ,

where l = 2k 2 + 2k + 1 is an integer because k is an integer. Thus, n2 +1 has the form
of an even number, and so n2 +1 is even.  QED

(b) Assume a divides b and b divides c . Then b = ka for some integer k , and c = jb
for some other integer j . Thus,

c = jb = j (ka) = ( jk )a .

Because the product of integers jk is still an integer, we have that a divides c . QED
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

(c) Let x and y be rational numbers. Then x = m / n and y = j / k for some integers m ,
n , j , and k , with n ≠ 0 and k ≠ 0 . Then

The products of integers m j and nk are still integers, and nk cannot be 0 because
neither n nor k is 0. Thus, x y is in the form of a rational number and therefore x y is
rational.  QED

Indirect Proofs

Given an implication , its contrapositive is ~ q → ~ p , which is logically
equivalent to the original implication. In order to prove that S is true, it might be easier
to prove that the contrapositive is true. That is, we can assume that q is not true, and
then argue that p is not true.

Another common method used to prove p → q is a proof by contradiction. In this
case, we assume that p is true but that q is not true. We then argue that a mathematical
contradiction occurs. We conclude that q in fact must be true.

Proof by Contrapositive
To prove p → q,
assume that q is not true,
then argue that p is not true.

To prove p → q,
assume that p is true but q is not true.
Then argue that a mathematical

Notes: (i) A logical statement is often a conjunction a ∧ b (a and b ) or a disjunction
a ∨ b (a or b ). We apply DeMorgan’s Laws to obtain the negations of these statements
as follows:

(ii) The negation of “ one or the other but not both” is given by “both or neither”.

(iii) A logical statement may be in terms of a quantifier such as “for every x , property
p(x ) holds.” The negation is “there exists an x for which p(x ) does not hold.”

Statement: Negation:

 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 April 21st 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!