Discrete Mathematics : Proof Techniques

Contents

• Proof
• Number theory
• Proof techniques
• Direct proof
• Proof by negation
• Proof by counterexample
• Proof by contraposition
• Proof by contradiction
• Proof by division into cases

Proof

What is a proof?

A proof is a method for establishing the truth of a statement.

Rigor	Truth type	Field	Truth teller
0	Word of God	Religion	God/Priests
1	Authoritative truth	Business/School	Boss/Teacher
2	Legal truth	Judiciary	Law/Judge/Law makers
3	Philosophical truth	Philosophy	Plausible argument
4	Scientific truth	Physical sciences	Experiments/Observations
5	Statistical truth	Statistics	Data sampling
6	Mathematical truth	Mathematics	Logical deduction

What is a mathematical proof?

A mathematical proof is a verification for establishing the truth of a proposition by a chain of logical deductions from a set of axioms.

Some concepts:

• Axiom is a proposition that is assumed to be true.
  Example: For mathematical quantities $a$ and $b$, if $a = b$, then $b = a$.
• Logical deduction is the process of deducing a conclusion from a set of hypotheses
  The first set of hypotheses are the axioms.
• Mathematical proof is a chain/necklace of logical deductions from a set of axioms.

Why care for mathematical proofs?

I believe that we can understand the laws of the world using mathematics and computation as shown below.

• Humanities can be reduced to and understood via pyschology
• Psychology can be reduced to and understood via biology
• Biology can be reduced to and understood via chemistry
• Chemistry can be reduced to and understood via physics
• Physics can be reduced to and understood via mathematics
• Mathematics can be implemented via computation

Properties of a proof

• Concise (not unnecessarily long)
• Clear (not ambiguous)
• Complete (no missing intermediate steps)
• Logical (every statement logically follows)
• Rigorous (uses mathematical expressions)
• Convincing (does not raise questions)
• The way a proof is presented might be different from the way the proof is discovered.

Number theory

Number theory is the branch of mathematics that deals with the study of integers.

Numbers	Set
Natural numbers $(\mathbb{N})$	$\{1, 2, 3, \ldots\}$
Whole numbers $(\mathbb{W})$	$\{0, 1, 2, \ldots\}$
Integers $(\mathbb{Z})$	$\{0, \pm 1, \pm 2, \pm 3, \ldots\}$
Even numbers $(\mathbb{E})$	$\{0, \pm 2, \pm 4, \pm 6, \ldots\}$
Odd numbers $(\mathbb{O})$	$\{\pm 1, \pm 3, \pm 5, \pm 7, \ldots\}$
Prime numbers $(\mathbb{P})$	$\{2, 3, 5, 7, 11, \ldots\}$
Composite numbers $(\mathbb{C})$	$\{\text{Natural numbers } (> 1) \text{ that are not prime}\}$
Rational numbers $(\mathbb{Q})$	$\{\text{Ratio of integers with non-zero denominator}\}$
Real numbers $(\mathbb{R})$	$\{\text{Numbers with infinite decimal representation}\}$
Irrational numbers $(\mathbb{I})$	$\{\text{Real numbers that are not rational}\}$
Complex numbers $(\mathbb{S})$	$\{\text{real} + i \cdot \text{real}\}$

Even and odd numbers

Examples:

• Even numbers:
  $0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32,\ldots$
• Odd numbers:
  $1, 3, 5, 7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,\ldots$

Rational and irrational numbers

Examples:

• Rational numbers:
  $10, -56.47, 10/13, 0, -17/9, 0.121212\ldots, -91, \ldots$
• Irrational numbers:
  $\sqrt{2}, \sqrt{3}, \sqrt{2}^{\sqrt{2}}, \pi, \phi, e, \pi^2, e^2, 2^{1/3}, \log_2 3, \ldots$
• Open problems:
  It's not known if $\pi + e, \pi e, \pi / e, \pi^e, \pi^{\sqrt{2}},$ and $\ln \pi$ are irrational

Divisibility

• Instead of "$n$ is divisible by $d$," we can say:
  $n$ is a multiple of $d$, or
  $d$ is a factor of $n$, or
  $d$ is a divisor of $n$, or
  $d$ divides $n$ (denoted by $d ~|~ n$)
• Note: $d ~|~ n$ is different from $d / n$

Examples:

• Divides: $1|1, 10|10, 2|4, 3|24, 7|-14, \ldots$
• Does not divide: $2 \nmid 1, 10 \nmid 1, 10 \nmid 2, 7 \nmid 10, 10 \nmid 7, 10 \nmid -7, \ldots$

Quotient-Remainder theorem

Examples: Let $n = 6$ and $d \in [1, 7]$:

Num. $(n)$	Divisor $(d)$	Theorem	Quotient $(q)$	Rem. $(r)$
$6$	$1$	$6 = 6 \times 1 + 0$	$6$	$0$
$6$	$2$	$6 = 3 \times 2 + 0$	$3$	$0$
$6$	$3$	$6 = 2 \times 3 + 0$	$2$	$0$
$6$	$4$	$6 = 1 \times 4 + 2$	$1$	$2$
$6$	$5$	$6 = 1 \times 5 + 1$	$1$	$1$
$6$	$6$	$6 = 1 \times 6 + 0$	$1$	$0$
$6$	$7$	$6 = 0 \times 7 + 6$	$0$	$6$

Primes and composites

Number	Factorization	Prime?
$2$	$2 = 1 \times 2 = 2 \times 1$	$\checkmark$
$3$	$3 = 1 \times 3 = 3 \times 1$	$\checkmark$
$4$	$4 = 1 \times 4 = 4 \times 1 = 2 \times 2$	$\times$
$5$	$5 = 1 \times 5 = 5 \times 1$	$\checkmark$
$6$	$6 = 1 \times 6 = 6 \times 1 = 2 \times 3 = 3 \times 2$	$\times$
$7$	$7 = 1 \times 7 = 7 \times 1$	$\checkmark$
$8$	$8 = 1 \times 8 = 8 \times 1 = 2 \times 4 = 4 \times 2$	$\times$
$9$	$9 = 1 \times 9 = 9 \times 1 = 3 \times 3$	$\times$
$10$	$10 = 1 \times 10 = 10 \times 1 = 2 \times 5 = 5 \times 2$	$\times$
$11$	$11 = 1 \times 11 = 11 \times 1$	$\checkmark$
$12$	$12 = 1 \times 12 = 12 \times 1 = 2 \times 6 = 6 \times 2 = 3 \times 4 = 4 \times 3$	$\times$
$13$	$13 = 1 \times 13 = 13 \times 1$	$\checkmark$
$14$	$14 = 1 \times 14 = 14 \times 1 = 2 \times 7 = 7 \times 2$	$\times$
$15$	$15 = 1 \times 15 = 15 \times 1 = 3 \times 5 = 5 \times 3$	$\times$
$16$	$16 = 1 \times 16 = 16 \times 1 = 2 \times 8 = 8 \times 2 = 4 \times 4$	$\times$
$17$	$17 = 1 \times 17 = 17 \times 1$	$\checkmark$

