Proof and Mathematical Induction

TABLE OF CONTENTS :

TABLE OF CONTENTS

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Nie wieder prokastinieren mit unseren Lernerinnerungen.

The proof is a very important element of mathematics. As mathematicians, we cannot believe a fact unless it has been fully proved by other facts we know.

There are a few key types of proofs we will look at briefly. These are:

Proof by Counter Example
Proof by Contradiction
Proof by Exhaustion

We will then move on to more difficult elements of proof, a special proof called mathematical induction.

These proofs are relatively straightforward and methodical, however, we will look at a few tricks one can use to help speed up the process.

What is Proof By Counter-Example?

Proof by counter-example is probably one of the more basic proofs we will look at. It pretty much is what it states and involves proving something by finding a counterexample.

The steps are as follows.

Step	Why?
State your conjecture and what you need to prove clearly.	To demonstrate what are aim is from this proof.
Find a counter example, we can do this by testing examples and eventually we will be able to find a good example.	This will disprove our conjecture.

Conjecture: Statement of what we are trying to prove or disprove.

Let's look at a short example to help us figure out what's going on.

Disprove by counterexample that all values of $2^{n}$ are odd, for $n \geq 1$ .

SOLUTION:

If we let $n = 2$ , $2^{2} = 4$

4 cannot be written as $2 n + 1$ , with $n \in ℤ$ .

So 4 is not odd.

We have found a counterexample to disprove the conjecture.

What is proof by exhaustion?

Proof by exhaustion involves testing all relevant examples and checking they all satisfy the conjecture. This, as used when there are limited cases, therefore, testing all relevant examples, will not take a long time. Let's look at how we do this as a series of steps:

Step	Why?
State your conjecture.	Find our aim for our proof.
Find all necessary examples to test.	Allows us to see what cases we need to test.
Test all relevant cases.	Checks all of our 'exhausted' cases work.
Make a statement about your proof.	Summarises the proof nicely.

Let's look at a short example as to how this works.

Prove by exhaustion that consecutive positive even numbers under 10, sum even numbers.

SOLUTION:

We want to see that the sum of two consecutive, positive even numbers under 10 is even.

Therefore the numbers we are going to use are 2,4,6 and 8.

$2 + 4 = 6 4 + 6 = 10 6 + 8 = 14$

6, 10 and 14 are all even numbers as they are all multiples of 2:

$6 = 2 (3) 10 = 2 (5) 14 = 2 (7)$

Therefore these sums are all even numbers.

So our conjecture has been proven.

There are a few useful symbols that we can use during and after we have finished a proof. This can make our proof look a little fancier. These are:

Symbol	Explanation
Q.E.D	Q.E.D stands for quod erat demonstrandum. This is the Latin for it has been proven.
$□$	This means exactly the same thing as Q.E.D.
$\Rightarrow$	This implies that. So you would use this when one statement directly implied another.
$\Leftrightarrow$	When two statements both imply each other this arrow is used.
∴	These three dots signify therefore, we use a statement of fact as a base for a new statement of fact e.g. a=2 ∴ a+2=4.

What is proof by contradiction?

Proof by contradiction is the process in which we attempt to prove the opposite of what we are asked for. Then realize that there is a contradiction in our listed proof.

There isn't really a list of steps to this. we just start off by trying to prove the opposite then use algebraic manipulation to eventually show this is wrong. Let's look at a key example of this, which should make enough sense.

Prove that $\sqrt{2}$ is irrational.

SOLUTION:

Firstly let's break down what we are being asked. We want to show that $\sqrt{2}$ cannot be written as a fraction.

So let's try and prove it is a fraction and find our contradiction.

Let $\sqrt{2} = \frac{a}{b}$ , where $\frac{a}{b}$ is a fraction in its' simplest form.

Then if we square both sides:

$2 = \frac{a^{2}}{b^{2}}$

$2 b^{2} = a^{2}$

$a$ must be even, this is because $a^{2}$ is even and the square root of an even number is even.

Let $a = 2 k$ , $a^{2} = {(2 k)}^{2} = 4 k^{2}$

$∴ 4 k^{2} = 2 b^{2}$

$2 k^{2} = b^{2}$

This means $b^{2}$ is even. Therefore it means that $b$ is even.

If both $a$ and $b$ are even, this means that $\frac{a}{b}$ , is not in its simplest form.

This is a contradiction as we originally assumed $\frac{a}{b}$ was in its simplest form.

