Induction, contradiction, counterexample (HL)

Induction
Contradiction
Disprove by counterexample

Induction

The base case is

$n = 0$ for $n \in \mathbb{N}$ ,
$n = 1$ for $n \in \mathbb{Z}^+$ ,
$n = 3$ for $n \in \mathbb{Z}^+, n \geq 3$

The steps:

Show true for $n = $ base case.
Assume true for $n = k$ .
Show true for $n = k+1$
$P_\text{base case}$ is true; $P_k$ is true $\implies P_{k+1}$ is true; $P_n$ is true for $n \geq \text{base case}.$

Steps 1 and 3 should be done using LHS to RHS proofs.

In step 3, try to involve the assumption from step 2 as early as possible.

If need to work backwards, be sure to cross out rough work. The final solution presented to examiners must be LHS to RHS proofs for steps 1 and 3.

Example: Using induction, prove that $(1 + x)^n \geq 1 + nx$ for all ${n \in \mathbb Z^+}$ and ${\{x\in\mathbb R \mid x \geq -1\}}$ .

The base case is when $n = 1$ .

\begin{align*} (1 + x)^{(1)} &= 1 + x \\ &= 1 + (1)x \end{align*}

Thus true for $n = 1$ .

Note that $x \geq -1$ implies $1 + x \geq 0$ .

Assume true for $n = k$ , ie

(1 + x)^k \geq (1 + kx)

Note: “Assume true for $n = k$ ” means “if we know the question statement is true for some $k$ ”. IB explicitly does not give marks for “let ${n = k}$ ” or “assume ${n = k}$ ”, which means something else.

Then for $n = k + 1$

\begin{align*} (1 + x)^{k + 1} &\geq (1 + x)^k (1 + x) \quad(\text{definitely non-negative})\\ &\geq (1 + kx)(1 + x) \quad(\text{may be negative})\\ &= 1 + x + kx + kx^2 \\ &= 1 + (k + 1)x + kx^2 \end{align*}

Since $kx^2\geq 0$ , this shows that

(1 + x)^{k + 1} \geq 1 + (k + 1)x

$P_k$ is true $\implies P_{k+1}$ is true; $P_1$ is true means $P_n$ is true for $n \geq 1 \qed$

A stronger version of the above example is by breaking into even $n$ and odd $n$ , then using two base cases of $n = 0$ and $n = 1$ , and showing $P_k \implies P_{k+2}$ means that ${(1+x)^n \geq 1 + nx}$ for ${n \in \mathbb N}$ and ${\{x\in\mathbb R \mid x \geq -2\}}$ (other than the case $n = 0, x = -1$ which is $0^0$ or indeterminate.)

Example: (From The Art and Craft of Problem Solving) Prove using induction that ${7^n - 1}$ is divisible by $6$ for all $n\in\mathbb Z^+$ .

For $n = 1$ , $7^1 - 1$ is $6$ , which is a multiple of $6$ .

Assume true for $n = k$ , or ${7^k - 1 = 6p}$ , for some ${p \in \mathbb Z^+}$ .

Then for $n = k + 1$

\begin{align*} 7^{k + 1} - 1 &= 7\cdot 7^k - 1 \\ &= 7\cdot 7^k - 7 + 6 \\ &= 7\cdot (7^k - 1) + 6 \\ &= 7\cdot 6p + 6 \\ &= 6 (7p + 1) \end{align*}

$P_k$ is true $\implies P_{k+1}$ is true; $P_1$ is true means $P_n$ is true for $n \geq 1 \qed$

As an extension (beyond HL), there is also strong induction, in which we assume true for ${ n \geq k \geq \text{base case},\, n,k \in \mathbb Z}$ .

Contradiction

Contradiction works by assuming the complement (opposite) of what you are trying to show, reaching a false conclusion, which invalidates the assumption.

There are two cases.

single proposition

The first case is “show [some statement] is true”, with the first step to “assume [some statement] is false”.

“There exists … ” becomes “Assume there is no …”, vice versa.
“This is an infinite number of …” becomes “Assume there is a list of all …”
” $\sqrt[3]6$ is irrational” becomes “Assume $\sqrt[3]6 = \frac{p}{q}, \,p, q \in \mathbb Z^+$ and $p$ and $q$ have no common factors.”
” $f(x) > y$ becomes “Assume $f(x) \leq y$ .”

Example: (Adapted from video by blackpenredpen ) Prove by contradiction that $a^2 + b^2 = 4c + 3$ has no integer solutions.

Assume there is a solution. Since right side is odd (EVEN + ODD = ODD), it follows that $a^2 + b^2$ is odd, and that one of $a$ and $b$ is even, and other one is odd.

In the case $a$ is even and $b$ is odd, and $(2m, 2n + 1, c)$ is a solution for $(a, b, c)$ . It follows that

\begin{align*} (2m)^2 + (2n + 1)^2 &= 4m^2 + 4n^2 + 4n + 1 \\ &= 4(m^2 + n^2 + n) + 1 \\ 4c + 3 &= 4(m^2 + n^2 + n) + 1 \\ 2 &= 4(m^2 + n^2 + n - c) \end{align*}

