MATH 302 Lecture 6

« previous | Wednesday, September 14, 2011 | next »

Proofs

Know terminology on pages 81 and 82

Main goal is to support the claim $p\rightarrow q$

Three main methods of proofs:

1. Direct: assume $p$ is true and show that $q$ is also true
2. Proof by Contraposition: assume $q$ is false and show that $p$ must be false.
3. Proof by Contradiction: assume that $\neg (p\rightarrow q)$ ($p$ is true and $q$ is false) and try to arrive at a conflict (contradiction)

Examples

Definitions

• $n$ is even: $\exists k(n=2k)$
• $n$ is odd: $\exists k(n=2k+1)$
• $x$ is rational: $x={\frac {p}{q}}$ for some $p,q\in \mathbb {Z} ,\ q\neq 0$

Example 1

Proposition. If $n$ is odd, then $n^{2}$ is odd.

Proof. Let $n$ be an odd integer. By definition, there exists some integer $k$ such that $n=2k+1$. Then $n^{2}=(2k+1)^{2}=4k^{2}+4k+1=2(2k^{2}+2k)+1$, where $2x^{2}$ is an integer. Hence by definition, $n^{2}$ is odd.

Q.E.D.

Example 2

Proposition. If $n$ is even, then $3n+5$ is odd.

Proof. Let $n$ be an even integer. By definition, for some integer $k$, $3n=3(2k)=6k$ is an even number. $6k+5=6k+4+1=2(3k+2)+1$ must be an odd number by definition, where $3k+2$ is an integer. Therefore $3n+5$ is odd for an even integer $n$.

Q.E.D.

Example 3

Proposition. If $a$ and $b$ are rational, then $a\cdot b$ is rational.

Proof. Let $a$ and $b$ be rational numbers. Then $a={\frac {p_{a}}{q_{a}}}$ and $b={\frac {p_{b}}{q_{b}}}$ for some integers $p_{a}$,

Example 4

Proposition. If $n^{2}$ is odd, then $n$ is odd.

Proof by contraposition. Let $n$ be even. Then $n=2k$ for some integer $k$, so $n^{2}=4k^{2}=2(2k^{2})$, which is even.

Q.E.D.

Example 5

Proposition. If $3n+5$ is odd, then $n$ is even.

Proof by contraposition. Assume $n$ is odd. Then $n=2x+1$ for some integer $k$.

${\begin{aligned}3n+5&=3(2k+1)+5\\&=6k+8\\&=2(3k+4)\end{aligned}}$

Hence $3n+5$ is even.

Q.E.D.

Example 6

Proposition. ${\sqrt {2}}$ is irrational

Proof by contradiction. Assume ${\sqrt {2}}$ is rational. Therefore, ${\sqrt {2}}={\frac {p}{q}}$ for some integers $p$ and $q$, where $q\neq 0$. We will assume without loss of generality that $p$ and $q$ have no common factors (are coprime). Thus we have ${\frac {p^{2}}{q^{2}}}=2$, giving $p^{2}=2q^{2}.<math>p^{2}$ is even, so $p$ must be even: $p=2k$ for some integer $k$. $p^{2}=(2k)^{2}=4k^{2}=2q^{2}$, then $2k^{2}=q^{2}$, so $q^{2}$—and therefore $q$—must be even. Since $p$ and $q$ are even, they would have a common factor of 2, which contradicts our generality that $p$ and $q$ are coprime.

Q.E.D.

Example 7

Proposition. If $x>0$, then $x+{\frac {1}{x}}\geq 2$

Scratch sheet. (Working backwards) $x^{2}+1\geq 2x$, so $x^{2}-2x+1=(x-1)^{2}\geq 2x$, which is true.

Proof. Assume $x>0$. We also have $(x-1)^{2}\geq 0$. Then $x^{2}-2x+1\geq 0$ by expansion, and can be simplified to $x+{\frac {1}{x}}\geq 2$

Q.E.D.

Methods and Strategies of Proofs

proof by exhaustion (proof by cases)

given a finite number of possibilities, just check the proof's validity by checking all of the possibilities

existence proofs

construct an example of a case that satisfies the proposition

uniqueness proofs