Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

0.2: Introduction to Proofs/Contradiction

( \newcommand{\kernel}{\mathrm{null}\,}\)

In this section, we will explore different techniques of proving a mathematical statement "If p then q." (pq).

Direct Proof

In this technique, we shall assume p and show that q is true.

Theorem 0.2.1

Let n be an integer. If n is even then n2 is even.

Proof

Assume that n is even. Then n=2m for some integer m.

Consider n2=(2m)2=4m2=2(2m2). Since m is an integer, (2m2) is an integer.

Thus n2 is even.

Example 0.2.1

Show that for all integers n, if n is odd then n2 is odd.

Answer

Assume that n is odd. Then n=2m+1 for some integer m.

Consider n2=(2m+1)2=4m2+4m+1=2(2m2+2m)+1.

Since m is an integer, (2m2+2m) is an integer.

Thus n2 is odd.

Proof by Contrapositive

In this technique, we shall assume ¬p and show that ¬q is true.

Theorem 0.2.2

Let n be an integer. If n2 is even then n is even.

Proof

We shall prove this statement by assuming n is odd. Then n=2m+1 for some integer m.

Consider n2=(2m+1)2=4m2+4m+1=2(2m2+2m)+1.

Since m is an integer, (2m2)+2m is an integer.

Thus n2 is odd.

Example 0.2.2

Show that for all integers n, if n2 is odd then n is odd.

Answer

We shall prove this statement by assuming n is even. Then n=2m for some integer m.

Consider n2=(2m)2=4m2=2(2m2).

Since m is an integer, (2m2) is an integer. Thus n2 is even.

Proof by Contradiction

In this technique, we shall assume the negation of the given statement is true and come to a contradiction.

Theorem 0.2.3

2 is irrational.

Proof

Assume that 2 is rational. Then 2=ba, where bZ,aZ{0}, with no common factors between a and b. Now, 2a=b. Then 2a2=b2. Since 2 divides 2a2, 2 divides b2. Thus b2 is even. Therefore, b is even (by theorem 2). Since b is even, 2 divides b. Therefore, 22 divides b2.

Since 2a2=b2, 22 divides 2a2. Therefore, 2 divides a2. Which implies a is even. This contradicts the fact that a and b have no common factors. Thus 2 is irrational.

Proof by Counterexample

Example 0.2.3:

Decide whether the statement is true or false and justify your answer:

For all integers a,b,u,v, and u0,v0, if au+bv=0 then a=b=0.

Solution: The statement is false.

Counterexample: Choose a=1,b=1,u=2,v=2, then au+bv=0, but a0.b0,ab.

Proof by induction

In mathematics, we use induction to prove mathematical statements involving integers. There are two types of induction: regular and strong. The steps start the same but vary at the end. Here are the steps. In mathematics, we start with a statement of our assumptions and intent:

Let p(n)nn0,n,n0Z be a statement. We would show that p(n) is true for all possible values of n.

  1. Show that p(n) is true for the smallest possible value of n: In our case p(n0). AND
  2. For Regular Induction: Assume that the statement is true for n=k, for some integer kn0. Show that the statement is true for n = k + 1.

OR

For Strong Induction: Assume that the statement p(r) is true for all integers r, where n0rk for some kn0. Show that p(k+1) is true.

If these steps are completed, and the statement holds, we are saying that, by mathematical induction, we can conclude that the statement is true for all values of nn0.

Example 0.2.4:

Prove that 1+2+...+n=n(n+1)2,nZ.

Solution:

Base step: Choose n=1. Then L.H.S =1 and R.H.S =(1)(1+1)2=1

Induction Assumption: Assume that 1+2+...+k=k(k+1)2, for kZ.

We shall show that 1+2+...+k+(k+1)=(k+1)[(k+1)+1]2=(k+1)(k+2)2

Consider, 1+2+...+k+(k+1)=k(k+1)2+(k+1)=(k+1)(k2+11)=(k+1)(k+22)=(k+1)(k+2)2.

Thus, by induction we have 1+2+...+n=n(n+1)2,nZ.

Example 0.2.5

Prove   for .

Solution

Let . Then is true, since clearly . Thus, the statement is true for .

Assume that is true for some .

We will show that .

Consider .

Since and , we have .

Thus the statement is true for all .

By induction, for all .◻


This page titled 0.2: Introduction to Proofs/Contradiction is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.

Support Center

How can we help?