Properties:

• A natural number $n > 1$ is prime iff it has exactly two positive divisors: $1$ and $n$
• A natural number $n > 1$ is composite iff it has at least three positive divisors, two of which are $1$ and $n$
• A natural number $n$ is a perfect square iff it has an odd number of divisors
• A natural number $n$ is not a perfect square iff it has an even number of divisors

Unique prime factorization of natural numbers

$n$	Unique prime factorization	$n$	Unique prime factorization	$n$	Unique prime factorization
$2$	$2$	$16$	$2^4$	$30$	$2 \times 3 \times 5$
$3$	$3$	$17$	$17$	$31$	$31$
$4$	$2^2$	$18$	$2 \times 3^2$	$32$	$2^5$
$5$	$5$	$19$	$19$	$33$	$3 \times 11$
$6$	$2 \times 3$	$20$	$2^2 \times 5$	$34$	$2 \times 17$
$7$	$7$	$21$	$3 \times 7$	$35$	$5 \times 7$
$8$	$2^3$	$22$	$2 \times 11$	$36$	$2^2 \times 3^2$
$9$	$3^2$	$23$	$23$	$37$	$37$
$10$	$2 \times 5$	$24$	$2^3 \times 3$	$38$	$2 \times 19$
$11$	$11$	$25$	$5^2$	$39$	$3 \times 13$
$12$	$2^2 \times 3$	$26$	$2 \times 13$	$40$	$2^3 \times 5$
$13$	$13$	$27$	$3^3$	$41$	$41$
$14$	$2 \times 7$	$28$	$2^2 \times 7$	$42$	$2 \times 3 \times 7$
$15$	$3 \times 5$	$29$	$29$	$43$	$43$

Some more definitions

• Absolute value of real number $x$, denoted by $|x|$ is
  $|x| = \begin{cases}x & \text{if } x \ge 0\\-x & \text{if } x < 0\end{cases}$
• Triangle inequality. For all real numbers $x$ and $y$,
  $|x + y| \le |x| + |y|$
• Floor of a real number $x$, denoted by $\lfloor x \rfloor$ is
  $\lfloor x \rfloor = $ unique integer $n$ such that $n \le x < n + 1$
  $\lfloor x \rfloor = n \Leftrightarrow n \le x < n + 1$
• Ceiling of a real number $x$, denoted by $\lceil x \rceil$ is
  $\lceil x \rceil = $ unique integer $n$ such that $n - 1 < x \le n$
  $\lceil x \rceil = n \Leftrightarrow n - 1 < x \le n$
• Given an integer $n$ and a natural number $d$,
  $n \text{ div } d =$ integer quotient obtained when $n$ is divided by $d$,
  $n \text{ mod } d =$ whole number remainder obtained when $n$ is divided by $d$.
• Symbolically,
  $n \text{ div } d = q$ and $n \text{ mod } d = r \Leftrightarrow n = dq + r$
  where $q$ and $r$ are integers and $0 \le r < d$.

Proof techniques

Statements	Method of proof
Proving existential statements (Disproving universal statements)	Constructive proof Non-constructive proof
Proving universal statements (Disproving existential statements)	Direct proof Proof by mathematical induction Well-ordering principle Proof by exhaustion Proof by cases Proof by contradiction Proof by contraposition Computer-aided proofs

Direct proof

Even + odd = odd

Proof

Direct proof.
Suppose $a$ is even and $b$ is odd. Then: \begin{align*} & a + b \\ &= (2m) + b && \text{(defn. of even, } a = 2m \text{ for integer } m \text{)}\\ &= (2m) + (2n+1) && \text{(defn. of odd, } b = 2n+1 \text{ for integer } n \text{)}\\ &= 2 (m+n) + 1 && \text{(taking 2 as common factor)}\\ &= 2 p + 1 && \text{(} p = m + n \text{ and addition is closed on integers)}\\ &= \text{odd} && \text{(defn. of odd)}\\ \end{align*}

Problems for practice

Prove the following propositions:

• Even + even = even
• Even + odd = odd
• Odd + odd = even
• Even $\times$ integer = even
• Odd $\times$ odd = odd

$n$ is odd $\Rightarrow$ $n^2$ is odd

Proof

Direct proof.
Formal statement: If $n$ is odd, then $n^2$ is odd.
\begin{align*} & n \text{ is odd} \\ & \implies n = (2k+1) && \text{(defn. of odd, } k \text{ is an integer)}\\ & \implies n^2 = (2k+1)^2 && \text{(squaring on both sides)}\\ & \implies n^2 = 4k^2 + 4k + 1 && \text{(expanding the binomial)}\\ & \implies n^2 = 2(2k^2 + 2k) + 1 && \text{(factoring 2 from first two terms)}\\ & \implies n^2 = 2j + 1 && \text{(let } j = 2k^2 + 2k \text{; } j \text{ is an integer as mult. and add. are closed on integers)}\\ & \implies n^2 \text{ is odd} && \text{(defn. of odd)}\\ \end{align*}

Odd = difference of squares

Workout

• Write a formal statement.
  $\forall k \in \mathbb{Z}$, $\exists m \in \mathbb{Z}$, $\exists n \in \mathbb{Z}$ such that $(2k+1) = m^2 - n^2$.
• Try out a few examples.
  $1 = 1^2 - 0^2 \qquad -1 = 0^2 - (-1)^2$
  $3 = 2^2 - 1^2 \qquad -3 = (-1)^2 - (-2)^2$
  $5 = 3^2 - 2^2 \qquad -5 = (-2)^2 - (-3)^2$
  $7 = 4^2 - 3^2 \qquad -7 = (-3)^2 - (-4)^2$