Therefore $\sqrt{2}$ is not rational and is irrational.

So in this example what we've done is used algebraic manipulation and basic mathematical fact to move some terms around and show that something is irrational. Therefore, whenever we get a question like this all we do is use algebra and facts about numbers to show we have a contradiction.

In Latin this is known as reductio ad absurdum, it essentially translates to proof by absurd so assuming something wrong and finding a contradiction.

What is mathematical induction?

Mathematical induction is the process in which we use previous values to find new values. So we use it when we are trying to prove something is true for all values. So here are the list of steps to how we would answer a general question:

Prove that "conjecture" is true for all values n≥m.

Step	Why?
1. Prove is true for our lowest value, (n=m in this case).	Shows that our lower bounded value is true.
2. Assume it is true for the value n=k.	We assume that the conjecture is true for some value in our range to use in future reference.
3. Use the fact that n=k is true, prove that n=k+1 is true.	This shows that for some n=k, n=k+1 is true. By induction this means values are true.
4. Make a statement to conclude this in the structure:It has been prove for n=m, and for some n=k, n=k+1 is true. So the conjecture is true for all values n≥m.	This gives a summary statement to our proof and allows us to see our aim proven.

Let's look at two examples of this, one which is more general and one which is specific to series and sequences.

Prove by mathematical induction that $f (n) = 5^{n} + 8 n + 3$ is divisible by 4 for all $n \in ℤ +$ .

SOLUTION:

Step 1: Firstly we need to test $n = 1$ , this gives $f (1) = 5^{1} + 8 (1) + 3 = 16 = 4 (4)$ .

So this is a multiple of 4.

Step 2: Assume that when $n = k,$ the statement is correct.

If we write this in mathematical notation we get $f (k) = 5^{k} + 8 k + 3 = 4 m$ , where m is a positive number.

Step 3: Now let's use the fact that $n = k$ is true to prove that for $n = k + 1$ :

$f (k + 1) = 5^{k + 1} + 8 (k + 1) + 3$

$f (k + 1) = (5^{k}) {(5)}^{1} + 8 k + 8 + 3$

$f (k + 1) = 5^{k} (4 + 1) + 8 k + 8 + 3 = 4 (5^{k}) + 5^{k} + 8 k + 8 + 3$

Now we substitute $4 m$ instead of $5^{k} + 8 k + 3$ in the $f (k + 1)$ , we get:

$f (k + 1) = 4 m + 4 (5^{k}) + 8 = 4 (m + 5^{k} + 2)$

Step 4: Therefore based on $f (k)$ being a multiple of 4, $f (k + 1)$ is a multiple of 4.

So this is true for $n = 1$ , and for some $n = k$ , it is true for some $n = k + 1$ .

Therefore the conjecture has been proven.

Let's look at another example specific to series and sequences.

Prove by mathematical induction that $\sum_{r = 1}^{n} \frac{1}{r (r + 1)} = \frac{n}{n + 1}$ for all $n \geq 1$ .

SOLUTION:

Step 1: Firstly we need to test the case when $n = 1$ .

$\sum_{1}^{1} \frac{1}{r (r + 1)} = \frac{1}{1 (1 + 1)} = \frac{1}{2} = \frac{n}{n + 1}$

Step 2: We assume that the case of $n = k$ is correct.

$\sum_{r = 1}^{k} \frac{1}{r (r + 1)} = \frac{k}{k + 1}$

Step 3: Now using the fact we need to test for $n = k + 1$ :

$\sum_{r = 1}^{k + 1} \frac{1}{r (r + 1)} = \sum_{r = 1}^{k} \frac{1}{r (r + 1)} + \frac{1}{(k + 1) (k + 2)} \sum_{r = 1}^{k} \frac{1}{r (r + 1)} + \frac{1}{(k + 1) (k + 2)} = \frac{1}{(k + 1) (k + 2)} + \frac{k}{k + 1}$

If we simplify this out we get:

$\frac{k}{k + 1} + \frac{1}{(k + 1) (k + 2)} = \frac{k (k + 2)}{(k + 1) (k + 2)} + \frac{1}{(k + 1) (k + 2)} \frac{k (k + 2)}{(k + 1) (k + 2)} + \frac{1}{(k + 1) (k + 2)} = \frac{k^{2} + 2 k + 1}{(k + 1) (k + 2)} \frac{k^{2} + 2 k + 1}{(k + 1) (k + 2)} = \frac{(k + 1) (k + 1)}{(k + 1) (k + 2)}$

