Introduction

Mathematics is an exact science whereby new knowledge is created through rigorous proofs of the universality of hypothesis by the application of axioms. Thus, it is crucial to have systems of proofs in order to establish mathematical validity of arguments and hypotheses.

There are many different types of proofs, however in computer science, we predominantly are concerned with Proof through Induction, and Proof through Deductive Reasoning. In this section, we will consider these two methods of proof.

Proof by Mathematical Induction

Proof by Induction is a mechanism of proving a property in a certain base case (usually n=1), and then proving that the property is applicable for all following cases. Proof by Induction has the following steps:

1. Base Case: prove the given statement for the first natural number. (n = 1)
2. Inductive Step: assuming that the statement is true for (n = k), prove that the given statement for any one natural number is true for (n = k + 1).

From these two steps, and by the rule of mathematical induction, we consider the given statement is established for all natural numbers.

Examples

Example 1

For example, we can prove by induction that all integers of the form 2n + 1 are odd:

(i) For n = 1, 2n + 1 = 2(1) + 1 = 3, and 3 is odd. Thus P(1) is true.
(ii) For 2n + 1 for some n, 2(n+1) + 1 = (2n+1) + 2. If 2n + 1 is odd, then (2n+1) + 2 must also be odd, because adding 2 to an odd number results in an odd number. So P(n+1) is true if P(n) is true.

Thus 2n + 1 is odd, for all natural numbers n.

Example 2

Prove that 1 + 2 + 3 + ... + n = [n(n + 1)]/2

In this example, we can watch the full proof with working in the video below.

Example 3

Prove that (a^m)^n = a ^mn

Once again, here is the full proof with working in video format.

Proof by Deductive Reasoning

A second approach to mathematical proofs is through the application of Propositional Logic laws. As we saw in the previous section, to construct a proof, we string together Propositional Logic Laws. Each line in the proof, by convention, is numbered with sequential numbers starting from 1. Next to each step we justify the progression with the name of the law being used.

Proofs by Propositional Logic validates statements from axioms, and uses these validated statements to eventual prove a theorem.

Exercises

Continue to next section: Probability