# Proof and Mathematical Induction

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.

#### Create learning materials about Proof and Mathematical Induction with our free learning app!

• Flashcards, notes, mock-exams and more
• Everything you need to ace your exams

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

• Proof by Counter Example
• 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\ge 1$.

SOLUTION:

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

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

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\phantom{\rule{0ex}{0ex}}4+6=10\phantom{\rule{0ex}{0ex}}6+8=14$

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

$6=2\left(3\right)\phantom{\rule{0ex}{0ex}}10=2\left(5\right)\phantom{\rule{0ex}{0ex}}14=2\left(7\right)$

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. $\square$ This means exactly the same thing as Q.E.D. $⇒$ This implies that. So you would use this when one statement directly implied another. $⇔$ 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=2k$, ${a}^{2}={\left(2k\right)}^{2}=4{k}^{2}$

$\therefore 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\left(n\right)={5}^{n}+8n+3$is divisible by 4 for all$n\in \mathrm{ℤ}+$.

SOLUTION:

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

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\left(k\right)={5}^{k}+8k+3=4m$, 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\left(k+1\right)={5}^{k+1}+8\left(k+1\right)+3$

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

$f\left(k+1\right)={5}^{k}\left(4+1\right)+8k+8+3\phantom{\rule{0ex}{0ex}}=4\left({5}^{k}\right)+{5}^{k}+8k+8+3$

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

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

Step 4: Therefore based on$f\left(k\right)$being a multiple of 4,$f\left(k+1\right)$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\left(r+1\right)}=\frac{n}{n+1}$for all$n\ge 1$.

SOLUTION:

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

$\sum _{1}^{1}\frac{1}{r\left(r+1\right)}=\frac{1}{1\left(1+1\right)}=\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\left(r+1\right)}=\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\left(r+1\right)}=\sum _{r=1}^{k}\frac{1}{r\left(r+1\right)}+\frac{1}{\left(k+1\right)\left(k+2\right)}\phantom{\rule{0ex}{0ex}}\sum _{r=1}^{k}\frac{1}{r\left(r+1\right)}+\frac{1}{\left(k+1\right)\left(k+2\right)}=\frac{1}{\left(k+1\right)\left(k+2\right)}+\frac{k}{k+1}$

If we simplify this out we get:

$\frac{k}{k+1}+\frac{1}{\left(k+1\right)\left(k+2\right)}=\frac{k\left(k+2\right)}{\left(k+1\right)\left(k+2\right)}+\frac{1}{\left(k+1\right)\left(k+2\right)}\phantom{\rule{0ex}{0ex}}\frac{k\left(k+2\right)}{\left(k+1\right)\left(k+2\right)}+\frac{1}{\left(k+1\right)\left(k+2\right)}=\frac{{k}^{2}+2k+1}{\left(k+1\right)\left(k+2\right)}\phantom{\rule{0ex}{0ex}}\frac{{k}^{2}+2k+1}{\left(k+1\right)\left(k+2\right)}=\frac{\left(k+1\right)\left(k+1\right)}{\left(k+1\right)\left(k+2\right)}$

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

$\frac{\left(k+1\right)}{\left(k+2\right)}$, 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\ge 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.

#### Flashcards in Proof and Mathematical Induction 11

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

We have 14,000 flashcards about Dynamic Landscapes.

What is mathematical induction?

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

How to prove mathematical induction?

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.

What are the principles of mathematical induction?

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.

How to use mathematical induction?

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

What is mathematical induction with example?

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.

## Test your knowledge with multiple choice flashcards

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

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

There are prime numbers divisible by 6.

StudySmarter is a globally recognized educational technology company, offering a holistic learning platform designed for students of all ages and educational levels. Our platform provides learning support for a wide range of subjects, including STEM, Social Sciences, and Languages and also helps students to successfully master various tests and exams worldwide, such as GCSE, A Level, SAT, ACT, Abitur, and more. We offer an extensive library of learning materials, including interactive flashcards, comprehensive textbook solutions, and detailed explanations. The cutting-edge technology and tools we provide help students create their own learning materials. StudySmarter’s content is not only expert-verified but also regularly updated to ensure accuracy and relevance.

##### StudySmarter Editorial Team

Team Math Teachers

• Checked by StudySmarter Editorial Team