# Proof and Mathematical Induction

## The Significance of Proof in Mathematics

Proof is a fundamental element in the realm of mathematics. As mathematicians, we depend on proof to validate the accuracy of a statement based on established facts. In this article, we will delve into the different types of proof and methodologies that can aid us in this process.

## Types of Proofs

- Proof by Counter-Example
- Proof by Contradiction
- Proof by Exhaustion

As we progress to more intricate concepts, we will also discuss the unique proof technique known as mathematical induction.

## Proof by Counter-Example

This is a basic form of proof where we disprove a statement by finding a contradictory example. The steps involved are as follows:

- Conjecture: A statement that we are trying to disprove or prove.
- Find a counterexample that contradicts the conjecture.

Let's consider an example:

**Conjecture:** All prime numbers are odd.

**Counterexample:** 2 is a prime number, yet it is not odd. Therefore, the conjecture is disproven.

## Proof by Exhaustion

This type of proof involves examining all relevant instances and verifying if they support the conjecture. This approach is useful when the number of cases to consider is limited. The steps involved are:

- List all relevant instances.
- Check if they all align with the conjecture.

Let's see this in action:

**Conjecture:** The sum of two consecutive, positive even numbers under 10 is even.

**Instances:** 2, 4, 6, and 8

We can observe that the sums of these pairs (2+4, 4+6, and 6+8) are all even numbers. Hence, our conjecture is proven.

## Useful Symbols in Proofs

There are symbols that we can use during and after a proof to improve its organization:

- ∴
*(Therefore)*: To signify that our conclusion logically follows from the premises. - ∵
*(Since)*: To indicate that a statement is true based on a preceding statement. - QED
*(Quod erat demonstrandum)*: Translated as "which was to be demonstrated," and is used to signal the end of a proof.

## Proof by Contradiction

In this type of proof, we attempt to prove the opposite of what is being asked and demonstrate a contradiction in our reasoning. Let's see an example:

**Prove:** √2 is irrational.

**Assumption:** √2 can be expressed as a fraction.

Through algebraic manipulation, we can arrive at the equation 2n² = m², where m and n are whole numbers. This indicates that m² must be even, and since the square of an even number is always even, m must also be even. However, this goes against our initial assumption that √2 was in its simplest form. Thus, our assumption is proven wrong, and √2 is irrational.

This technique is also known as reductio ad absurdum, meaning proving something by its absurdity.

## Mathematical Induction

Mathematical induction is a technique used to prove that a statement holds for all values. The steps involved are:

- Prove the statement for a specific value (usually the smallest value).
- Assume that the statement is true for some value n.
- Based on this assumption, prove that the statement is also valid for n+1.
- Therefore, the statement is true for all values n≥m.

Let's see this in practice:

**Prove:** n² is divisible by 4 for all n≥1.

**Step 1:** For n=1, n²=1, and 1 is a multiple of 4.

**Step 2:** Assume that for some n, n² is divisible by 4.

**Step 3:** Based on this assumption, we can write (n+1)² = n²+2n+1. Since n² is divisible by 4, we can represent it as 4k, where k is a whole number. Substituting, we get (n+1)² = 4k+2n+1.

**Step 4:** We can rewrite this as (n+1)² = 2(2k+n)+1. As (2k+n) is also a whole number, (n+1)² is divisible by 2. Therefore, it is also divisible by 4.

Based on the above steps, we can see that the statement holds for n=1, and if it is true for some n, it is also true for n+1. Therefore, the statement is valid for all values n≥1.

These are just some of the techniques and methods utilized in mathematical proofs. With practice and a strong foundation in mathematics, anyone can become proficient in proving mathematical statements and theorems.

## Discovering the Power of Mathematical Induction

Mathematical induction is an essential tool in mathematics that allows us to verify conjectures for all values. Let's explore how to utilize this method and its principles to prove statements by examining previous values.

To demonstrate this, let's use the following example:

Prove by mathematical induction thatfor all.

### SOLUTION:

**Step 1:** First, we must test the case when.

**Step 2:** Next, we assume that the case ofis correct.

**Step 3:** Using this assumption, we can test for the following case:

By simplifying this, we get:

After canceling out theterm from the numerator and denominator, we are left with:

By referring back to our initial assumption, it is clear that this statement holds true for all values of.

**Step 4:** Therefore, we have proven the statement for when, and since it is true for some, it is true for all.

As we can see, by using simple algebraic manipulation and applying some series rules, we can verify conjectures for all values.

### Key Takeaways from Mathematical Induction

There are three main types of mathematical proofs: counterexample, exhaustion, and contradiction.

In contrast, counterexample is the easiest method, where we find an example that disproves a statement.

The exhaustion method involves testing all relevant cases and determining their validity.

Lastly, the contradiction method involves attempting to prove the opposite and finding that the statement is false.

On the other hand, mathematical induction focuses on testing the lowest case to be true. Then, assuming the conjecture is true for one case, we use that fact to prove the case one above the previous case to be true.

### The Three Steps for Using Mathematical Induction

To apply mathematical induction, we follow a simple three-step process:

**Base Step:**Test the lowest case to be true.**Inductive Step:**Assume the conjecture is true for one case and use that fact to prove the next case.**Conclusion:**Based on the inductive step, prove that the statement holds true for all values.

### Understanding Mathematical Induction Through an Example

Mathematical induction is a proof technique that utilizes the principles mentioned above to verify statements. For instance, we can use mathematical induction to demonstrate that n(n+1)(n+5) is a multiple of 3.