Skip to main content
Mathematics LibreTexts

0.0: Introduction to proofs

  • Page ID
    10717
  • This page is a draft and is under active development. 

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

    ( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\id}{\mathrm{id}}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\kernel}{\mathrm{null}\,}\)

    \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\)

    \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\)

    \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

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

     


    This page titled 0.0: Introduction to proofs is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.

    • Was this article helpful?