• Find a pattern.
  $(k + 1)^2 - k^2 = (k^2 +2k + 1) - k^2 = 2k+1=$ odd

Proof

Direct proof. \begin{align*} &\text{Odd}\\ &= 2k+1 && \text{(defn. of odd)}\\ & = (k^2 + 2k + 1) - k^2 && \text{(adding and subtracting } k^2 \text{)}\\ & = (k+1)^2 - k^2 && \text{(use the formula for $(a+b)^2$)}\\ & = m^2 - n^2 && \text{(set } m = k + 1 \in \mathbb{Z} \text{ and } n = k \in \mathbb{Z} \text{)}\\ & = \text{difference of two squares} \end{align*}

So, every odd integer can be written as the difference between two squares.

If $a|b$ and $b|c$, then $a|c$

Proof

Direct proof.
Formal statement: $\forall$ integers $a,b,c$, if $a|b$ and $b|c$, then $a|c$. \begin{align*} & c \\ &= bn && \text{(} b|c \text{ and definition of divisibility)}\\ &= (am)n && \text{(} a|b \text{ and definition of divisibility)}\\ &= a(mn) && \text{(multiplication is associative)}\\ &= ak && \text{(let } k = mn \text{ and multiplication is closed on integers)}\\ &\implies a|c && \text{(definition of divisibility and } k \text{ is an integer)}\\ \end{align*}

Summation

Proof

Direct proof.
Formal statement. $\forall $ natural number $n$, $1 + 2 + 3 + \cdots + n = n (n + 1) / 2$. \begin{align*} & S = 1 + 2 + 3 + \cdots + n \\ & \implies S = n + (n - 1) + (n - 2) + \cdots + 1 && \text{(addition on integers is commutative)}\\ & \implies 2S = \underbrace{(n + 1) + (n + 1) + (n + 1) + \cdots + (n + 1)}_{n \text{ terms}} && \text{(adding the previous two equations)}\\ & \implies 2S = n(n + 1) && \text{(simplifying)}\\ & \implies S = n(n + 1)/2 && \text{(divide both sides by 2)}\\ \end{align*}

Proof by Negation

$2^{999}+1$

Workout

• Trying out a few examples is not possible here.
• When is a number prime?
  A number that is not composite is prime.
• When is a number composite?
  A number is composite if we can factorize it.
• How do you check if a number can be factorized?
  Check whether the number satisfies an algebraic formula that can be factored.
  It seems like the given number can be represented as $a^3 + b^3$.

Solution

Proof by negation.
False!
Negation: $2^{999}+1$ is composite. \begin{align*} & 2^{999} + 1 \\ &= (2^{333})^3 + 1^3 && \text{(terms represented as cubes)}\\ &= a^3 + b^3 && \text{(set } a = 2^{333} \text{, } b = 1 \text{)}\\ &= (a + b)(a^2 - ab + b^2) && \text{(factorize } a^3 + b^3 \text{)}\\ &= (2^{333} + 1)(2^{666} - 2^{333} + 1) && \text{(substituting } a \text{ and } b \text{ values)}\\ &= \text{composite} \\ \end{align*}

$n^2 + 3n + 2$

Workout

• Write a formal statement.
  $\exists n \in \mathbb{N}$ such that $n^2 + 3n + 2$ is prime.
• Try out a few examples.
  $1^2 + 3(1)+2 = 6 \qquad \text{composite}$
  $2^2 + 3(2)+2 = 12 \qquad \text{composite}$
  $3^2 + 3(3)+2 = 20 \qquad \text{composite}$
  $4^2 + 3(4)+2 = 30 \qquad \text{composite}$
  $5^2 + 3(5)+2 = 42 \qquad \text{composite}$
• Find a pattern.
  It seems like $n^2 + 3n + 2$ is always composite.

Solution

Proof by negation.
False!
Negation: $\forall n \in \mathbb{N}$, $n^2 + 3n + 2$ is composite. \begin{align*} & n^2 + 3n + 2 \\ &= n^2 + n + 2n + 2 && \text{(split } 3n \text{)}\\ &= n(n + 1) + 2(n + 1) && \text{(taking common factors)}\\ &= (n + 1)(n + 2) && \text{(distributive law)}\\ &= \text{composite} && \text{(} n + 1 > 1 \text{ and } n + 2 > 1 \text{)}\\ \end{align*}

Polynomial root

Proof (Invalid)

Substitute $x = 7$ in the expression to get $7^3 - 7(7^2)+7-7 = 0$.
As $x$ satisfies the equation, $x = 7$.

Incorrect! What's wrong?

Proof

Proof by negation.
False! Negation: Not all roots of the polynomial is $7$.

A polynomial equation of degree $n$ has $n$ roots.
So, the polynomial equation $x^3 - 7x^2 + x - 7 = 0$ has 3 roots.

Factorize the expression.
\begin{align*} & x^3 - 7x^2 + x - 7 \\ &= x^2(x-7) + (x-7) && \text{(taking } x^2 \text{ factor from first two terms)}\\ &= (x-7)(x^2+1) && \text{(taking } (x-7) \text{ factor)}\\ &= (x-7)(x+ i) (x - i) && \text{(factorizing } (x^2+1) \text{; this is because } (x + i)(x - i) = (x^2 - i^2) = (x^2 + 1) \text{)}\\ \end{align*} So, the three roots to the equation $x^3 - 7x^2 + x - 7 = 0$ are $x = 7$, $x = -\sqrt{-1}$, and $x = \sqrt{-1}$.

Exactly one of the three roots is $x = 7$. Hence, we have \begin{align*} & x = 7 \implies x^3 - 7x^2 + x - 7 = 0\\ & x^3 - 7x^2 + x - 7 = 0 \nRightarrow x = 7\\ \end{align*}

Proof

Direct proof.
We factorize the expression.
\begin{align*} & x^3 - 7x^2 + x - 7 \\ &= x^2(x-7) + (x-7) && \text{(taking } x^2 \text{ factor from first two terms)}\\ &= (x-7)(x^2+1) && \text{(taking } (x-7) \text{ factor)}\\ &= (x-7)(x+ i) (x - i) && \text{(factorizing } (x^2+1) \text{; this is because } (x + i)(x - i) = (x^2 - i^2) = (x^2 + 1) \text{)}\\ \end{align*} So, the three roots to the equation $x^3 - 7x^2 + x - 7 = 0$ are $x = 7$, $x = -\sqrt{-1}$, and $x = \sqrt{-1}$.
As $x$ has to be a real number, $x = 7$ and hence the given proposition is true.

