Processing math: 100%

Old PBM763 (2020): Proof Strategies

Proofs

Proofs reflect our creativity, but they mostly follow certain patterns and rules of the genre. Here we list some proof templates used in course assignments with examples.

Name of a template	A Typical Example	Further Examples
Direct proof of an IF-THEN statement	Prove that for any odd integer $k$ , the square $k^2$ gives remainder 1, when divided by 8. (1) Translate: Odd $k$ means $k = 2n+1$ (2) Rewrite: $(2n+1)^2 = 4n^2 + 4n + 1 = 4n(n+1)+1$ (3) Sort cases: $n$ even or odd.
Bidirectional proof of an IF-AND-ONLY-IF statement	Prove that a positive integer $n$ has odd number of positive divisors (including 1 and $n$ itself) if and only if $n$ is a full square - can be expressed as $k^2$ .
Contrapositive proof of an IF-AND-ONLY-IF statement	Prove that for any prime number $\ p$ , the square root $\ \sqrt{p}$ is irrational.
Proving an identity by sorting cases	For any real number $\ x \in \mathbb{R}$ its rounded value to the nearest tenth (rounding to one decimal place) is equal to $\frac{1}{10} \lfloor 10x + 0.5 \rfloor$ .
Proving that a bijective function exists by construction	Prove that there is a function $\ f : (-\pi;\pi) \rightarrow \mathbb{R}$ mapping interval $\ (-\pi;\pi)$ to $\ \mathbb{R}$ such that every real number $\ y$ has exactly one $\ x$ such that $\ f(x)=y$ .
Disproving that a bijective function exists from the contrary.	Prove that it is impossible to enumerate all subsets of natural numbers with natural numbers.
Prove that some set is infinite by contradiction.	Prove that there are infinitely many primes.