Proof

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.

solution

example 2

“The square of an odd number is odd.”

solution

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

solution

task 1

Prove that following implications are false.

  1. For all natural numbers n ($n \in \mathbb{N}$), $n^2+n+17$ is prime.
  2. For all $n = a$, $n^2+n+a$ is not a prime number.

solution

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.

solution

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

solution

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}^+ $.

some proofs - A.J. Hildebrand


  1. parity - odd or even ↩︎


(c) 2019 sebastian.williams[at]sebinberlin.de - impressum und datenschutz - Powered by MathJax & XMin & HUGO & jsxgraph & mypaint