0.0: Introduction to proofs

Introduction to Proofs/Contradiction

In this section, we will explore different techniques of proving a mathematical statement "If \(p\) then \(q\)". (\(p \to q\)). This is a conditional statement.

Direct Proof

In this technique, we shall assume \(p\) and show that \(q\) is true.

Theorem \(\PageIndex{1}\)

Let \(n\) be an integer. If \(n\) is even then \(n^2\) is even.

Proof

Assume that \(n\) is even. Then \(n=2m\) for some integer \(m \).

Consider \(n^2=(2m)^2=4m^2=2(2m^2).\) Since \( m \) is an integer, \( (2m^2)\) is an integer.

Thus \(n^2\) is even.\(\square\)

Example \(\PageIndex{1}\)

Show that for all integers \( n\), if \(n\) is odd then \(n^2\) is odd.

Proof

Assume that \(n\) is odd. Then \(n=2m+1\) for some integer \(m \).

Consider \(n^2=(2m+1)^2=4m^2+4m+1=2(2m^2+2m)+1.\)

Since \( m \) is an integer, \( (2m^2+2m)\) is an integer.

Thus \(n^2\) is odd.\(\square\)

Proof by Contrapositive

In this technique, we shall assume \(\neg  p\) and show that \( \neg q\) is true.

Theorem \(\PageIndex{2}\)

Let \(n\) be an integer. If \(n^2\) is even then \(n\) is even.

Proof

We shall prove this statement by assuming \(n\) is odd. Then \(n=2m+1\) for some integer \(m \).

Consider \(n^2=(2m+1)^2=4m^2+4m+1=2(2m^2+2m)+1.\)

Since \( m \) is an integer, \( (2m^2)+2m\) is an integer.

Thus \(n^2\) is odd.\(\square\)

Example \(\PageIndex{2}\)

Show that for all integers \( n\), if \(n^2\) is odd then \(n\) is odd.

Proof

We shall prove this statement by assuming \(n\) is even. Then \(n=2m\) for some integer \(m \).

Consider \(n^2=(2m)^2=4m^2=2(2m^2).\)

Since \( m \) is an integer, \( (2m^2)\) is an integer. Thus \(n^2\) is even.\(\square\)

Proof by Contradiction

In this technique, we shall assume the negation of the given statement is true, and come to a contradiction.

Theorem \(\PageIndex{3}\)

\(\sqrt{2}\) is irrational.

Proof

Assume that \(\sqrt{2}\) is rational. Then \(\sqrt{2}= \dfrac {b}{a}\), where \(b \in \mathbb{Z}, a \in \mathbb{Z}\setminus \{0\}\), with no common factors between \(a\) and \(b\). Now, \( \sqrt{2} a=b\). Then \( 2a^2=b^2\). Since \(2\) divides \(2a^2\), \(2\) divides \(b^2\). Thus \(b^2\) is even. Therefore, \(b\) is even, (by theorem 2). Since \( b\) is even, \(2 \) divides \(b\). Therefore, \(2^2 \) divides \(b^2\).

Since \(2a^2=b^2\), \(2^2 \) divides \(2a^2\). Therefore, \(2 \) divides \(a^2\). Which implies \(a\) is even. This contradicts the fact that \(a\) and \(b\) have no common factors. Thus \(\sqrt{2}\) is irrational.\(\square\)

Proof by Counterexample

Example \(\PageIndex{3}\):

Decide whether the statement is true or false and justify your answer:

For all integers \(a,b,u,v\), and \(u\ne 0, v \ne 0\), if \(au+bv =0\) then \(a=b=0.\)

Solution: The statement is false.

Counterexample: Choose \(a=1,b=-1, u=2,v=2\), then \(au+bv =0\), but \(a\ne 0. b \ne 0, a \ne b.\)

Mathematical Induction

Process of Proof by Induction

Let \(p(n)\) be a mathematical statement, \(n \in \mathbb{N}\) i.e., \(n \ge1\).

1. Prove the statement is true for the lowest value of \(n\).

2. Assume that \(p(n)\) is true for all \(n=k\).

3. Prove \(p(k+1)\) is true.

Example \(\PageIndex{4}\)

Prove \(2^n>n+4\) for \(n\ge 3, n\in \mathbb{N}\).

Proof

Let \(n=3\).  Then \(2^3 >3+4\) is true since clearly \(8>7\).  Thus the statement is true for \(n=3\).

Assume that \(2^n > n+4\) is true for some \(n=k\).

We will show that \(2^{k+1} > (k+1)+4\).

Consider \(2^{k+1}=2 \cdot 2^{k} >2 \cdot (k+4)=2k+8\).

Since \(2k > k+1\) and \(8 >4\), we have \(2k+8>(k+1)+4\).

Thus the statement is true for all \(n=k\).

By induction, \(2^n > n+4\) for all \(n\ge 3, n \in \mathbb{Z} \).◻

Example \(\PageIndex{5}\)