Proof by Counterexample

$a = b$

Solution

False!
Counterexample: $a = 1$ and $b = -1$.
In this example, $a^2 = b^2$ but $a \ne b$.

Solution

False!
Counterexample: $a = 1$ and $b = -1$.
In this example, $a | b$ and $b | a$, however, $a \ne b$.

$2^{n}+1$

Workout

• Write a formal statement.
  $\forall n \in \mathbb{N}$, $2^n + 1$ is prime.
• Try out a few examples.
  $2^1 + 1 = 3 \qquad \text{prime}$
  $2^2 + 1 = 5 \qquad \text{prime}$
  $2^3 + 1 = 9 = 3^2 \qquad \text{composite}$
• Find a pattern.
  $2^n + 1$ can be either prime or composite.

Solution

False!
Counterexample: $n = 3$
When $n = 3$, then $2^n + 1 = 2^3 + 1 = 9 = 3^2$ is composite.

$n^2 + n + 41$

Workout

• Write a formal statement.
  $\forall$ whole number $n$, $n^2 + n + 41$ is prime.
• Try out a few examples.
  $0^2 + 0 + 41 = 41 \qquad \text{prime}$
  $1^2 + 1 + 41 = 43 \qquad \text{prime}$
  $2^2 + 2 + 41 = 47 \qquad \text{prime}$
  $3^2 + 3 + 41 = 53 \qquad \text{prime}$
  $4^2 + 4 + 41 = 61 \qquad \text{prime}$
  $5^2 + 5 + 41 = 71 \qquad \text{prime}$
• Find a pattern.
  It seems like $n^2 + n + 41$ is always prime.

Solution

• False!
• Formal statement. $\forall$ whole numbers $n$, $n^2 + n + 41$ is prime.
• Counterexample: $41$.
  ($41^2 + 41 + 41 = 41 (41 + 1 + 1) = 41 \times 43$)
• Another counterexample: $40$.
  ($40^2 + 40 + 41 = 40(40 + 1) + 41 = 40 \times 41 + 41 = 41 (40 + 1) = 41 \times 41$)

$x/(y + z) + y/(x+z) + z/(x+y)$

Workout

• Write a formal statement.
  $\forall x,y,z \in \mathbb{N}$, $x/(y + z) + y/(x+z) + z/(x+y) \ne 4$.
• Try out a few examples.
  $(x, y, z) \qquad x/(y + z) + y/(x+z) + z/(x+y) = 4 ~?$
  $(1,1,1) \qquad 1/2 + 1/2 + 1/2 = 1.5 \ne 4$
  $(1,2,1) \qquad 1/3 + 2/2 + 1/3 = 1.666\cdots \ne 4$
  $(1,2,3) \qquad 1/5 + 2/4 + 3/3 = 1.7 \ne 4$
  $(1,10,100) \qquad 1/110 + 10/101 + 100/11 = 9.199\cdots \ne 4$
• Find a pattern.
  It seems like there are no +ve integers satisfying the property.

Solution

• False!
• Counterexample:
  $x = ~154476802108746166441951315019919837485664325669565431700026634898253202035277999$
  $y = ~36875131794129999827197811565225474825492979968971970996283137471637224634055579$
  $z = ~373612677928697257861252602371390152816537558161613618621437993378423467772036$

121111111111111111111111111111111111111111

Workout

• Try out a few examples.
  $(n, \text{Number}) \qquad \text{Factorization}$
  $(0, 12) \qquad 3 \times 4$
  $(1, 121) \qquad 11 \times 11$
  $(2, 1211) \qquad 7 \times 173$
  $(3, 12111) \qquad 33 \times 367$
  $(4, 121111) \qquad 281 \times 431$
  $(5, 1211111) \qquad 253 \times 4787$
• Find a pattern.
  It seems like the sequence of numbers is composite.

Solution

• False!
• Smallest counterexample: $n = 136$.
  $12,1111111111,$ $1111111111,$ $1111111111,$ $1111111111,$ $1111111111,1111111111,$ $1111111111,$ $1111111111,$ $1111111111,$ $1111111111,$ $1111111111,$ $1111111111,$ $1111111111,$ $111111 \text{ is prime.}$

Proof by Contraposition

$n^2$ is odd $\Rightarrow$ $n$ is odd

Proof

Proof by contraposition
Contrapositive: If $n$ is even, then $n^2$ is even. \begin{align*} & n \text{ is even} \\ & \implies n = 2k && \text{(defn. of even, } k \text{ is an integer)}\\ & \implies n^2 = (2k)^2 && \text{(squaring on both sides)}\\ & \implies n^2 = 4k^2 && \text{(simplifying)}\\ & \implies n^2 = 2(2k^2) && \text{(factoring 2)}\\ & \implies n^2 = 2j && \text{(let } j = 2k^2 \text{; } j \text{ is an integer as mult. is closed on integers)}\\ & \implies n^2 \text{ is even} && \text{(defn. of even)}\\ \end{align*}

$n$ is odd $\Leftrightarrow$ $n^2$ is odd

Workout

• Write a formal statement.
  $\forall$ integer $n$, $n^2$ is odd $\Leftrightarrow$ $n$ is odd.
• Try out a few examples.
  $\text{Odd numbers} \qquad \text{Even numbers}$
  $(1, 1) \qquad (0,0)$
  $(3, 9) \qquad (2,4)$
  $(5, 25) \qquad (4,16)$
  $(7, 49) \qquad (6,36)$
• Pattern. It seems that the proposition is true.

Proof

There are two parts in the proof.

1. Prove that if $n$ is odd, then $n^2$ is odd.
   Direct proof
2. Prove that if $n^2$ is odd, then $n$ is odd.
   Proof by contraposition

Proof

We have \begin{align*} & n \text{ is odd} \Leftrightarrow n^2 \text{ is odd} && \text{(previous theorem)}\\ & \implies n^2 \text{ is odd} \Leftrightarrow n^4 \text{ is odd} && \text{(previous theorem used on } n^2 \text{)}\\ & \implies n \text{ is odd} \Leftrightarrow n^4 \text{ is odd} && \text{(transitivity of biconditional)}\\ \end{align*}

$n^2$ is even $\implies$ $n$ is even