If we cancel out the term $(k + 1)$ from the numerator and denominator we get:

$\frac{(k + 1)}{(k + 2)}$ , if we go back to the fact that $n = k + 1$ , $\frac{k + 1}{k + 2} = \frac{n}{n + 1}$

Step 4: Therefore it has been proven for when $n = 1$ , and for some $n = k$ it has been proven for $n = k + 1$ . Therefore it is true for all $n \geq 1$ .

So we can see that just through algebraic manipulation and using some rules about series we can prove conjectures for all values.

Proof and Mathematical Induction - Key takeaways

There are three main types of proof: counterexample, exhaustion, and contradiction.
Counterexample is relatively straightforward and involves finding an example to disprove a statement.
Exhaustion involves testing all relevant cases and seeing if they are true.
Contradiction involves attempting to prove the opposite and finding that the statement is contradicted.
Mathematical Induction involves testing the lowest case to be true. Then assuming the conjecture is true for one case before using that fact to prove the case one above the previous case is true.

Frequently Asked Questions about Proof and Mathematical Induction

Mathematical induction is the process in which we use previous values to find new values.

Mathematical Induction is proved by testing the lowest case to be true. Then assuming the conjecture is true for one case before using that fact to prove the case one above the previous case is true.

The principle of mathematical induction is - Every nonnegative integer belongs to F if F is hereditary and integer 0 belongs to class F. Also every positive integer belongs to F if F is hereditary and integer 1 belongs to F.

Mathematical induction is used by taking the base step, inductive step, and conclusion.

Mathematical induction is a proof technique. For example, we can prove that n(n+1)(n+5) is a multiple of 3 by using mathematical induction.

Flashcards in Proof and Mathematical Induction11 Start learning

What is proof by counter example?

Proof by counter example is proving something by finding a counterexample.

Statement of what we are trying to prove or disprove is called?

Solution

Which value of x is a counterexample of 5x > 4x?

There are prime numbers divisible by 6.

True

Meaning of proof by exhaustion.

Proof by exhaustion involves testing all relevant examples and checking they all satisfy the conjecture.

When is proof by exhaustion used?

Proof by exhaustion is used when conjecture can be reduced to a finite number of cases.

Learn with 11 Proof and Mathematical Induction flashcards in the free StudySmarter app

Already have an account? Log in

More about Proof and Mathematical Induction

Save Article

How would you like to learn this content?

Creating flashcards

Studying with content from your peer

Taking a short quiz

How would you like to learn this content?

Creating flashcards

Studying with content from your peer

Taking a short quiz

Free math cheat sheet!

Everything you need to know on . A perfect summary so you can easily remember everything.

Email Address*

Find Study Materials for

Create Study Materials

Proof and Mathematical Induction

What is Proof By Counter-Example?

What is proof by exhaustion?

What is proof by contradiction?

What is mathematical induction?

Proof and Mathematical Induction - Key takeaways

Frequently Asked Questions about Proof and Mathematical Induction

Test your knowledge with multiple choice flashcards

Join over 22 million students in learning with our StudySmarter App

This is still free to read, it's not a paywall.

You need to register to keep reading

This is still free to read, it's not a paywall.

You need to register to keep reading

Entdecke Lernmaterial in der StudySmarter-App

Proof and Mathematical Induction

What is Proof By Counter-Example?

What is proof by exhaustion?

What is proof by contradiction?

What is mathematical induction?

Proof and Mathematical Induction - Key takeaways

Frequently Asked Questions about Proof and Mathematical Induction

What is mathematical induction?

How to prove mathematical induction?

What are the principles of mathematical induction?

How to use mathematical induction?

What is mathematical induction with example?

Test your knowledge with multiple choice flashcards

Join the StudySmarter App and learn efficiently with millions of flashcards and more!

Learn with 11 Proof and Mathematical Induction flashcards in the free StudySmarter app

Learn with 11 Proof and Mathematical Induction flashcards in the free StudySmarter app

Join over 22 million students in learning with our StudySmarter App

This is still free to read, it's not a paywall.

You need to register to keep reading

This is still free to read, it's not a paywall.

You need to register to keep reading

Create a free account to save this explanation.

Entdecke Lernmaterial in der StudySmarter-App

Join over 22 million students in learning with our StudySmarter App

Join over 22 million students in learning with our StudySmarter App