introduction to proof
direct proof
P and Q are two propositions (here, usually mathematical statements).
If P, then Q
$${P \Rightarrow Q}$$
In other words this is an implication. P implies Q.
Proofs can be quite simple.
example 1
Theorem: every odd number can be written as a difference of squares.
example 2
“The square of an odd number is odd.”
equivalent statements
If ${P \Rightarrow Q}$
and ${Q \Rightarrow P}$
, we say ${P \Leftrightarrow Q}$
, that is P is equivalent to Q.
The equivalence of P and Q is sometimes written as “if and only if P, then Q” or “P is a necessary and sufficient for Q.”
Note To prove ${P \Leftrightarrow Q}$
we must prove ${P \Rightarrow Q}$
and ${Q \Rightarrow P}$
.
counterexample
To disprove a statement it is enough to find one counterexample.
example 3
Prime numbers are divisible by 1 and itself. Prove the following hypothesis is false.
“For all natural numbers n the expression $n^2+n+5$
is prime.”
task 1
Prove that following implications are false.
- For all natural numbers n (
$n \in \mathbb{N}$
),$n^2+n+17$
is prime. - For all
$n = a$
,$n^2+n+a$
is not a prime number.
proof by exhaustion
Sometimes you have to prove for different cases. So, you “exhaust” all possibilities and show that the proof holds for all cases.
example
TODO
proof by contrapositive
You prove that “P implies Q” by showing that the contrapositive of Q, “not Q” implies “not P”.
$${\neg Q \Rightarrow \neg P}$$ proves that
${P \Rightarrow Q}$
“My coat is red” as a contrapositive is “The coat is not red, it is therefore not mine.”
example 5
Let $x, y \in \mathbb{Z}$
. If x + y is even, then x and y have the same parity 1.
TODO - truth table
proof by contradiction
To show that P implies Q, you assume the opposite of Q (logical negation of the result) and try come to a contradiction by argumentation using axioms and previously proven theorems.
To prove “If P, then Q”, assume P and not Q.
example 6
$\sqrt{2}$
and $\sqrt{3}$
are irrational. See here.
example 7
For all numbers a, b, where $a \geq 0$
and $b \geq 0$
the following is true:
$$a+b \geq 2 \cdot \sqrt{a \cdot b}$$
proof by induction
A proof by induction is divided into two steps.
proposition notation
We use P(n) or $P_n$
to represent a propostion which is defined for every integer $n \geq a$
, $ a \in \mathbb{Z}$
the principle of mathematical induction
Let us suppose that $P_n$
is a proposition which is defined for every $n \geq a$
, $ a \in \mathbb{Z}$
.
If
$P_a$
is true, and$P_{k+1}$
is true whenever$P_k$
is true,then
$P_n$
is true for all$n \geq a$
.
This means if a = 1 and the two conditions hold, then the fact that $P_1$
is true implies that $P_2$
, $P_3$
, etc. are also true.
initial step
Show that P(1) is true. This means that you show that for k = 1 the statement is true.
inductive step
If there is a k such that P(k) is true, then P(k+1) is true. You have to then try and show, for the same k, that the formula is also true for k + 1. I.e., P(k+1) is true.
This means you have to show algebraically that the expression is also true for k + 1
Example
Prove by induction that the sum of the first n odd numbers is $n^2$
.
$${\begin{align}\sum_{i=1}^{n}{(2i-1)} & = n^2 && (1) \end{align}}$$
Proof
1 initial step: Prove the formula is true for $n = 1$
.
LHS: $2 \cdot 1 - 1 = 1$
and the RHS: $1^2 = 1$
.
The LHS and the RHS are equal, so the initial step is true.
2 inductive hypothesis. Let $k \in \mathbb{Z}^+$
Now, assume the formula (1) is correct for n = k. Then
3
$${ \begin{align} \sum_{i=1}^{k+1}{(2i-1)} & = \sum_{i=1}^{k}{(2i-1)} + (2(k+1) - 1) \newline & = \color{orange}{k^2} + (2(k+1) - 1) && \text{(by induction hypothesis)} \newline & = k^2 + 2k + 1 \newline & = (k+1)^2\end{align} }$$
4 Therefore, as P(k+1) is true if P(k) is true and by principle of induction, (1) is true for all $n \geq 2, n \in \mathbb{Z}^+ $
.
useful links
-
parity - odd or even ↩︎