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}$$

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$

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$

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.

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.

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).