Show that \(9|(10^{n+1}+3(10^n)+5), \forall n \ge 1\).

Proof

Let \(n=1\).  Then \(9|(10^2)+3(10)+5\), which is \(9|135\), which is true since \(135=9(15)\) and \(15 \in \mathbb{Z}\).

Assume that \(9|(10^{n+1}+3(10^n)+5\) is true for some \(n=k\).

We will show that \(10^{k+1+1}+3(10^{k+1})+5=9m\) for some \(m \in \mathbb{Z}\).

Consider \(10^{k+1+1}+3(10^{k+1})+5=10(10^{k+1}+3(10^k)+5)-9(5)\)

       \(=10(9m)-9(5)\)

       \(=9(10m-5)\), where \(10m-5 \in \mathbb{Z}\).

By induction, \(9|(10^{n+1}+3(10^n)+5), \forall n \ge 1\).◻

Example \(\PageIndex{6}\)

Show that \(1+2+3+\cdots + n=\frac{n(n+1)}{2}, \; \forall \; n\ge 1\).

Proof

Let \(n=1\).  Then \(1=\frac{1(1+1)}{2}\) which is true.

Assume \(1+2+3+\cdots + n=\frac{n(n+1)}{2}\) is true for some \(n=k\).

We will show that \(1+2+3+\cdots + n +(n+1)=\frac{(n+1)(n+1+1)}{2}\)

Consider \(1+2+3+\cdots +n+(n+1)=[1+2+3+\cdots+n]+(n+1)\).

        \(=\frac{n(n+1)}{2} +(n+1)\)

        \(=\frac{n(n+1)+2(n+1)}{2}\)

        \(=\frac{(n+1)(n+1+1)}{2}\).

By induction, \(1+2+3+\cdots + n=\frac{n(n+1)}{2}, \; \forall \; n\ge 1\).◻

Example \(\PageIndex{7}\)

 Prove that \(3|(10^{n+1}+10^n+1), \; \forall \; n\ge 1\).

Proof

Let \(n=1\).  Then \(3|(10^2+10+1)\) is true since \(111=3(37)\) and \(37 \in \mathbb{Z}\).

Assume that \(3|(10^{n+1}+10^n+1)\) for some \(n=k\).

We will show that \(10^{k+1+1}+10^{k+1}+1=3m, m\in \mathbb{Z}\).

Consider \(10^{k+1+1}+10^{k+1}+1=10(10^{k+1}+10^k+1)-9(1)\)

  \(=10(3m)-3(3)\)

  \(=3(10m-3)\) where \(10m-3 \in \mathbb{Z}\).

By induction, \(3|(10^{n+1}+10^n+1), \; \forall \; n\ge 1\).◻

Bi-conditional statements 

Bi-conditional statements are conditional statements which depend on both component propositions. They read "\(p\) if and only if \(q\)" and are denoted \(p \leftrightarrow q\) or "p iff q", which is logically equivalent to \((p \to q) \wedge (q \to p)\).

Example \(\PageIndex{8}\)

Consider the statement: "Two lines are perpendicular if and only if they intersect to form a right angle."

The component propositions are:

1. \(p\): Two lines are perpendicular
2. \(q\): [The lines] intersect to form a right angle

Logically, we can see that if two lines are perpendicular, then they must intersect to form a right angle. Also, we can see that if two lines form a right angle, then they are perpendicular.

If two lines are not perpendicular, then they cannot form a right angle. Conversely, if two lines do not form a right angle, they cannot be perpendicular. This is why, if both propositions in a biconditional statement are false, the statement itself is true!

Proof Do's and Dont's

Do's:

1. Write the statement to be proved. It should be clear what you are proving.
2. Clearly mark the beginning of your proof with the word "Proof".
3. Make your proof self-contained. In particular, identify all variables used in your proof in the body of your proof.
4. Write proof in complete English sentences.

Example \(\PageIndex{9}\): Acceptable

Proof: Let \(n\in \mathbb{Z}\). Assume \(n\) is an even integer. Then \(n=2k,\) for some \(k \in \mathbb{Z}\).

Example \(\PageIndex{10}\): Unacceptable

Proof: \(n\) is even \(\implies\) 2k.

5. Indicate what method of proof you are using. (The default assumption is that it is a direct proof).

6. Learn the definitions and how they come into play when proving various types of statements.

Don'ts:

1. Argue from examples. A general statement can't be proved true by showing it is true for special cases.
2. Use the same letter to mean two different things within a proof.

Example \(\PageIndex{11}\):

Proof: Let \(n\in \mathbb{Z}\). Assume \(n\) is an even integer. Then \(n=2k,\) for some \(k \in \mathbb{Z}\). So \(n^2=4K^2=2(2k^2)\). Thus \(n^2=2k, k \in \mathbb{Z}\) is even. (The reader asks, does \(n=n^2\)?)

3. Assume what you are trying to prove. This is also known as begging the question. You can do it inadvertently in the middle of proof if you are not careful.