Mathematics - Discrete Mathematics - Proof Strategies (part 2)

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 q_i '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, n² - 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 41², 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 ≥ n₀:

prove that P(n₀) 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) = k² 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

Images

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

Introduction → Discrete Mathematics, Why Discrete Math, Series Outline
Sets → Set Theory, Sets (Representation, Common Notations, Cardinality, Types)
Set Operations → Venn Diagrams, Set Operations, Properties and Laws
Sets and Relations → Cartesian Product of Sets, Relation and Function Terminology (Domain, Co-Domain and Range, Types and Properties)
Relation Closures → Relation Closures (Reflexive, Symmetric, Transitive), Full-On Example
Equivalence Relations → Equivalence Relations (Properties, Equivalent Elements, Equivalence Classes, Partitions)
Partial Order Relations and Sets → Partial Order Relations, POSET (Elements, Max-Min, Upper-Lower Bounds), Hasse Diagrams, Total Order Relations, Lattices
Combinatorial Principles → Combinatorics, Basic Counting Principles (Additive, Multiplicative), Inclusion-Exclusion Principle (PIE)
Combinations and Permutations → Factorial, Binomial Coefficient, Combination and Permutation (with / out repetition)
Combinatorics Topics → Pigeonhole Principle, Pascal's Triangle and Binomial Theorem, Counting Derangements
Propositions and Connectives → Propositional Logic, Propositions, Connectives (∧, ∨, →, ↔ and ¬)
Implication and Equivalence Statements → Truth Tables, Implication, Equivalence, Propositional Algebra
Proof Strategies (part 1) → Proofs, Direct Proof, Proof by Contrapositive, Proof by Contradiction

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!