Mathematics - Discrete Mathematics - Proof Strategies (part 2)

in STEMGeeks8 months ago

[Image 1]

Introduction

Hey it's a me again @drifter1!

Today we continue with Mathematics, and more specifically the branch of "Discrete Mathematics", in order to get into Proof Strategies. This is part 2. You can find part 1 here.

So, without further ado, let's get straight into it!


Proof by Cases

Another useful strategy is proving through cases, which can be summarized as follows: In order to prove that p is true:

  • prove q → p, and
  • prove ¬q → p

for statement q.

That way the truth value of q doesn't matter as p will be true no matter the case. Contradictions are also commonly used when applying this technique.

This can be easily generalized into proving that at least one of the chosen qi 's is true in order to conclude p. Of course, all possibilities have to be considered.

Example

This is much easier to explain through an example...

Consider the following statement:

There are two cases for n: it can be even or odd. So, in order to prove for all n what needs to be done is proving that each case is true.

1: n is even:

2: n is odd:

And so, the statement is true for any integer n.


Proof by Counter-Example

Proving a statement by providing an counter-example is never okay in most cases. Many logical statements are generalizations for all naturals, integers, reals etc. and so picking one or even multiple cases that "work" doesn't allow for such an generalization.

But, don't "strike out" such a strategy completely! Where providing a counter-example really shines is when trying to proof that a statement is false. Even one counter-example is sufficient for proving that such so called existential statements are false.

Example

For example, n2 - n + 41 is not a prime number for all integers n.

Trying out small integers 1, 2 and 3 yields only primes: 41, 43, 47. This may trick us into generalizing for all integers! But, in the case of n = 41 the result is 412, which clearly isn't a prime. So, this counter-example is sufficient for disproving the statement!


Biconditional Proof

From the definition of an biconditional statement, proving statements of the form p ↔ q is as simple as proving that each of the two implications: p → q and q → p, is true.


Mathematical Induction

Proving the validity of statements, which involve only natural numbers is mostly done using a principle known as Mathematical Induction.

In order to prove that a statement P(n) is true for all n ≥ n0:

  • prove that P(n0) is true
  • assuming that P(k) is true prove that P(k + 1) is true

Example

A great example is the sum of odds:

First of all, P(n) = 1 for n = 1, and so the statement holds for n = 1.

Assuming that the statement holds for P(k), let's now prove that it's also true for P(k + 1)...

Starting from P(k) = k2 let's add 2k + 1 to both sides:

The right-hand side is a well-known expansion formula (square of binomial) and so the result is:

which shows that the statement holds for P(k + 1) as well.

Therefore, the statement is true for all naturals n ≥ 1.


RESOURCES:

References

  1. https://www.javatpoint.com/discrete-mathematics-tutorial
  2. http://discrete.openmathbooks.org/dmoi3.html
  3. https://brilliant.org/wiki/discrete-mathematics/
  4. https://ece.iisc.ac.in/~parimal/2015/proofs/lecture-02.pdf
  5. https://www.cs.amherst.edu/~djvelleman/pd/help/Strategies.html

Images

  1. https://en.wikipedia.org/wiki/File:Modus_ponens_logical_form.jpg

Mathematical equations used in this article, have been generated using quicklatex.

Block diagrams and other visualizations were made using draw.io.


Previous articles of the series


Final words | Next up

And this is actually it for today's post!

Next time we will continue on with a post on Sequences and Recurrence Relations...

See ya!

Keep on drifting!

Posted with STEMGeeks