1.7 Simple Deductive Proof

1. The Difference Between Symbols $=$ and $\equiv$

Consider the relation $3x = 6$. It holds only for a particular value $x=2$. This is an Equation.

Consider the relation $2(x+3) \equiv 2x+6$. It holds for any value of $x$. This is an Identity.

The symbol $\equiv$ emphasizes this "stronger" relation.

Example: It is easy to check that $\dfrac{1}{4} + \dfrac{1}{12} = \dfrac{1}{3}$. This is a specific instance of the general identity:

$$\dfrac{1}{m+1} + \dfrac{1}{m^2+m} \equiv \dfrac{1}{m}$$

2. Proof of an Equality (or Identity)

To prove $A = B$, three techniques are commonly used:

  • Method A: Start from $\text{LHS} \implies \dots \implies \text{RHS}$.
  • Method B: Work independently: $\text{LHS} \implies \dots \implies C$ and $\text{RHS} \implies \dots \implies C$.
  • Method C: Use equivalence: $A=B \iff \dots \iff \text{True Statement}$.

Method A Example

Prove $(a+b)^3 \equiv a^3 + 3a^2b + 3ab^2 + b^3$.

Proof: Start from LHS:

$$\begin{aligned} (a+b)^3 &= (a+b)^2(a+b) \\ &= (a^2+2ab+b^2)(a+b) \\ &= a^3 + a^2b + 2a^2b + 2ab^2 + ab^2 + b^3 \\ &= a^3 + 3a^2b + 3ab^2 + b^3 \quad (= \text{RHS}) \end{aligned}$$

Method B Example

Prove $(2a+b)^2 - 4a^2 - b^2 \equiv (a+b)^2 - (a-b)^2$.

Proof:

$$\begin{aligned} \text{LHS} &= 4a^2 + 4ab + b^2 - 4a^2 - b^2 = 4ab \\ \text{RHS} &= (a^2 + 2ab + b^2) - (a^2 - 2ab + b^2) = 4ab \end{aligned}$$

Therefore, $\text{LHS} = \text{RHS}$.

Method C Example

Given $a \ne \pm b$, show that $\dfrac{a-2b}{a-b} \equiv \dfrac{a^2-ab-2b^2}{a^2-b^2}$.

Proof:

$$\begin{aligned} \dfrac{a-2b}{a-b} &= \dfrac{a^2-ab-2b^2}{a^2-b^2} \\ \iff (a-2b)(a^2-b^2) &= (a-b)(a^2-ab-2b^2) \\ \iff a^3 - ab^2 - 2a^2b + 2b^3 &= a^3 - a^2b - 2ab^2 - a^2b + ab^2 + 2b^3 \\ \iff 0 &= 0 \quad (\text{True}) \end{aligned}$$

EXAMPLE 1

Prove $\dfrac{1}{m+1} + \dfrac{1}{m^2+m} \equiv \dfrac{1}{m}$.

Solution: From LHS to RHS.

$$\begin{aligned} \text{LHS} &= \dfrac{1}{m+1} + \dfrac{1}{m(m+1)} \\ &= \dfrac{m}{m(m+1)} + \dfrac{1}{m(m+1)} \\ &= \dfrac{m+1}{m(m+1)} \\ &= \dfrac{1}{m} \quad (= \text{RHS}) \end{aligned}$$

EXAMPLE 2

Show that $2x^2 - 12x + 19 \equiv 2(x-3)^2 + 1$.

Solution: Work from RHS to LHS.

$$\begin{aligned} \text{RHS} &= 2(x^2 - 6x + 9) + 1 \\ &= 2x^2 - 12x + 18 + 1 \\ &= 2x^2 - 12x + 19 \quad (= \text{LHS}) \end{aligned}$$

EXAMPLE 3

Given $2x^2 - 12x + 19 \equiv a(x-b)^2 + c$, find $a, b, c$.

Solution: First, expand the RHS:

$$\begin{aligned} \text{RHS} &= a(x^2 - 2bx + b^2) + c \\ &= ax^2 - 2abx + (ab^2 + c) \end{aligned}$$

Now compare coefficients with the LHS ($2x^2 - 12x + 19$):

  • 1. $a = 2$
  • 2. $-2ab = -12 \implies -4b = -12 \implies b = 3$
  • 3. $ab^2 + c = 19 \implies 2(9) + c = 19 \implies c = 1$

1.8 Methods of Proof (HL)

1. Converse and Contrapositive

For a statement of the form "If A then B":

  • Converse: If B then A (Not necessarily true)
  • Contrapositive: If not B then not A (Always equivalent to the original statement)

Notice: The contrapositive of a true statement is always true. The converse of a true statement is not necessarily true.

EXAMPLE 1

For the original statement: If $x=0$, then $x^2=0$ [True]

  • Converse: If $x^2=0$, then $x=0$ [True]
  • Contrapositive: If $x^2 \neq 0$, then $x \neq 0$ [True]

Remark: Here all three statements happen to be true.

EXAMPLE 2

For the original statement: If $x=1$, then $x^2=1$ [True]

  • Converse: If $x^2=1$, then $x=1$ [False]
  • Contrapositive: If $x^2 \neq 1$, then $x \neq 1$ [True]

EXAMPLE 3

For the original statement: If $x=0$ or $y=0$, then $xy=0$

  • Converse: If $xy=0$, then $x=0$ or $y=0$
  • Contrapositive: If $xy \neq 0$, then $x \neq 0$ and $y \neq 0$