Proof

Proof by contraposition.
Contrapositive. For all integers, if $n$ is odd, then $n^2$ is odd. \begin{align*} & n = 2k + 1 && \text{(definition of odd number)}\\ & \implies n^2 = (2k+1)^2 && \text{(squaring both sides)}\\ & \implies n^2 = 4k^2 + 4k + 1 && \text{(expand)}\\ & \implies n^2 = 2(2k^2 + 2k) + 1 && \text{(taking 2 out from two terms)}\\ & \implies n^2 = 2m+1 && \text{(set } m = 2k^2 + 2k \text{; } m \text{ is an integer as multiplication is closed on integers)}\\ & \implies n^2 = \text{odd} && \text{(definition of odd number)}\\ \end{align*}

Hence, the proposition is true.

Polynomial root

Proof

Proof by contraposition.
Contrapositive. If $x = 10$, then $x^3 - 7x^2 + x - 7 \ne 0$
Substitute $x = 10$ in the expression.
We get $10^3 - 7(10^2)+10-7 = 1000-700+10-7=303\ne 0$.
That is, $x = 10$ does not satisfy $x^3 - 7x^2 + x - 7 = 0$ equation.
Hence, the contrapositive is correct which implies that the original statement is correct.

$n \nmid ab \implies n \nmid a$ and $n \nmid b$

Proof

Proof by contraposition.
Contrapositive. Let $a,b,n \in \mathbb{Z}$. If $n | a$ or $n | b$, then $n | ab$. \begin{align*} & \text {if } n | a \\ & \implies a = nc && \text{(for some } c \in \mathbb{Z} \text{)}\\ & \implies ab = (nc)b = n(cb) && \text{(multiply by } b \text{)}\\ & \implies n | ab && \text{(definition of divisibility)}\\ \end{align*} \begin{align*} & \text {if } n | b \\ & \implies b = nd && \text{(for some } d \in \mathbb{Z} \text{)}\\ & \implies ab = a(nd) = n(ad) && \text{(multiply by } a \text{)}\\ & \implies n | ab && \text{(definition of divisibility)}\\ \end{align*}

Hence, the proposition is true.

$n^2 - 6n + 5$ is even $\implies$ $n$ is odd

Proof

Proof by contraposition.
Contrapositive. If $n$ is even, then $n^2 - 6n + 5$ is odd. \begin{align*} & n \text{ is even} \\ & \implies n = 2a \text{ for some integer } a && \text{(defn. of even)}\\ & \implies n^2-6n+5 = (2a)^2 - 6(2a) + 5 && \text{(substitute } n = 2a \text{)}\\ & \implies n^2-6n+5 = 2(2a^2)-2(6a)+2(2)+1 && \text{(simplify)}\\ & \implies n^2-6n+5 = 2(2a^2-6a+2) + 1 && \text{(take 2 common)}\\ & \implies n^2-6n+5 \text{ is odd} && \text{(defn. of odd)}\\ \end{align*}

Hence, the proposition is true.

$xy > 9 \implies x > 3$ or $y > 3$

Proof

Proof by contraposition.
Contrapositive. If $x \le 3$ and $y \le 3$, then $xy \le 9$. \begin{align*} & \text{Suppose } x \le 3 \text{ and } y \le 3. \\ & \implies xy \le 9 && \text{(multiply the two inequalities)} \end{align*}

Hence, the proposition is true.

Incorrect! Why?

Nonconstructive Proof

Irrational$^{\text{irrational}}$ can be rational

Proof

Nonconstructive proof.
We make use of the fact that $\sqrt{2}$ is irrational.
Let $x = \sqrt{2}^{\sqrt{2}}$. Number $x$ is either rational or irrational.

Case 1. If $x$ is rational, then the proposition is true.

Irrational	Irrational	Rational
$\sqrt{2}$	$\sqrt{2}$	$\sqrt{2}^{\sqrt{2}} = x =$ rational

Case 2. If $x$ is irrational, then the proposition is true.

Irrational	Irrational	Rational
$x$	$\sqrt{2}$	$x^{\sqrt{2}} = \left( \sqrt{2}^{\sqrt{2}} \right)^{\sqrt{2}} = \sqrt{2}^{\sqrt{2} \cdot \sqrt{2}} = \sqrt{2}^2 = 2$

Proof by Contradiction

$n^2$ is even $\implies$ $n$ is even (Contradiction)

Proof

Proof by contradiction.
Negation. Suppose there is an integer $n$ such that $n^2$ is even but $n$ is odd. \begin{align*} & n = 2k + 1 && \text{(definition of odd number)}\\ & \implies n^2 = (2k+1)^2 && \text{(squaring both sides)}\\ & \implies n^2 = 4k^2 + 4k + 1 && \text{(expand)}\\ & \implies n^2 = 2(2k^2 + 2k) + 1 && \text{(taking 2 out from two terms)}\\ & \implies n^2 = 2m+1 && \text{(set } m = 2k^2 + 2k \text{; } m \text{ is an integer as multiplication is closed on integers)}\\ & \implies n^2 = \text{odd} && \text{(definition of odd number)}\\ \end{align*}

Contradiction! Hence, the proposition is true.

Greatest integer

Proof

Proof by contradiction.
Negation. Suppose there is a greatest integer $N$.
Then $N \ge n$ for every integer $n$.
Let $M = N + 1$.
$M$ is an integer since addition is closed on integers.
$M > N$ since $M = N + 1$.
$M$ is an integer that is greater than $N$.
So, $N$ is not the greatest integer.
Contradiction! Hence, the proposition is true.

$\sqrt{2}$ is irrational

Proof

Proof by contradiction.
Negation. Suppose $\sqrt{2}$ is the simplest rational. \begin{align*} & \implies \sqrt{2} = m / n && \text{(} m, n \text{ have no common factors, } n \ne 0 \text{)}\\ & \implies m^2 = 2 n^2 && \text{(squaring and simplifying)}\\ & \implies m^2 = \text{even} && \text{(definition of even)}\\ & \implies m = \text{even} && \text{(why?)}\\ & \implies m = 2k \text{ for some integer } k && \text{(definition of even)}\\ & \implies (2k)^2 = 2n^2 && \text{(substitute } m \text{)}\\ & \implies n^2 = 2k^2 && \text{(simplify)}\\ & \implies n^2 = \text{even} && \text{(definition of even)}\\ & \implies n = \text{even} && \text{(why?)}\\ & \implies m, n \text{ are even} && \text{(previous results)}\\ & \implies m, n \text{ have a common factor of 2} && \text{(definition of even)}\\ \end{align*}