This is a contradiction because left side is not a multiple of $4$ but right side is. (More explicitly, when dividing both sides by 2, we have ODD on the left side and EVEN on the right). Hence $(2m, 2n + 1, c)$ is not a solution.

Since $b^2 + a^2 = 4c + 3$ has the same solutions as $a^2 + b^2 = 4c + 3$ , $(2n + 1, 2m, c)$ is also not a solution. Both cases have no solution $\qed$

Example: Prove by contradiction that $\sqrt[3]6$ is irrational.

Assume $\sqrt[3]6 = \frac pq, \,p, q, \in \mathbb Z^+$ and $p, q$ are coprime, ie have no common factors.

\begin{align*} 6 &= \frac{p^3}{q^3}\\ 6q^3 &= p^3 \end{align*}

Since $6q^3$ is even, then $p^3$ and $p$ are even, so $p = 2k, \, k\in\mathbb Z^+$ .

\begin{align*} 6q^3 &= (2k)^3 \\ 6q^3 &= 8k^3 \\ 3q^3 &= 4k^3 \end{align*}

Since $4k^3$ is even, then $q^3$ and $q$ are even.

This contradicts the assumption that $p$ and $q$ are coprime. In other words, the contradiction is there is a more simplified fraction than the simplest fraction. Hence $\sqrt[3]6$ is irrational $\qed$

if A then B

The second case is “if $A$ then $B$ ”, with the first step to “assume $A$ AND not $B$ ”. It is at times interchangeable with the first, but this helps with longer propositions or statements.

Example: Prove by contradiction that if $a^2 + b^2 = c^2$ and $a, b, c\in \mathbb Z$ , then at least one of $a$ and $b$ is even.

Assume $a^2 + b^2 = c^2,\, a, b, c \in\mathbb Z$ and $a$ and $b$ are both odd. This means for ${p, q \in \mathbb Z}$ , let ${a = 2p + 1}$ , ${b = 2q + 1}$ .

\begin{align*} (2p+1)^2 + (2q+1)^2 = 4p^2 + 4p + 1 + 4q^2 + 4q + 1 &= c^2 \\ 4(p^2 + p + q^2 + q) + 2 = c^2 \end{align*}

$c$ is even. Let $c = 2r,\,r\in\mathbb Z$

\begin{align*} 4(p^2 + p + q^2 + q) + 2 &= (2r)^2 \\ &= 4r^2 \end{align*}

This is a contradiction as left side is not a multiple of $4$ (remainder $2$ ), but right side is.

Hence by contradiction the statement requires $a$ and/or $b$ to be even $\qed$

Example: Prove using contradiction that $\sin x - \cos x \geq 1$ for all ${x\in\left[\frac\pi2, \pi\right]}$ .

In quadrant II, $\sin x \geq 0$ and $\cos x \leq 0$ , and they cannot be zero at the same time. So we can immediately show that ${\sin x - \cos x > 0}$ , and ${\sin x \cos x \leq 0}$ .

Assume that $\sin x - \cos x < 1$ for some ${x\in\left[\frac\pi2, \pi\right]}$ .

Then

\begin{align*} (\sin x - \cos x)^2 &= \sin^2 x -2\sin x\cos x + \cos^2 x \\ &= 1 - 2 \sin x \cos x \end{align*}

Since we squared $0 < \sin x - \cos x < 1$ , we see that

\begin{align*} 1 - 2\sin x \cos x &< 1 \\ - 2 \sin x \cos x &< 0 \\ \sin x\cos x &> 0 \quad{\text{after division by }-2} \end{align*}

This contradicts ${\sin x \cos x \leq 0}$ .

Therefore, the assumption is wrong, and ${\sin x - \cos x \geq 1}$ for all ${x\in\left[\frac\pi2, \pi\right]}\qed$

Note: It is insufficient to show that $\sin x - \cos x \geq 1$ results in no inconsistencies, rather we needed to show $\sin x - \cos x < 1$ led to an inconsistency.

tips

In your working, you can use the following without proof:

parities (odd vs even) when adding or multiplying two integers

odd $+$ odd is even, even $+$ even is even, odd $+$ even is odd
odd $\times$ odd is odd, even $\times$ (odd or even) is even
even numbers are $2k$ ; odd numbers are $2k+1$

algebra rules, for both equations and inequalities

Common contradictions look like

An equation is odd on one side but even on the other.
(Extension:) A equation has a multiple of $n$ on one side but not on the other.
A statement that is algebraically false.
Existence of a smaller number than the smallest. (Existence of a large number than the largest.)

Disprove by counterexample

Provide a specific case and explain that it shows the statement is not always true.

Example: Kim claims that if an integer in base- $10$

is greater than $1$ , AND
each digit is $1, 3, 7,$ or $9$ , AND
the digits are all different, AND
the digits do not sum to a multiple of $3$

then the integer is prime.

Provide a counterexample and explain why Kim is incorrect.

$91$ is greater than one; its digits are $9$ and $1$ ; $9 + 1 = 10$ which is not a multiple of $3$ , but it is not prime as ${91 = 7 \times 13 \qed}$

$1$ is not a counterexample, because it is not greater than $1$ .

$23$ is not a counterexample, because the statement does not apply to integers with a digit $2$ . The statement does not say what happens if an integer is prime.

$37$ is not a counterexample, but rather an example for which the statement holds true.