Notice: The negation of "and" is "or", and the negation of "or" is "and".

2. Three Methods of Proof

We use a simple example to demonstrate three kinds of proof. Let $X$ be the name of a city.

European Cities
Greek Cities
X
Rome
Tokyo
(Not Europe)

1. Deductive Proof

The usual process of reasoning is to start from the hypothesis and reach the result by using logical steps.

Statement: If $X$ is a Greek city, then $X$ is a European city.

Proof: Assume that $X$ is a Greek city. Greece is part of Europe. Therefore, $X$ is a European city.

2. Proof by Counterexample

We use a counterexample to establish that a statement is not true in general.

Statement: The converse of the statement above is "If $X$ is a European city, then $X$ is a Greek city". Show that this statement is not true.

Proof: Select Rome. It is a European city but not in Greece. Hence the statement is not true in general.

3. Proof by Contradiction

Assume the result is false, and deduce a contradiction.

Statement: The contrapositive of the original statement is true: "If $X$ is a non-European city, then it is not a Greek city".

Proof: Let $X$ be a non-European city. Assume the result is false (i.e., $X$ is a Greek city). But then $X$ would be a European city! Contradiction. Thus, $X$ is not a Greek city.

3. Mathematical Examples

EXAMPLE 5 (Deduction: Even Numbers)

Show: If $a$ is even then $a^2$ is also even.

Proof: $a$ is even $\implies a=2n$ for some $n \in \mathbb{Z}$.

$$ a^2 = (2n)^2 = 4n^2 = 2(2n^2) $$

Since $2n^2 \in \mathbb{Z}$, $a^2$ is a multiple of 2 (even).

EXAMPLE 6 (Contradiction: Even Numbers Converse)

Show: We will prove that the converse is also true: If $a^2$ is even, then $a$ is even.

Proof: Suppose that $a^2$ is even. Assume that $a$ is not even (for contradiction), then $a=2n+1$ for some $n \in \mathbb{Z}$.

$$ a^2 = (2n+1)^2 = 4n^2 + 4n + 1 = 2(2n^2 + 2n) + 1 $$

Hence $a^2$ is odd, which is a contradiction. Therefore, $a$ must be even.

Notice: In fact, in the last example, instead of the statement "if $a^2$ is even then $a$ is even", we have shown the equivalent contrapositive statement: "If $a$ is odd then $a^2$ is odd".

EXAMPLE 7 (Deductive: Multiples of 4)

Statement: If $a$ is a multiple of 4, then $a^2$ is also a multiple of 4.

Proof: $a$ is a multiple of 4 $\implies a=4n$ for some $n \in \mathbb{Z}$.

$$ a^2 = (4n)^2 = 16n^2 = 4(4n^2) $$

Therefore, $a^2$ is a multiple of 4.

EXAMPLE 8 (Counterexample: Multiples of 4)

Statement: If $a^2$ is a multiple of 4, then $a$ is a multiple of 4.

Proof: Choose $a=6$. Then $a^2 = 36$, which is a multiple of 4. However, 6 is not a multiple of 4. The statement is false.

EXAMPLE 9 (Contradiction: Irrationality of $\sqrt{2}$)

Show: $\sqrt{2}$ is irrational.

Proof: Assume $\sqrt{2}$ is rational, i.e., $\sqrt{2} = \dfrac{a}{b}$ where $a, b$ are coprime integers.

$$\begin{aligned} a &= \sqrt{2}b \implies a^2 = 2b^2 \\ \end{aligned}$$
  • Thus $a^2$ is even, so $a$ is even ($a=2c$).
  • Substitute back:
$$ (2c)^2 = 2b^2 \implies 4c^2 = 2b^2 \implies b^2 = 2c^2 $$
  • Thus $b^2$ is even, so $b$ is even.
  • If $a$ and $b$ are both even, they are not coprime. Contradiction.

EXAMPLE 10 (Contradiction: Integer Solutions)

Show: The equation $6x + 15y = 100$ has no integer solutions.

Proof: Assume it has an integer solution $(x,y)$.

$$\begin{aligned} 6x + 15y &= 100 \\ 3(2x + 5y) &= 100 \end{aligned}$$

$\text{LHS}$ is a multiple of 3.
$\text{RHS} = 100$ is not a multiple of 3.
Contradiction. No integer solutions exist.

EXAMPLE 11 (Counterexample: Integer Solutions)

Statement: Chris claims that the equation $x^2 + y^2 = 100$ has no integer solutions. Investigate his claim.

Proof: Proof by counterexample that the statement is false. The integer values $x=6$ and $y=8$ satisfy the equation.

$$ x^2 + y^2 = 6^2 + 8^2 = 36 + 64 = 100 $$

EXAMPLE 12 (The Pigeonhole Principle - Contradiction)

Statement: Suppose $n+1$ pigeons are placed in $n$ pigeonholes. There exists a pigeonhole with at least 2 pigeons.

Proof: Assume all pigeonholes have at most 1 pigeon. Total pigeons $\le n$. Contradiction (since we have $n+1$).

EXAMPLE 13 (The Pigeonhole Principle Applied)

Statement: Suppose 64 pigeons are placed in 7 pigeonholes. Show some pigeonhole contains at least 10 pigeons.

Proof: Assume all pigeonholes have at most 9 pigeons. Total pigeons $\le 7 \times 9 = 63$. Contradiction (since we actually have 64 pigeons).