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.

Proof and Mathematical Induction Proof and Mathematical Induction

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

  • Instand access to millions of learning materials
  • Flashcards, notes, mock-exams and more
  • Everything you need to ace your exams
Create a free account
Contents
Table of contents

    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 of2nare odd, forn1.

    SOLUTION:

    If we letn=2,22=4

    4 cannot be written as2n+1, withn.

    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.

    2+4=64+6=106+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.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 that2is irrational.

    SOLUTION:

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

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

    Let2=ab, whereabis a fraction in its' simplest form.

    Then if we square both sides:

    2=a2b2

    2b2=a2

    amust be even, this is becausea2is even and the square root of an even number is even.

    Leta=2k, a2=(2k)2=4k2

    4k2=2b2

    2k2=b2

    This meansb2is even. Therefore it means thatbis even.

    If bothaandbare even, this means thatab, is not in its simplest form.

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

    Therefore2is 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 thatf(n)=5n+8n+3is divisible by 4 for alln+.

    SOLUTION:

    Step 1: Firstly we need to testn=1, this givesf(1)=51+8(1)+3=16=4(4).

    So this is a multiple of 4.

    Step 2: Assume that whenn=k, the statement is correct.

    If we write this in mathematical notation we getf(k)=5k+8k+3=4m, where m is a positive number.

    Step 3: Now let's use the fact thatn=kis true to prove that forn=k+1:

    f(k+1)=5k+1+8(k+1)+3

    f(k+1)=(5k)(5)1+8k+8+3

    f(k+1)=5k(4+1)+8k+8+3 =4(5k)+5k+8k+8+3

    Now we substitute4minstead of5k+8k+3in thef(k+1), we get:

    f(k+1)=4m+4(5k)+8=4(m+5k+2)

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

    So this is true forn=1, and for somen=k, it is true for somen=k+1.

    Therefore the conjecture has been proven.

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

    Prove by mathematical induction thatr=1n1r(r+1)=nn+1for alln1.

    SOLUTION:

    Step 1: Firstly we need to test the case whenn=1.

    111r(r+1)=11(1+1)=12=nn+1

    Step 2: We assume that the case ofn=kis correct.

    r=1k1r(r+1)=kk+1

    Step 3: Now using the fact we need to test forn=k+1:

    r=1k+1 1r(r+1)=r=1k 1r(r+1)+1(k+1)(k+2)r=1k 1r(r+1)+1(k+1)(k+2)=1(k+1)(k+2)+kk+1

    If we simplify this out we get:

    kk+1+1(k+1)(k+2)=k(k+2)(k+1)(k+2)+1(k+1)(k+2)k(k+2)(k+1)(k+2)+1(k+1)(k+2)=k2+2k+1(k+1)(k+2)k2+2k+1(k+1)(k+2)=(k+1)(k+1)(k+1)(k+2)

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

    (k+1)(k+2), if we go back to the fact thatn=k+1, k+1k+2=nn+1

    Step 4: Therefore it has been proven for whenn=1, and for somen=kit has been proven forn=k+1. Therefore it is true for alln1.

    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

    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. 

    Next

    Discover learning materials with the free StudySmarter app

    Sign up for free
    1
    About StudySmarter

    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.

    Learn more
    StudySmarter Editorial Team

    Team Math Teachers

    • 8 minutes reading time
    • Checked by StudySmarter Editorial Team
    Save Explanation

    Study anywhere. Anytime.Across all devices.

    Sign-up for free

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

    Join over 22 million students in learning with our StudySmarter App

    The first learning app that truly has everything you need to ace your exams in one place

    • Flashcards & Quizzes
    • AI Study Assistant
    • Study Planner
    • Mock-Exams
    • Smart Note-Taking
    Join over 22 million students in learning with our StudySmarter App

    Get unlimited access with a free StudySmarter account.

    • Instant access to millions of learning materials.
    • Flashcards, notes, mock-exams, AI tools and more.
    • Everything you need to ace your exams.
    Second Popup Banner