Contradiction! Hence, the proposition is true.

If $p | n$, then $p \nmid (n + 1)$

Proof

Proof by contradiction.
Negation. Suppose there exists integer $n$ and prime $p$ such that
$p | n$ and $p | (n + 1)$.
$p | n$ implies $pr = n$ for some integer $r$
$p | (n + 1)$ implies $p s = n + 1$ for some integer $s$
Eliminate $n$ to get:
$1 = (n + 1) - n = ps - pr = p (s - r)$
Hence, $p | 1$, from the definition of divisibility.
As $p | 1$, we have $p \le 1$. (why?)
As $p$ is prime, $p > 1$.
Contradiction! Hence, the proposition is true.

#Primes is infinite

Proof

Proof by contradiction.
Negation. Assume that there are only finite number of primes.
Let the set of primes be $\{ p_1, p_2, \ldots, p_n \}$
such that $(p_1 = 2) < (p_2 = 3) < \cdots < p_n$.
Consider the number $N = p_1 p_2 p_3 \ldots p_n + 1$. Clearly, $N > 1$.
$(i)$ There is a prime that divides $N$.
Use unique prime factorization theorem.
$(ii)$ No prime divides $N$.
For all $i \in [1, n]$, $p_i$ does not divide $N$ as it leaves a remainder of $1$ when it divides $N$.
So, $p_1 \nmid ~N$, $p_2 \nmid ~N$, $\ldots$, $p_n \nmid ~N$.
Contradiction! Hence, the proposition is true.

Average

Proof

Proof by contradiction.

• Average $A = (a_1 + a_2 + \cdots + a_n) / n$
• Negation. $\forall i \in \{1, 2, \ldots, n\}$ $a_i < A$. That is
• We have $a_1 < A$, $a_2 < A$, $\ldots$, $a_n < A$
  Now add all these inequalities to get
  $(a_1 + a_2 + \cdots + a_n) < n \times A$
  $\implies A > (a_1 + a_2 + \cdots + a_n) / n$ on simplification
  How is it possible that $A$ is both equal to and greater than $(a_1 + a_2 + \cdots + a_n) / n$
• Contradiction! Hence, the proposition is true.

Proof

Direct proof.

• Let $a_{\text{max}}$ represent the maximum among the $n$ real numbers.
• Let average $A = (a_1 + a_2 + \cdots + a_n) / n$. Then
• $a_1 = a_{\text{max}} - b_1$ such that $b_1 \ge 0$
  $a_2 = a_{\text{max}} - b_2$ such that $b_2 \ge 0$
  $\ldots$
  $a_n = a_{\text{max}} - b_n$ such that $b_n \ge 0$
  Adding the above equations, we get
  $(a_1 + a_2 + \cdots + a_n) = n \times a_{\text{max}} - (b_1 + b_2 + \cdots + b_n)$
  $\implies a_{\text{max}} = [ (a_1 + a_2 + \cdots + a_n) + (b_1 + b_2 + \cdots + b_n) ] / n$
  $= ( (a_1 + a_2 + \cdots + a_n) / n ) + ( (b_1 + b_2 + \cdots + b_n) / n )$
  $= A + ( (b_1 + b_2 + \cdots + b_n) / n )$
  $\ge A$ $(\forall i, b_i \ge 0)$

$2^p - 1$ is prime $\implies$ $p$ is prime

Proof

Proof by contradiction.
Negation. Suppose $p$ is an integer at least $2$ such that $2^p - 1$ is prime and $p$ is composite.
\begin{align*} &p \text{ is compositive}\\ & \implies p = rs \text{ such that both } r, s \text{ are in the range } [2, p - 1] \end{align*} Now consider \begin{align*} &2^p - 1 \\ &= 2^{rs} - 1 && \text{(substitute for } p \text{)}\\ &= (2^r)^s - 1 && \text{(} a^{bc} = ( a^b )^c \text{)}\\ &= (2^{r} - 1) \left( \frac{(2^r)^s - 1}{2^{r} - 1} \right) && \text{(multiply and divide by } (2^{r} - 1) > 0 \text{)}\\ &= (2^{r} - 1) \left( 1 + (2^r)^1 + (2^r)^2 + \cdots + (2^r)^{s - 1} \right) \\ &= m \times n && \text{(} m \ge 2 \text{ and } n \ge 2 \text{)}\\ \end{align*}

Contradiction! Hence, the proposition is true.

Pythagorean triplets

Proof

Proof by contraposition.
Negation. $a$ and $b$ are odd and $a^2 + b^2 = c^2$.
$a = 2m + 1$; $b = 2n + 1$ (defintion of odd)
Consider \begin{align*} \text{Consider } & a^2 + b^2 \\ &= (2m+1)^2 + (2n+1)^2 \\ &= 4m^2 + 4n^2 + 4m + 4n + 2 && \text{(expand)}\\ &= 4 \times (m^2 + n^2 + m + n) + 2 && \text{(take common factor)}\\ \equiv & \; 2 \bmod 4 && \text{(remainder is 2 when divided by 4)}\\ \end{align*} $c = 2k$ or $c = 2k + 1$ (quotient-remainder theorem)
Now consider \begin{align*} &c^2 \\ &= 4k^2 \text{ or } 4(k^2 + k) + 1 && \text{(squaring)}\\ \not\equiv & \; 2 \bmod 4 && \text{(remainder is never 2 when divided by 4)}\\ \end{align*}

Contradiction! Hence, the proposition is true.

Proof by Division into Cases

$n^2 + 3n + 2$ is prime for some $n$

Proof 2

Proof by division into cases.
False!
Negation. $\forall$ natural number $n$, $n^2 + 3n + 2$ is composite.
We prove the negation in two cases:

1. $n$ is even
2. $n$ is odd

1. Prove that $n$ is even $\implies n^2 + 3n + 2$ is composite.
   \begin{align*} & n \text{ is even} \\ & \implies n^2 \text{ is even and } 3n \text{ is even} && \text{(even } \times \text{ integer = even)}\\ & \implies n^2 + 3n + 2 \text{ is even} && \text{(even + even = even)}\\ & \implies n^2 + 3n + 2 \text{ is composite} && \text{(2 is a factor)}\\ \end{align*}
