Proofs and induction · Definition

Direct proof

discrete mathematicsproofs

It is the default method in mathematics: move from what is known to what must be proved.

Definition

A direct proof of an implication \(p\Rightarrow q\) starts from the hypothesis \(p\) and, using definitions and previously proved results, chains steps until it reaches the conclusion \(q\).

\[p\Rightarrow\cdots\Rightarrow q\]

Almost every statement of the form «if \(p\), then \(q\)» is attacked this way first. Assume \(p\), translate the terms into their definitions, and manipulate until \(q\) appears. To prove that the square of an even integer is even, write \(n=2k\) and compute \(n^2=4k^2=2(2k^2)\): the result has the form of an even number.

The key is choosing the right representation. An even number is \(2k\); an odd one is \(2k+1\); «\(a\) divides \(b\)» means \(b=ak\) for some integer \(k\). With these definitions the proof reduces to algebra: if \(a=2k+1\) and \(b=2j+1\), then \(a+b=2(k+j+1)\), which is even.

A common mistake is to believe that a few examples prove a universal statement. Examples build intuition but do not prove; the proof must hold for an arbitrary element. By contrast, to refute a universal claim a single counterexample suffices: \(n^2+n+41\) is prime for \(n=1,2,\dots,39\), but not for \(n=40\).

When the direct route resists, one turns to contradiction or induction. Before that, always try writing the hypothesis with definitions: often the proof is two steps away.

Think about it

Prove directly that the sum of two even integers is even.

Let \(a=2k\) and \(b=2j\). Then \(a+b=2(k+j)\), a multiple of 2.

Exercises 10

  1. To prove directly that if \(n\) is even then \(n^2\) is even, one starts by writing:
  2. If \(n=2k+1\), what is \(n^2\) equal to?
  3. Let \(a=2k+1\) and \(b=2j+1\) be odd. Which expression shows that \(a+b\) is even?
  4. In a direct proof of \(p\Rightarrow q\), what do we do?
  5. Which of these starts is a direct proof of «if \(n\) is odd then \(n+1\) is even»?
  6. Let \(a=2x\) and \(b=2y\) be even. What follows about \(ab\)?
  7. We know \(a\mid b\) and \(b\mid c\), i.e. \(b=ak\) and \(c=bm\). How do we conclude \(a\mid c\)?
  8. Does checking that \(3^2=9\), \(5^2=25\) and \(7^2=49\) are odd prove that the square of every odd number is odd?
  9. To prove that if \(n\) is odd then \(8\mid n^2-1\), write \(n=2k+1\). What is \(n^2-1\) equal to?
  10. It is claimed that \(n^2+n+41\) is prime for every integer \(n\ge1\). Which value of \(n\) refutes it?

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §1.7
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §4.1
  • László Lovász, József Pelikán, Katalin Vesztergombi, Discrete Mathematics: Elementary and Beyond, 1st edition, Springer, 2003. Cap. 1