Prove: Suppose n is an integer. If n^2 is even, then n is even.

Let \color{red}n be an integer. We want to show that whenever \large{\color{red}n^2} is even, then \large{\color{red}n} must be even.

suppose n is an integer. if n squared is an even number, then n is also an even number.

Just a heads-up, the result of this theorem is significant because it will help you prove a more important fact [in the future] that the square root of 2 is irrational. But, let’s disregard it for now.

The proof of the theorem above is actually very simple. But before we begin writing the proof, we will review some background knowledge that are relevant in proving the theorem in question.

◉ First, we need to describe how an even and odd numbers look like algebraically. I have separate lessons dedicated to even and odd numbers.

Remember that an even number can be expressed as 2k where k is an integer. For example, the number 6 is even since we can rewrite it as the product of 2 and some integer k. Thus, 6 = 2\left( k \right) \to 6 = 2\left( 3 \right).

On the other hand, an odd number can be expressed as 2k+1 or 2k-1 where k is just an integer. For instance, we can rewrite the odd number 13 as 13 = 2\left( 6 \right) + 1 or 13 = 2\left( 7 \right) - 1.

◉ Secondly, we need to know how to write the contrapositive of a statement. The reason is that if it is hard or impossible to prove a statement by direct proof, then the workaround is to prove its contrapositive. We can do this because they are logically the same.

So, for the conditional statement {\color{blue}p} \to {\color{red}q} (read as “p implies q”) its contrapositive is written as ~\color{red}q \to ~\color{blue}p (read as “not q implies not p”).


Observe how the contrapositive is constructed from the original statement.

  • The hypothesis {\color{blue}p} and the conclusion {\color{red}q} are swapped.
  • Then, the new hypothesis {\color{red}q} and the new conclusion {\color{blue}p} are both negated. The tilde symbol ~ is often used to denote negation.
p implies q is logically equivalent to not q implies not p

Again, this is how you read the statement and its contrapositive.

  • Statement: {\color{blue}p} \to {\color{red}q} is read as “p implies q”.
  • Contrapositive: ~\color{red}q \to ~\color{blue}p is read as “not q implies not p”.

Examples of the Contrapositive of a Conditional Statement

Example 1

Statement: If you live in Dallas, Texas, then you live in the United States.

Contrapositive: If you don’t live in the United States, then you don’t live in Dallas, Texas.

Example 2

Statement: If a number is divisible by 2, then the number is even.

Contrapositive: If a number is odd, then the number is not divisible by 2.

Example 3

Statement: If a polygon has four sides, then it is a quadrilateral.

Contrapositive: If it is not a quadrilateral, then the polygon does not have four sides.


As you already know, a statement and its contrapositive are logically equivalent. That means if the conditional statement is true, its contrapositive is also true. On the other hand, if the conditional statement is false, its contrapositive must also be false. Thus, the conditional statement and its contrapositive are either both true or both false. This is what it means to be logically equivalent.

the statement p implies q is logically equivalent to its contrapositive which is not q implies not p

So here’s the main takeaway.

Proving the contrapositive of a statement is logically the same as proving the statement itself.


BRAINSTORM BEFORE WRITING THE PROOF

Equipped with the background knowledge that we discussed above regarding even and odd numbers, and the contrapositive of a statement, then we are ready to tackle the proof.

Here is the theorem again that we want to prove.

  • Suppose \color{red}n is an integer.

It is impossible to prove the statement as it stands, therefore we need a different strategy to approach this. In fact, we should always consider proof by contrapositive if the direct proof of the original statement seems to be difficult. Remember, proving the contrapositive of a statement is logically the same as proving the original statement.

Since the original statement is

  • If n^2 is even, then n is even.

The contrapositive is

  • If n is not even, then n^2 is not even.

But there is a better way of saying “not even”. If you think about it, the opposite of an even number is odd number.

Rewrite the contrapositive as

If n is odd, then n^2 is odd.

Since n is odd (hypothesis), we can let n = 2k + 1 for some integer k. Then we are going to square it as the conclusion suggests, and show that it is odd.

Is the square of an odd number or 2k + 1 also an odd number? Let’s do the math.

{\left( {2k + 1} \right)^2} = 4{k^2} + 4k + 1

Factor out \color{red}2 from the first two terms of the trinomial which are 4{k^2} and 4{k}.

4{k^2} + 4k + 1 = {\color{red}2}\left( {2{k^2} + 2k} \right) + 1

Focus your attention to the algebraic expression inside the parenthesis which is {2{k^2} + 2k}. Since k is some integer, then both {2{k^2}} and {2k} are integers as well. Adding them together, {2{k^2} + 2k}, we get a sum that is also an integer.

The reason why we made those claims is because of the fact that the set of integers is close under the operations of addition and multiplication. In other words, we made those justifications using the Closure Properties of Addition and Multiplication over the set of integers. The symbol for the set of integers is \mathbb{Z}.

Since we established that {2{k^2} + 2k} is also integer, we can let {2{k^2} + 2k} equal to r where r is just another integer. Thus, r = 2{k^2} + 2k

Now, we can safely substitute the expression {2{k^2} + 2k} inside the parenthesis by r.

4{k^2} + 4k + 1 = {\color{red}2}\left( {2{k^2} + 2k} \right) + 1

4{k^2} + 4k + 1 = {\color{red}2}\left( {r} \right) + 1

The right hand side (RHS) of the equation which is 2r + 1 is an odd number by definition. We have reached our goal to show that the square of an odd number, {\left( {2k + 1} \right)^2}, is also odd.


WRITE THE PROOF

THEOREM: Let n be an integer. If n^2 is even, then n is even.

PROOF: We will prove this theorem by proving its contrapositive. The contrapositive of the theorem: Suppose n is an integer. If n is odd, then n^2 is odd. Since n is odd then we can express n as n = 2{\color{red}k} + 1 for some integer \color{red}k. Next, we square n, thus {n^2} = {\left( {2k + 1} \right)^2}. Expand the square of the binomial {\left( {2k + 1} \right)^2} to get {\left( {2k + 1} \right)^2} = 4{k^2} + 4k + 1. Factor out 2 from the first two terms of the trinomial, we have 4{k^2} + 4k + 1 = 2\left( {2{k^2} + 2k} \right) + 1. Since k is an integer, then {2{k^2} + 2k} must also be an integer by the Closure Property of Addition and Multiplication over the set of integers (\mathbb{Z}). Let r = 2{k^2} + 2k, thus 2\left( {2{k^2} + 2k} \right) + 1 becomes 2r + 1 which is clearly an odd number. Since we proved the contrapositive to be true, then the original statement must also be true. Therefore, we have proved that if n^2 is even, then n is even.◼︎


You might also be interested in:

Prove: Suppose n is an integer. If n^2 is odd, then n is odd.