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\)).

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.

Example \(\PageIndex{1}\)

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

Answer

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.

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.

Example\(\PageIndex{2}\)

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

Answer

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.

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 {a}{b}\), where \(a \in \mathbb{Z}, b \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.

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}\).

Answer

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\).

Answer

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\).

Answer

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\).

Answer

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\).◻