Log In Start studying!

Select your language

Suggested languages for you:
StudySmarter - The all-in-one study app.
4.8 • +11k Ratings
More than 3 Million Downloads
Free
|
|

Proof and Mathematical Induction

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.

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.

StepWhy?
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 ofare odd, for.

SOLUTION:

If we let,

4 cannot be written as, with.

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:

StepWhy?
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.

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

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.DQ.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.
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 thatis irrational.

SOLUTION:

Firstly let's break down what we are being asked. We want to show thatcannot be written as a fraction.

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

Let, whereis a fraction in its' simplest form.

Then if we square both sides:

must be even, this is becauseis even and the square root of an even number is even.

Let,

This meansis even. Therefore it means thatis even.

If bothandare even, this means that, is not in its simplest form.

This is a contradiction as we originally assumedwas in its simplest form.

Thereforeis 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.

StepWhy?
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 thatis divisible by 4 for all.

SOLUTION:

Step 1: Firstly we need to test, this gives.

So this is a multiple of 4.

Step 2: Assume that whenthe statement is correct.

If we write this in mathematical notation we get, where m is a positive number.

Step 3: Now let's use the fact thatis true to prove that for:

Now we substituteinstead ofin the, we get:

Step 4: Therefore based onbeing a multiple of 4,is a multiple of 4.

So this is true for, and for some, it is true for some.

Therefore the conjecture has been proven.

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

Prove by mathematical induction thatfor all.

SOLUTION:

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

Step 2: We assume that the case ofis correct.

Step 3: Now using the fact we need to test for:

If we simplify this out we get:

If we cancel out the termfrom the numerator and denominator we get:

, if we go back to the fact that,

Step 4: Therefore it has been proven for when, and for someit has been proven for. Therefore it is true for all.

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. 

Final Proof and Mathematical Induction Quiz

Question

What is proof by counter example?

Show answer

Answer

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

Show question

Question

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

Show answer

Answer

Solution

Show question

Question

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

Show answer

Answer

1

Show question

Question

There are prime numbers divisible by 6. 

Show answer

Answer

True

Show question

Question

Meaning of proof by exhaustion.

Show answer

Answer

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

Show question

Question

When is proof by exhaustion used?

Show answer

Answer

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

Show question

Question

Is n²-1 a multiple of 3, when n is not a multiple of 3 shown using proof by exhaustion?


Show answer

Answer

Yes

Show question

Question

When is proof by exhaustion is called complete?

Show answer

Answer

All values are true

Show question

Question

Define proof by contradiction.

Show answer

Answer

Proof by contradiction is the process in which the opposite of what is asked for is proved.

Show question

Question

Define mathematical induction.

Show answer

Answer

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

Show question

Question

The lowest value is kept what when using mathematical induction?

Show answer

Answer

True

Show question

More about Proof and Mathematical Induction
60%

of the users don't pass the Proof and Mathematical Induction quiz! Will you pass the quiz?

Start Quiz

Discover the right content for your subjects

No need to cheat if you have everything you need to succeed! Packed into one app!

Study Plan

Be perfectly prepared on time with an individual plan.

Quizzes

Test your knowledge with gamified quizzes.

Flashcards

Create and find flashcards in record time.

Notes

Create beautiful notes faster than ever before.

Study Sets

Have all your study materials in one place.

Documents

Upload unlimited documents and save them online.

Study Analytics

Identify your study strength and weaknesses.

Weekly Goals

Set individual study goals and earn points reaching them.

Smart Reminders

Stop procrastinating with our study reminders.

Rewards

Earn points, unlock badges and level up while studying.

Magic Marker

Create flashcards in notes completely automatically.

Smart Formatting

Create the most beautiful study materials using our templates.

Sign up to highlight and take notes. It’s 100% free.

Get FREE ACCESS to all of our study material, tailor-made!

Over 10 million students from across the world are already learning smarter.

Get Started for Free
Illustration