2. Prove that $n$ is odd $\implies n^2 + 3n + 2$ is composite.
   \begin{align*} & n \text{ is odd} \\ & \implies n^2 \text{ is odd and } 3n \text{ is odd} && \text{(odd } \times \text{ odd = odd)}\\ & \implies n^2 + 3n \text{ is even} && \text{(odd + odd = even)}\\ & \implies n^2 + 3n + 2 \text{ is even} && \text{(even + even = even)}\\ & \implies n^2 + 3n + 2 \text{ is composite} && \text{(2 is a factor)}\\ \end{align*}

Odd$^2 = 8m + 1$

Proof

Proof by division into cases.
Consider an integer $n$.
We know that $n = 4q \text{ or } n = 4q + 1 \text{ or } n = 4q + 2 \text{ or } n = 4q + 3$ due to quotient remainder theorem.
In the problem, $n$ is odd.
This implies $n \ne 4q$ and $n \ne 4q + 2$ (as $4q$ and $4q+2$ are even)
Hence, $n = 4q + 1$ or $n = 4q + 3$.

• Case 1. $n = 4q + 1$.
  $\implies n^2 = (4q + 1)^2 = 8(2q^2 + q) + 1 = 8 m + 1$,
  where $m = 2q^2 + q =$ integer.
• Case 2. $n = 4q + 3$.
  $\implies n^2 = (4q + 3)^2 = 8(2q^2 + 3q + 1) + 1 = 8m + 1$,
  where $m = 2q^2 + 3q + 1 = $ integer.

$(x^2 - y^2) \bmod 4 \ne 2$

Proof

Proof by division into cases.

• Case 1. $x$ is even and $y$ is even. \begin{align*} & \implies x^2 = 4 m \text{ and } y^2 = 4 n \\ & \implies x^2 - y^2 = 4(m - n) \\ \end{align*}
• Case 2. $x$ is even and $y$ is odd. \begin{align*} & \implies x^2 = 4 m \text{ and } y^2 = 4 n + 1 \\ & \implies x^2 - y^2 = 4(m - n) - 1 \\ \end{align*}
• Case 3. $x$ is odd and $y$ is even. \begin{align*} & x \text{ is odd and } y \text{ is even.} \\ & \implies x^2 = 4 m + 1 \text{ and } y^2 = 4 n \\ & \implies x^2 - y^2 = 4(m - n) + 1 \\ \end{align*}
• Case 4. $x$ is odd and $y$ is odd. \begin{align*} & x \text{ is odd and } y \text{ is odd.} \\ & \implies x^2 = 4 m + 1 \text{ and } y^2 = 4 n + 1 \\ & \implies x^2 - y^2 = 4(m - n) \\ \end{align*}

In all these four cases, $(x^2 - y^2) \bmod 4 \ne 2$.

Problems for practice

Prove or disprove the following propositions:

• If more than $n$ pigeons fly into $n$ pigeon holes for natural number $n$, then at least one pigeon hole will contain at least two pigeons. [Hint: Contradiction.]
• $1/\sqrt{2}$ is irrational. [Hint: Contradiction.]
• $\sqrt{3}$ is irrational. [Hint: Contradiction.]
• $\sqrt{6}$ is irrational. [Hint: Contradiction.]
• $\log_2 3$ is irrational. [Hint: Contradiction.]
• $\log_2 7$ is irrational. [Hint: Contradiction.]
• For all integers $a$ and $b$, if $ab$ is a multiple of 6, then $a$ is even and $b$ is a multiple of 3. [Hint: Counterexample.]
• There are no integers $a$ and $b$ such that $752b = 4183 - 326a$. [Hint: Contradiction.]
• $a^n + b^n = c^n$ has no integral solutions for all natural numbers $n \ge 1$. [Hint: Counterexample.]
• Suppose $p \in \mathbb{N}$ and $p \ge 2$. If $2^p - 1$ is prime, then $p$ is prime. [Hint: Contraposition.]
• For integers $a$, $b$, $c$, if $a^2 + b^2 = c^2$, then $a$ is even or $b$ is even. [Hint: Contraposition + division into cases.]
• There are 1000 consecutive natural numbers that are not perfect squares. [Hint: Direct proof.]
• Consider any ten prime numbers that are greater than or equal to 15. Then the sum of these prime numbers can never be (1 trillion + 1). [Hint: Direct proof, contradiction.]
• Let $n$ be a positive integer. Prove that the closed interval $[n, 2n]$ contains a power of 2. [Hint: Division into cases (power of 2 and not a power of 2).]
• Rational + rational = rational. [Hint: Direct proof.]
• Rational + irrational = irrational. [Hint: Contradiction.]
• Irrational + irrational = rational or irrational. [Hint: Examples. $\sqrt{2} + (-\sqrt{2}) = 0$ and $\frac{1}{\sqrt{2}} + \frac{1}{\sqrt{2}} = \sqrt{2}$.]
• Rational $\times$ rational = rational. [Hint: Direct proof.]
• Rational $\times$ irrational = rational or irrational. [Hint: Examples $0 \times \sqrt{2} = 0$ and $1 \times \sqrt{2} = \sqrt{2}$.]
• Nonzero rational $\times$ irrational = irrational. [Hint: Contradiction.]
• Irrational $\times$ irrational = rational or irrational. [Hint: Examples $\sqrt{2} \times \sqrt{2} = 2$ and $\sqrt{2} \times \sqrt{2} = \sqrt{6}$.]
• Rational$^{\text{rational}}$ = rational or irrational. [Hint: Examples $1^1 = 1$ and $2^{1/2} = \sqrt{2}$.]

Bogus Proofs

Prove 1 = 2

Proof using basic algebra (Invalid)

\begin{align*} & a > 0, b > 0 && \text{(Given)}\\ & a = b && \text{(Given)}\\ &\implies ab = b^2 && \text{(Multiply both sides by } b\text{)}\\ &\implies ab - a^2 = b^2 - a^2 && \text{(Subtract } a^2 \text{ from both sides)}\\ &\implies a(b - a) = (b + a)(b - a) && \text{(Factoring)}\\ &\implies a = b + a && \text{(Divide both sides by } (b - a)\text{)}\\ &\implies 0 = b && \text{(Subtract } a \text{ from both sides)}\\ &\implies b = 2b && \text{(Add } b \text{ to both sides)}\\ &\implies 1 = 2 && \text{(Divide both sides by } b\text{)}\\ \end{align*}

Error

• Cannot divide by 0 in mathematics
• Cannot divide by $(b - a)$ as $a = b$

Proof using basic algebra (Invalid)

\begin{align*} & n^2 + 2n + 1 = (n + 1)^2 && \text{(Expand)}\\ &\implies n^2 = (n + 1)^2 - (2n + 1) && \text{(Subtract)}\\ &\implies n^2 - n(2n + 1) = (n + 1)^2 - (2n + 1) - n(2n + 1) && \text{(Subtract)}\\ &\implies n^2 - n(2n + 1) = (n + 1)^2 - (n + 1)(2n + 1) && \text{(Factoring)}\\ &\implies n^2-n(2n + 1) + (2n + 1)^2/4 = (n + 1)^2 - (n + 1)(2n + 1) + (2n + 1)^2/4 && \text{(Add)}\\ &\implies (n - (2n + 1)/2)^2 = ((n + 1) - (2n + 1)/2)^2 && \text{(Simplify)}\\ &\implies n - (2n + 1)/2 = (n + 1) - (2n + 1)/2 && \text{(Square roots)}\\ &\implies n = n + 1 && \text{(Add)}\\ &\implies 1 = 2 && \text{(Subtract)}\\ \end{align*}

Error

• Cannot take square roots directly
• $a^2 = b^2$ does not imply $a = b$
  E.g.: $1^2 = (-1)^2$ does not imply $1 = -1$

Proof using calculus (Invalid)

\begin{align*} & \int u \,dv = uv - \int v \,du && \text{(Product rule)}\\ & \text{Set } u = \frac{1}{x} \text{ and } v = x \text{; We get } du=-\frac{1}{x^2} \,dx \text{ and } dv = \,dx \\ &\implies \int \frac{1}{x} \,dx = x \cdot \frac{1}{x} - \int x \cdot \left( - \frac{1}{x^2} \right) \,dx && \text{(Substitute)}\\ &\implies \int \frac{1}{x} \,dx = 1 + \int \frac{1}{x} \,dx && \text{(Simplify)}\\ &\implies 0 = 1 && \text{(Subtract)}\\ &\implies 1 = 2 && \text{(Add)}\\ \end{align*}

Error

• Cannot subtract integrals from both sides
• $\int \,dx = x ~+ $ const. (const. depends on conditions)
  E.g.: $\frac{d}{dx} \left( x + 1 \right) = \frac{d}{dx} \left( x + 2 \right)$ does not imply
  $\int \frac{d}{dx} \left( x + 1 \right) = \int \frac{d}{dx} \left( x + 2 \right)$

Proof using algebra and calculus (Invalid)

\begin{align*} & x \ne 0 && \text{(Given)}\\ & x = x && \text{(Given)}\\ &\implies x + x = 2x && \text{(Add)}\\ &\implies \underbrace{x + x + \cdots + x}_{x \text{ times}} = x^2 && \text{(Repeatedly add } x \text{ times)}\\ &\implies \underbrace{1 + 1 + \cdots + 1}_{x \text{ times}} = 2 x && \text{(Differentiate)}\\ &\implies x = 2x && \text{(Simplify)}\\ &\implies 1 = 2 && \text{(Divide)}\\ \end{align*}

Error

• Cannot write $\underbrace{x + x + \cdots + x}_{x \text{ times}} = x^2$ for non-integers
• E.g.: Cannot write $\underbrace{1.5 + 1.5 + \cdots + 1.5}_{1.5 \text{ times}} = 1.5^2$

Proof using continued fractions (Invalid)

• $1 = \frac{2}{3 - 1} = \frac{2}{3 - \frac{2}{3 - 1}} = \frac{2}{3 - \frac{2}{3 - \frac{2}{3 - 1}}} = \frac{2}{3 - \frac{2}{3 - \frac{2}{3 - \frac{2}{3 - 1}}}} = \frac{2}{3 - \frac{2}{3 - \frac{2}{3 - \frac{2}{3 - \cdots}}}}$
• $2 = \frac{2}{3 - 2} = \frac{2}{3 - \frac{2}{3 - 2}} = \frac{2}{3 - \frac{2}{3 - \frac{2}{3 - 2}}} = \frac{2}{3 - \frac{2}{3 - \frac{2}{3 - \frac{2}{3 - 2}}}} = \frac{2}{3 - \frac{2}{3 - \frac{2}{3 - \frac{2}{3 - \cdots}}}}$
• So, $1 = 2$ (continued fractions are the same)

Error

• Cannot equate the values of the continued fractions
• The given continued fraction is $x = \frac{2}{3 - x}$
  Solving for $x$, we have $x = 1$ or $x = 2$
• Beware of infinity!

Proof using infinite series (Invalid)

\begin{align*} & \text{Let } S = 1 - 1 + 1 - 1 + \cdots \\ &\implies S = (1 - 1) + (1 - 1) + \cdots = 0 + 0 + \cdots = 0 \\ &\implies S = 1 + (- 1 + 1) + (- 1 + 1) + \cdots = 1 + 0 + 0 + \cdots = 1 \\ &\implies 0 = 1 && \text{(} S = 0 \text{ and } S = 1 \text{)}\\ &\implies 1 = 2 && \text{(Add)}\\ \end{align*}

Error

• Cannot use several algebraic methods on a divergent series
• Grandi's series is divergent
• Beware of infinity!

Proof using set theory (Invalid)

• Using Georg Cantor's set theory and his idea of one-to-one correspondence, we can show that the number of points on the number line segment $[0, 1]$ is same as the number of points on the number line segment $[0, 2]$
• So, $1 = 2$

Error

• Solution is out of scope
• The problem is because the principles that apply in the world of finite quantities do not apply in the world of infinite quantities
• Beware of infinity!

Proof using geometry (Invalid)

• Banach-Tarski paradox states that a solid ball can be split into a finite number of disjoint subsets, which can then be assembled to create two identical copies of the original solid ball

• So, $1 = 2$

Error

• Solution is out of scope
• The problem is because the principles that apply in the world of finite quantities do not apply in the world of infinite quantities
• Beware of infinity!

Proofs

Elisha Scott Loomis' book "The Pythagorean Proposition" presents 367 correct proofs of the theorem (algebraic proofs + geometric proofs + trigonometric proofs).