Sign In | Subscribe
Start learning today, and be successful in your academic & professional career. Start Today!
Loading video...
This is a quick preview of the lesson. For full access, please Log In or Sign up.
For more information, please see full course syllabus of Pre Calculus
  • Discussion

  • Study Guides

  • Practice Questions

  • Download Lecture Slides

  • Table of Contents

  • Transcription

  • Related Books

Bookmark and Share

Start Learning Now

Our free lessons will get you started (Adobe Flash® required).
Get immediate access to our entire library.

Sign up for Educator.com

Membership Overview

  • Unlimited access to our entire library of courses.
  • Search and jump to exactly what you want to learn.
  • *Ask questions and get answers from the community and our teachers!
  • Practice questions with step-by-step solutions.
  • Download lesson files for programming and software training practice.
  • Track your course viewing progress.
  • Download lecture slides for taking notes.
  • Learn at your own pace... anytime, anywhere!

Mathematical Induction

  • One of the most important ideas in mathematics is being able to prove something with total certainty. We can show not just that something works out, but that it will work every time, forever-it is mathematical fact. We show this with proof.
  • Mathematical induction is a form of proof that allows us to prove that a pattern holds true forever.
  • A good metaphor for the idea of induction is a never-ending line of dominoes. If we have two guarantees,
    1. The first domino will fall over;
    2. If a domino falls over, it will cause the next domino to fall over as well;
    then we know that all the dominoes in our infinitely long line of dominoes will fall over.
  • The principle of mathematical induction is basically the same idea as the above metaphor, except we replace "domino falling over" with "statement being true". Let P1, P2, P3, P4, ..., Pn, ... be some sequence of statements where n is a positive integer. If
    1. P1 is true, and
    2. If Pk is true for a positive integer k, then Pk+1 must also be true,
    then the statement Pn is true for all positive integers n.
  • Above, we call the first step the base case because it establishes the basis we are working from.
  • Above, the second step is called the inductive step since that is where the actual induction occurs. In the inductive step, the assumption "if Pk is true" is called the inductive hypothesis, because we must use this hypothesis to show Pk+1 will also be true.
  • It helps a lot to somehow include part of the statement for Pk when we are writing out Pk+1. This is because we will almost inevitably wind up using our inductive hypothesis (Pk is true) to show that Pk+1 is also true. But we can't use our hypothesis about Pk unless it somehow appears in Pk+1.
  • Check out the video to see a working example of the inductive hypothesis where each step is explained. Induction can be a little confusing at first, and it really helps to see it in action.

Mathematical Induction

Below is the general statement Pn.
Pn:     Buying n loaves of bread costs $(2.20 ·n).
Write out the statements P1, P7, Pk, and Pk+1.
  • A statement is just a string of words and/or symbols. In the case of the above statement, Pn is a statement that varies depending on the specific value used for n.
  • To find out what P1, P7, Pk, and Pk+1 are, we need to replace the n with the corresponding value. This is just simple substitution. Plug in the value you're working with for each place that n shows up.

    For P1, we have n=1, so substitute for every value of n in the general statement:
    P1:     Buying 1 loaves of bread costs $(2.20 ·1).
    We're close, but there are some minor issues. First off, there's a grammar problem: the plural is `loaves', the singular is `loaf'. Thus, since we're buying just one of them, we need to use the singular `loaf'. Second, because the multiplication is so simple, it doesn't really show any useful information, so we can simplify $(2.20 ·1) = $2.20. Putting these fixes in, we have
    P1:     Buying 1 loaf of bread costs $2.20.
  • To find the other statements, we just plug in the appropriate value for n:
    P7:     Buying 7 loaves of bread costs $(2.20 ·7).

    Pk:     Buying k loaves of bread costs $(2.20 ·k).

    Pk+1:     Buying (k+1) loaves of bread costs $(2.20 ·(k+1)).
    For each of these, the grammar is correct (we almost always treat variables as if they indicate the plural). For P7, it also works well to leave the cost as $(2.20 ·7), since that shows how to arrive at the price of all the bread: multiply the cost of one loaf by the number of loaves. The only minor improvement we could make is to Pk+1, where we could distribute: $(2.20 ·(k+1)) = $(2.20·k + 2.20). This makes it a little bit clearer that purchasing (k+1) loaves just adds the price of one more loaf to the cost of purchasing k loaves.
    Pk+1:     Buying (k+1) loaves of bread costs $(2.20·k + 2.20).
P1:     Buying 1 loaf of bread costs $2.20. P7:     Buying 7 loaves of bread costs $(2.20 ·7). Pk:     Buying k loaves of bread costs $(2.20 ·k). Pk+1:     Buying (k+1) loaves of bread costs $(2.20·k + 2.20).
Below is the general statement Pn.
Pn:     The number (n3n+2) is divisible by 2.
Write out the statements P1, P7, Pk, and Pk+1.
  • A statement is just a string of words and/or symbols. In the case of the above statement, Pn is a statement that varies depending on the specific value used for n.
  • To find out what P1, P7, Pk, and Pk+1 are, we need to replace the n with the corresponding value. This is just simple substitution. Plug in the value you're working with for each place that n shows up.

    For P1, we have n=1, so substitute for every value of n in the general statement:
    P1:     The number (131+2) is divisible by 2.
    The above is fine: although we could simplify the expression (13−1+2), doing so will not make the structure of the later statements any clearer, so we probably want to leave it like it is. That said, we could simplify to get the equivalent statement "The number 2 is divisible by 2." Simplifying to that would be quite useful if we wanted to verify the statement, like when doing a proof by mathematical induction.
  • To find the other statements, we just plug in the appropriate value for n:
    P7:     The number (737+2) is divisible by 2.

    Pk:     The number (k3k+2) is divisible by 2.

    Pk+1:     The number ((k+1)3(k+1)+2) is divisible by 2.


    [Once again, like for the statement P1, the above statement Pk+1 could be expanded and simplified, but it doesn't help us see the pattern of the statements. Leaving it in the above, unsimplified form is fine for now. If we were proving by induction, the next step would be to expand and simplify to help us work with it, but all we want is to write out the statement, so we're fine for now.]
P1:     The number (131+2) is divisible by 2. P7:     The number (737+2) is divisible by 2. Pk:     The number (k3k+2) is divisible by 2. Pk+1:     The number ((k+1)3(k+1)+2) is divisible by 2.
Below is the general statement Pn.
Pn:     15  + 25  + 35  + … + n5   =   n2·(2n2+2n−1)·(n+1)2

12
Write out the statements P1, P7, Pk, and Pk+1.
  • A statement is just a string of words and/or symbols. In the case of the above statement, Pn is a statement that varies depending on the specific value used for n.
  • To find out what P1, P7, Pk, and Pk+1 are, we need to replace the n with the corresponding value. This is just simple substitution. Plug in the value you're working with for each place that n shows up.

    For P1, we have n=1, so substitute for every value of n in the general statement. The hardest part here is probably figuring out what to do with the left side (the part with the `…′ in it). To understand what to do with the sum, first make sure you understand what the notation is indicating. The expression 15  + 25  + 35  + … + n5 means that we start off with 15, then we add the next number up raised to the fifth (25), then the next number up raised to the fifth (35), and we continue to repeat this process until we reach n and add n5. However, for P1, we have n=1. Thus the summation process ends as soon as it starts. The very first value of 15 means we have already reached n5, so we only have one term on the left for P1:
    P1:     15   =   12·(2·12+2·1−1)·(1+1)2

    12
  • To find the other statements, we just plug in the appropriate value for n:
    P7:     15  + 25  + 35  + … + 75   =   72·(2·72+2·7−1)·(7+1)2

    12

    Pk:     15  + 25  + 35  + … + k5   =   k2·(2k2+2k−1)·(k+1)2

    12

    Pk+1:     15  + 25  + 35  + … + (k+1)5   =   (k+1)2·(2(k+1)2+2(k+1)−1)·((k+1)+1)2

    12


    [Remarks: The above statement Pk+1 could be expanded and simplified, but it doesn't help us see the pattern of the statements. Leave it in the above, unsimplified form for now. If we were proving by induction, the next step would be to expand and simplify to help us work with it, but all we want is to write out the statement, so we're fine. Furthermore, if we were going to prove by induction, we'd want the last statement Pk+1 to somehow be connected to Pk. We could do this by rewriting the left-side sum to show the connection:
    15  + 25  + 35  + … + (k+1)5     =     15  + 25  + 35  + … + k5  + (k+1)5
    These are exactly the same, it's just showing one more element from the part covered by the ellipsis (…). But by doing this, it makes it much easier to see that Pk is connected to Pk+1, which would allow us to plug in from the statement of Pk. However, we weren't asked to prove this by induction, so we're fine to leave it in the original form for now.]
P1:     15   =  [(12·(2·12+2·1−1)·(1+1)2)/12] P7:     15  + 25  + 35  + … + 75   =  [(72·(2·72+2·7−1)·(7+1)2)/12] Pk:     15  + 25  + 35  + … + k5   =  [(k2·(2k2+2k−1)·(k+1)2)/12] Pk+1:     15  + 25  + 35  + … + (k+1)5   =  [((k+1)2·(2(k+1)2+2(k+1)−1)·((k+1)+1)2)/12]
Using mathematical induction, prove that the below is true for every positive integer.
2 + 4  + 6  + … + 2n   =  n(n+1)
  • (Note: Make sure that you've watched the video lesson before working on these problems. The concept of mathematical induction can be rather difficult when you're first learning it, and it's important to understand the idea behind it and the steps involved. The method is carefully explained in the video, but it will be assumed in the below steps that you are already familiar with the process.) To prove something by induction, we first need a general statement Pn that makes sense for any positive integer n (notice that we haven't proven it is true yet, it just can't be total nonsense). The problem is pretty clearly set up in such a format, so we can just take the equation itself as our general statement:
    Pn:     2 + 4  + 6  + … + 2n   =  n(n+1)
  • Now that we have our general statement, we need to accomplish the two parts of mathematical induction. We begin with the base case. Base Case: Here we show that P1 is true. First, let us see what P1 is: plugging in n=1 into our general statement, we get
    P1:     2   =  1·(1+1)
    [If you're confused by why the left-side is simply `2', remember that the left-side is the sum of all the even numbers from 2 up until 2n. Since n=1, that means it's the sum of all the even numbers from 2 up until 2·1 = 2, that is, it starts where it stops, so the sum is just `2'.]
  • Now that we know the statement of the base case, we must verify that it is indeed true. Just do this with some simple arithmetic:
  • P1:     2   =  1·(1+1)
    P1:     2  =  1·(2)
    P1:     2   =  2       
  • Great, the statement P1 is clearly true, so the base case is complete.
  • Once the base case is complete, we move on to the inductive step. This is where where we will spend most of our time and effort. The inductive step begins with the inductive hypothesis, the assumption that Pk is true. Inductive Step: We assume our inductive hypothesis:
    Inductive Hypothesis- Pk:  2 + 4  + 6  + … + 2k   =  k(k+1)    is true.
    Using this inductive hypothesis, we now show that the next statement (Pk+1) must be true as well. That is, using our above assumption, we want to show the below is true:
    Pk+1:     2 + 4  + 6  + … + 2(k+1)   =  (k+1) ·
    (k+1)+1
  • A key idea in induction is that we must use our inductive hypothesis of Pk to somehow prove that Pk+1 will be true as well. Thus, we need to make some portion of Pk appear in Pk+1 so that we can apply our hypothesis. Notice that we can rewrite the above formulation of Pk+1 to make it easier to see Pk in it:
    Pk+1:     2 + 4  + 6  + … + 2k  + 2(k+1)   =  (k+1) ·
    (k+1)+1
    We haven't changed anything, we've just shown an extra term that was "hiding" in the ellipsis (…). From there we can plug in our inductive hypothesis of
    Pk:  2 + 4  + 6  + … + 2k   =  k(k+1).
    Let us plug in. We have
    Pk+1:    
    2 + 4  + 6  + … + 2k
     + 2(k+1)   =  (k+1) ·
    (k+1)+1
    ,
    and we can clearly replace the bracketed [ ] part with what we know from our inductive hypothesis:

    k(k+1)
     + 2(k+1)   =  (k+1) ·
    (k+1)+1
  • Once we have managed to apply the inductive hypothesis, it is simply a matter of verifying that the equation is true.
  • k(k+1)  + 2(k+1)   =  (k+1) ·((k+1)+1)
    k2+k  + 2k+2   =  (k+1) ·(k+2)
    k2 + 3k + 2   =  k+ 3k + 2    
  • Excellent! Thus, from our inductive hypothesis that Pk is true, we have shown that Pk+1 must also be true.

    Therefore, by showing the base case and inductive step, the principle of mathematical induction says that the statement Pn must be true for all positive integers n. Thus we have shown that the below is true for all positive integers n:
    2 + 4  + 6  + … + 2n   =  n(n+1)       
Prove by induction. [By the nature of proof, it can't be given as just a single answer. Check out the steps to the problem if you want to see a version of the proof.]
Using mathematical induction, prove that the below is true for every positive integer.
1  + 6  + 11  + … + (5n−4)   =   n

2
(5n−3)
  • (Note: Make sure that you've watched the video lesson before working on these problems. The concept of mathematical induction can be rather difficult when you're first learning it, and it's important to understand the idea behind it and the steps involved. The method is carefully explained in the video, but it will be assumed in the below steps that you are already familiar with the process.) To prove something by induction, we first need a general statement Pn that makes sense for any positive integer n (notice that we haven't proven it is true yet, it just can't be total nonsense). The problem is pretty clearly set up in such a format, so we can just take the equation itself as our general statement:
    Pn:     1  + 6  + 11  + … + (5n−4)   =   n

    2
    (5n−3)
  • Now that we have our general statement of Pn, we need to show that the base case of P1 is true. Base Case:
    P1:     1   =   1

    2
    ·(5·1 −3)
    Just simplify the equation and verify that it is true.
  • 1   =  [1/2] ·(5·1 −3)
    1   =  [1/2] ·(2)
    1   =  1     Great, the statement P1 is clearly true, so the base case is complete.
  • Once the base case is complete, we move on to the inductive step. This is where we will spend most of our time and effort. The inductive step begins with the inductive hypothesis, the assumption that Pk is true. Inductive Step: We assume our inductive hypothesis:
    Inductive Hypothesis- Pk:  1  + 6  + 11  + … + (5k−4)   =   k

    2
    (5k−3)    is true.
    Using this inductive hypothesis, we now show that the next statement (Pk+1) must be true as well. That is, using our above assumption, we want to show the below is true:
    Pk+1:     1  + 6  + 11  + … + (5k−4)  + 
    5(k+1)−4
      =   k+1

    2

    5(k+1)−3
  • Notice how we wrote Pk+1 so that it included an easily recognizable part from our inductive hypothesis of Pk. This allows us to apply our hypothesis.
    Pk+1:    
    1  + 6  + 11  + … + (5k−4)
     + 
    5(k+1)−4
      =   k+1

    2

    5(k+1)−3
    We can easily substitute the bracketed portion [ ] for what we know from our inductive hypothesis Pk. Plug in:

    k

    2
    (5k−3)
     + 
    5(k+1)−4
      =   k+1

    2

    5(k+1)−3
    Now we just expand and simplify both sides until it is clear that the equation is true:
  • [(5k2−3k)/2]  + (5k + 5 −4)   =  [(k+1)/2] (5k+5−3)
    [(5k2−3k)/2]  + (5k+1)   =  [(k+1)/2] (5k+2)
    [(5k2−3k)/2]  + [(10k+2)/2]   =  [((k+1))/2] ·[((5k+2))/1]
    [(5k2 + 7k + 2)/2]   =  [(5k2+7k+2)/2]     Excellent! Thus, from our inductive hypothesis that Pk is true, we have shown that Pk+1 must also be true.

    Therefore, by showing the base case and inductive step, the principle of mathematical induction says that the statement Pn must be true for all positive integers n. Thus we have shown that the below is true for all positive integers n:
    1  + 6  + 11  + … + (5n−4)   =   n

    2
    (5n−3)       
Prove by induction. [By the nature of proof, it can't be given as just a single answer. Check out the steps to the problem if you want to see a version of the proof.]
Using mathematical induction, prove that the below is true for every positive integer.

1 + 1

1


1 + 1

2


1 + 1

3


1 + 1

n

  =  n+1
  • (Note: Make sure that you've watched the video lesson before working on these problems. The concept of mathematical induction can be rather difficult when you're first learning it, and it's important to understand the idea behind it and the steps involved. The method is carefully explained in the video, but it will be assumed in the below steps that you are already familiar with the process.) To prove something by induction, we first need a general statement Pn that makes sense for any positive integer n (notice that we haven't proven it is true yet, it just can't be total nonsense). The problem is pretty clearly set up in such a format, so we can just take the equation itself as our general statement:
    Pn:    
    1 + 1

    1


    1 + 1

    2


    1 + 1

    3


    1 + 1

    n

      =  n+1
  • Now that we have our general statement of Pn, we need to show that the base case of P1 is true. Base Case:
    P1:    
    1 + 1

    1

      =  1+1
    Just simplify the equation and verify that it is true:
  • (1 + [1/1])   =  1+1
    (1 + 1)   =  2
    2   =  2     Great, the statement P1 is clearly true, so the base case is complete.
  • Once the base case is complete, we move on to the inductive step. The inductive step begins with the inductive hypothesis, the assumption that Pk is true. Inductive Step: We assume our inductive hypothesis:
    Inductive Hypothesis- Pk:  
    1 + 1

    1


    1 + 1

    2


    1 + 1

    3


    1 + 1

    k

      =  k+1    is true.
    Using this inductive hypothesis, we now show that the next statement (Pk+1) must be true as well. That is, using our above assumption, we want to show the below is true:
    Pk+1:    
    1 + 1

    1


    1 + 1

    2


    1 + 1

    3


    1 + 1

    k


    1 + 1

    k+1

      =  (k+1)+1
  • Notice how we wrote Pk+1 so that it included an easily recognizable part from our inductive hypothesis of Pk. This allows us to apply our hypothesis.
    Pk+1:    

    1 + 1

    1


    1 + 1

    2


    1 + 1

    3


    1 + 1

    k



    1 + 1

    k+1

      =  (k+1)+1
    We can easily substitute the bracketed portion [ ] for what we know from our inductive hypothesis Pk. Plug in:

    k+1

    1 + 1

    k+1

      =  (k+1)+1
    Now we just expand and simplify both sides until it is clear that the equation is true:
  • ( k+1) (1 + [1/(k+1)] )  =  (k+1)+1
    (k+1)  + [(k+1)/(k+1)]   =  k+2
    (k+1)  + 1   =  k+2
    k+2   =  k+2     Excellent! Thus, from our inductive hypothesis that Pk is true, we have shown that Pk+1 must also be true.

    Therefore, by showing the base case and inductive step, the principle of mathematical induction says that the statement Pn must be true for all positive integers n. Thus we have shown that the below is true for all positive integers n:

    1 + 1

    1


    1 + 1

    2


    1 + 1

    3


    1 + 1

    n

      =  n+1       
Prove by induction. [By the nature of proof, it can't be given as just a single answer. Check out the steps to the problem if you want to see a version of the proof.]
Using mathematical induction, prove that the below is true for every positive integer.
n

i=1 
1

i(i+1)
  =   n

n+1
  • (Note1: Make sure that you've watched the video lesson before working on these problems. The concept of mathematical induction can be rather difficult when you're first learning it, and it's important to understand the idea behind it and the steps involved. The method is carefully explained in the video, but it will be assumed in the below steps that you are already familiar with the process. Note2: Furthermore, for this problem, it is necessary that you be familiar with sigma notation (Σ) for compactly writing summations. If you are not familiar with them, skim the lesson Introduction to Series where they are explained.) To prove something by induction, we first need a general statement Pn that makes sense for any positive integer n (notice that we haven't proven it is true yet, it just can't be total nonsense). The problem is pretty clearly set up in such a format, so we can just take the equation itself as our general statement:
    Pn:    n

    i=1 
    1

    i(i+1)
      =   n

    n+1
  • Now that we have our general statement of Pn, we need to show that the base case of P1 is true. Base Case:
    P1:     1

    i=1 
    1

    i(i+1)
      =   1

    1+1
    Just simplify the equation and verify that it is true:
  • i=11 [1/(i(i+1))]   =  [1/(1+1)]
    [1/(1(1+1))]   =  [1/2]
    [1/2]   =  [1/2]     Great, the statement P1 is clearly true, so the base case is complete.
  • Once the base case is complete, we move on to the inductive step. The inductive step begins with the inductive hypothesis, the assumption that Pk is true. Inductive Step: We assume our inductive hypothesis:
    Inductive Hypothesis- Pk:   k

    i=1 
    1

    i(i+1)
      =   k

    k+1
        is true.
    Using this inductive hypothesis, we now show that the next statement (Pk+1) must be true as well. That is, using our above assumption, we want to show the below is true:
    Pk+1:     k+1

    i=1 
    1

    i(i+1)
      =   k+1

    (k+1)+1
  • At this point, since both statements Pk and Pk+1 are written in sigma notation (Σ), it's hard to see how we can apply our hypothesis of Pk to Pk+1. To deal with this, let's expand both of them into versions using an ellipsis (…) to see the pattern:
    Pk:    k

    i=1 
    1

    i(i+1)
      =   k

    k+1
                                                                  

           ⇒     1

    1(1+1)
     +  1

    2(2+1)
     + … +  1

    k(k+1)
      =   k

    k+1



    Pk+1:    k+1

    i=1 
    1

    i(i+1)
      =   k+1

    (k+1)+1
                                                                  

           ⇒     1

    1(1+1)
     +  1

    2(2+1)
     + … +  1

    k(k+1)
     +  1

    (k+1)
    (k+1)+1
      =   k+1

    (k+1)+1
  • Notice that we wrote out the expansion of Pk+1 so that it included an easily recognizable part from our inductive hypothesis of Pk. This allows us to apply our hypothesis.
    Pk+1:  
    1

    1(1+1)
     +  1

    2(2+1)
     + … +  1

    k(k+1)

     +  1

    (k+1)
    (k+1)+1
      =   k+1

    (k+1)+1
    We can easily substitute the bracketed portion [ ] for what we know from our inductive hypothesis Pk. Plug in:

    k

    k+1

     +  1

    (k+1)
    (k+1)+1
      =   k+1

    (k+1)+1
  • Now we just expand and simplify both sides until it is clear that the equation is true:
  • [k/(k+1)]  + [1/((k+1)((k+1)+1))]   =  [(k+1)/((k+1)+1)]
    [k/(k+1)]  + [1/((k+1)(k+2))]   =  [(k+1)/(k+2)] Put the left-side fractions over a common denominator to combine them:
  • [((k+2))/((k+2))]·[k/(k+1)]  + [1/((k+1)(k+2))]   =  [(k+1)/(k+2)]
    [(k(k+2))/((k+1)(k+2))]  + [1/((k+1)(k+2))]   =  [(k+1)/(k+2)]
    [(k2+2k+1)/((k+1)(k+2))]   =  [(k+1)/(k+2)] Finally, notice that we can factor the left-side numerator to cancel out a common factor in the denominator:
  • [((k+1)(k+1))/((k+1)(k+2))]   =  [(k+1)/(k+2)]
    [(k+1)/(k+2)]   =  [(k+1)/(k+2)]     Excellent! Thus, from our inductive hypothesis that Pk is true, we have shown that Pk+1 must also be true.

    Therefore, by showing the base case and inductive step, the principle of mathematical induction says that the statement Pn must be true for all positive integers n. Thus we have shown that the below is true for all positive integers n:
    n

    i=1 
    1

    i(i+1)
      =   n

    n+1
          
Prove by induction. [By the nature of proof, it can't be given as just a single answer. Check out the steps to the problem if you want to see a version of the proof.]
Prove that, for any positive integer n, the number (n2+3n) is an even number.
  • (Note: Make sure that you've watched the video lesson before working on these problems. The concept of mathematical induction can be rather difficult when you're first learning it, and it's important to understand the idea behind it and the steps involved. The method is carefully explained in the video, but it will be assumed in the below steps that you are already familiar with the process.) To prove something by induction, we first need a general statement Pn that makes sense for any positive integer n (notice that we haven't proven it is true yet, it just can't be total nonsense). The problem isn't set up as an equation, but that's okay: our general statement can use everyday language as well.
    Pn:     The number (n2+3n) is an even number.
    Notice how the above is just a re-statement of what the problem is asking us to prove. It's our job to show that the above statement is true for every positive integer n, so now we turn to mathematical induction to prove it.
  • Now that we have our general statement of Pn, we need to show that the base case of P1 is true. Base Case:
    P1:     The number (12+3·1) is an even number.
    To verify that P1 is true, let's look at the number:
    (12+3·1)     =     1 + 3     =     4
    We know the number 4 is an even number, so the statement P1 is clearly true and the base case is complete.    
  • Once the base case is complete, we move on to the inductive step. The inductive step begins with the inductive hypothesis, the assumption that Pk is true. Inductive Step: We assume that our inductive hypothesis is true:
    Inductive Hypothesis- Pk:  The number (k2+3k) is an even number.
    Using this inductive hypothesis, we now show that the next statement (Pk+1) must be true as well. That is, using our above assumption, we want to show the below is true:
    Pk+1:     The number
    (k+1)2+3(k+1)
    is an even number.
    In other words, we must show that ((k+1)2+3(k+1)) is indeed an even number, thus verifying the statement Pk+1.
  • Unlike previous problems, we don't have a clear way to plug in and use the hypothesis of Pk. Previously, all the statements were two-sided equations, and one of the sides contained a part that looked like part of the hypothesis Pk, which allowed us to plug in. This is not the case for this problem, though. However, we can still follow that general idea. We need to somehow make some portion of Pk appear in the statement of Pk+1. We can do this by expanding the number Pk+1 is based on, then hopefully seeing the number Pk is based on contained in that. Try expanding Pk+1's number:

    (k+1)2+3(k+1)

    k2+2k +1   +  3k+3

    k2 + 5k + 4
    At this point, remember that the number from Pk was (k2+3k). Notice that we can pull that part to one "side" in the number from Pk+1:
    k2 + 5k + 4     =    
    k2+3k
     + 2k+4
  • At this point, we can finally use our inductive hypothesis. The hypothesis Pk guaranteed that (k2+3) is an even number. We have shown that the number from Pk+1 can be written as

    k2+3k
     + 2k + 4.
    Thus, this number is made from adding up three numbers:
    [k2+3k],              2k,              4
    Long ago in grade school, we learned that an even number added with an even number produces an even number. Thus, if we can show that each of the three numbers above are even, it must be that Pk+1 is even as well. From the inductive hypothesis Pk, we know (k2+3k) is even. Since multiplying any number by 2 creates an even number, we also know that 2k must be even. Finally, 4 is clearly even. Therefore, since each number involved is even, we have that the whole sum must be even as well. Thus, the number in Pk+1 is even, which verifies the statement we set out to show and completes the inductive step.    

    Therefore, by showing the base case and inductive step, the principle of mathematical induction says that the statement Pn must be true for all positive integers n. Thus we have shown that the below is true for all positive integers n:
    The number (n2+3n) is an even number.       
Prove by induction. [By the nature of proof, it can't be given as just a single answer. Check out the steps to the problem if you want to see a version of the proof.]
Prove that, for any positive integer n, the number (9n−2n) is divisible by 7.
  • (Note: Make sure that you've watched the video lesson before working on these problems. The concept of mathematical induction can be rather difficult when you're first learning it, and it's important to understand the idea behind it and the steps involved. The method is carefully explained in the video, but it will be assumed in the below steps that you are already familiar with the process.) To prove something by induction, we first need a general statement Pn that makes sense for any positive integer n (notice that we haven't proven it is true yet, it just can't be total nonsense). The problem isn't set up as an equation, but that's okay: our general statement can use everyday language as well.
    Pn:     The number (9n2n) is divisible by 7.
    Notice how the above is just a re-statement of what the problem is asking us to prove. It's our job to show that the above statement is true for every positive integer n, so now we turn to mathematical induction to prove it. [Make sure you know what the word divisible means. If you're not sure, look it up. It means that the number can be "evenly" divided by 7. In other words, we can divide out 7 and have no remainder.]
  • Now that we have our general statement of Pn, we need to show that the base case of P1 is true. Base Case:
    P1:     The number (9121) is divisible by 7.
    To verify that P1 is true, let's look at the number:
    (91−21)     =     9−2     =     7
    The number 7 is clearly divisible by 7, so the statement P1 is true and the base case is complete.    
  • Once the base case is complete, we move on to the inductive step. The inductive step begins with the inductive hypothesis, the assumption that Pk is true. Inductive Step: We assume that our inductive hypothesis is true:
    Inductive Hypothesis- Pk:  The number (9k2k) is divisible by 7.
    Using this inductive hypothesis, we now show that the next statement (Pk+1) must be true as well. That is, using our above assumption, we want to show the below is true:
    Pk+1:     The number ( 9k+12k+1 ) is divisible by 7.
    In other words, we must show that ( 9k+1 − 2k+1 ) is indeed divisible by 7, thus verifying the statement Pk+1.
  • Unlike past problems, we don't have a clear way that we can plug part of Pk in to the expression we have for Pk+1. However, we know that we somehow need to have the number from Pk appear in the number for Pk+1 so we can use our inductive hypothesis. With this in mind, look for a way to re-arrange the number for Pk+1 so that the number from Pk (that is, 9k−2k) will appear:
    Pk+1     ⇒     9k+1 − 2k+1
    First, we need to have 9k and 2k appear, so take the exponents down by one by "popping out" a multiplier of the appropriate base:
    9k+1 − 2k+1     =     9k·9 − 2k·2
    Next, we need to get the expression (9k−2k) to appear. We can do this by moving things around cleverly:
    9k·9 − 2k·2     =     9k ·2 + 9k ·7 − 2k ·2     =     9k·2 − 2k ·2 + 9k ·7
    Finally, we cause it to clearly appear by using the distributive property in reverse:
    9k·2 − 2k ·2 + 9k ·7     =     2·( 9k − 2k )  + 9k ·7
  • Now we have the number from Pk+1 expressed in such a way that we can use our inductive hypothesis from Pk. However, to formally prove this, we need a way to talk about what our inductive hypothesis is saying. Notice that the below
    Pk:  The number (9k2k) is divisible by 7,
    is equivalent to the statement that
    There exists some integer number a such that   9k−2k = 7 ·a.
    Why? If there is some integer a where 9k−2k = 7 ·a, then (9k−2k) must be divisible by 7 since (7·a) is clearly divisible by 7. And if no such number a existed that would work, then (9k−2k) could not be divisible by 7, so we know the a must exist (even if we don't know its value).
  • With this re-statement of Pk in terms of (7·a) in mind, let's look again at the number from Pk+1:
    Pk+1     ⇒     ( 9k+1 − 2k+1 )     =     2·( 9k − 2k )  + 9k ·7
    Swap out the ( 9k − 2k ) for (7·a):
    2·(7 ·a)  + 9k ·7
    We can now pull out a 7 from both terms to get
    7 · (2 ·a + 9k),
    which must be divisible by 7, because we clearly have a factor of 7 contained in the number. Thus we have shown that Pk+1 is divisible by 7, which completes the inductive step.    

    Therefore, by showing the base case and inductive step, the principle of mathematical induction says that the statement Pn must be true for all positive integers n. Thus we have shown that the below is true for all positive integers n:
    The number (9n2n) is divisible by 7.       
Prove by induction. [By the nature of proof, it can't be given as just a single answer. Check out the steps to the problem if you want to see a version of the proof.]
Below is a false theorem and its "proof" using mathematical induction. Looking at the theorem, it's clearly not true, so something must be wrong with the proof. What's the mistake in the proof?

Theorem: All horses are the same color. "Proof" (by mathematical induction): Let the general statement be
Pn:     A group of n horses are all the same color.
       Base Case: Consider the statement P1:
P1:     A group of 1 horse is all the same color.
This statement is trivially true: a single horse must be the same color as itself. Thus the base case is shown to be true.           Inductive Step: Begin by assuming the inductive hypothesis:
Inductive Hypothesis- Pk:  A group of k horses are all the same color.
Now we show that the statement Pk+1 must follow from Pk being true:
Pk+1 :     A group of (k+1) horses are all the same color.
To prove that this is true, consider the diagram below where we have lined all (k+1) horses up in some arbitrary order. Within this group of (k+1) horses, we can break it up into two sub-groups of k horses. Notice that by our hypothesis Pk, we have that each of these two sub-groups of horses must all be the same color, like in the below diagrams: Furthermore, looking at the diagrams, we see that there is some "middle horse" that appears in both sub-groups. Since this "middle horse" can not change colors, it must be that both sub-groups are the same color, and thus the entire group of (k+1) horses must all be the same color. Thus we have shown that all (k+1) horses must be the same color, so Pk+1 is true, completing the inductive step.     Therefore, by mathematical induction, we have that any group of n horses must all be the same color. Since there exists some finite number of horses in the world, they must all be the same color, so all horses are the same color.    
  • Begin by working through the proof: at first glance, everything seems to work fine. The base case is shown to be true, then the inductive step is shown to be true, so the general statement must be true. However, we know that the theorem is nonsense. If you've ever seen a group of horses, they clearly are not all necessarily the same color. Therefore there must be something wrong with the proof. Start looking through it very carefully, step-by-step.
  • To begin with, the general statement Pn is just fine. As long as the language and meaning is clear, there can be nothing inherently wrong with a statement: the job of the later steps is to prove that it is always true, but the statement we start with can be anything.
  • Next, consider the base case of P1:
    P1:     A group of 1 horse is all the same color.
    Nothing wrong here, either. A horse does have to be same color as itself, so a group with just one horse can only be one color-the color of the horse in the group.
  • Now we move on to the inductive step. The "proof" begins by putting all (k+1) horses from Pk+1 in some arbitrary order. There is nothing wrong with this: you can order any finite set, so we can put our horses in some order. Once the horses are ordered, the "proof" separates the group of (k+1) horses into two sub-groups of k horses, one where the last horse is excluded and one where the first horse is excluded. There's nothing wrong with this either: given a group, we can break it into sub-groups, and since it's ordered, we can easily choose what goes into each sub-group.
  • Finally, we make it to where the mistake occurs: the next part of the "proof" says that these two sub-groups overlap on some "middle horse". But do we have a guarantee that this "middle horse" actually exists? While the "proof" refers to the diagrams to show that the overlap is supposedly clear, we must remember that the diagrams have to represent all possible values for k. That is, k+1 ≥ 2. But what happens if we consider the case where k+1=2? That is, when there are just two horses?
  • If we consider the case of just two horses, we have a diagram like the one below: Next, we break it into two sub-groups, where each sub-group is all one color: We see that in the case of looking at only two horses, there is no overlapping "middle horse", so we cannot guarantee that the entire group must all be the same color.
  • This shows us the issue with the original "proof". While the original diagrams seemed to indicate the existence of an overlap, they failed to properly show all the cases. In the specific case of k+1=2, there cannot be an overlapping "middle horse", so we have no guarantee that both sub-groups must be the same color. Thus, we cannot show that the entire group of horses must be the same color. Because the inductive step is based on a flawed assumption, the proof does not hold.
  • The lesson we should take away from this problem is that we must be very careful in our assumptions when working on proofs. Even if something seems "obvious", we must carefully check that we can assume it before using it. When we take something for granted without carefully thinking about it, we introduce the possibility for serious error.
We cannot assume the automatic existence of an overlapping "middle horse". In the case of k+1=2 horses, there is no horse in both sub-groups, so there is no guarantee that the sub-groups have matching colors. [See the steps to the problem for a more detailed explanation along with some explanatory diagrams.]

*These practice questions are only helpful when you work on them offline on a piece of paper and then use the solution steps function to check your answer.

Answer

Mathematical Induction

Lecture Slides are screen-captured images of important points in the lecture. Students can download and print out these lecture slide images to do practice problems as well as take notes while watching the lecture.

  • Intro 0:00
  • Introduction 0:06
  • Belief Vs. Proof 1:22
  • A Metaphor for Induction 6:14
  • The Principle of Mathematical Induction 11:38
    • Base Case
    • Inductive Step
    • Inductive Hypothesis
  • A Remark on Statements 14:18
  • Using Mathematical Induction 16:58
  • Working Example 19:58
    • Finding Patterns
  • Example 1 30:17
  • Example 2 37:50
  • Example 3 42:38

Transcription: Mathematical Induction

Hi--welcome back to Educator.com.0000

Today, we are going to talk about mathematical induction.0002

The great thing about math is that we can trust it.0005

Regardless of the technology that math enables us to have in our daily lives (like the Internet), what we learn in math is entirely, beautifully true.0007

We can have certainty in this truth, because of proof.0016

In math, we start with a few simple ideas, and then we use proof to build a tower of logic.0019

Because we prove every theorem and method that we work with, we can trust the whole of mathematics.0025

Mathematics is built on this concept of truth--that we start with some things that we can just take for granted,0030

absolutely certainly--these axiomatic truths that we looked at in geometry, for example, previously--you have seen it in some courses.0037

We start with these basic axioms, and then we work up from there, using logic.0044

We can use proof to make sure that we can trust every single thing that we work with.0048

So far in this course, we have proved many things with a variety of logical arguments.0052

We have made very strong logical arguments that show, without a doubt, that something has to be true.0056

In this lesson, we are going to see a new form for proofs, mathematical induction.0061

This method can be used anywhere, from our current level of math all the way to very advanced mathematics.0066

It is this really flexible kind of proof that lets us show a lot of things; it is a very powerful way of proving things.0071

All right, let's talk about belief versus proof.0077

In math, it is important to recognize that there is a difference between believing that something is true and proving that something is true.0080

While we may strongly believe in something, that implies that there is still some level of reasonable doubt.0087

Believing in something doesn't mean that we can know it absolutely certainly; it just means that it is probably true.0092

But there is still this tiny crack of doubt that maybe it is not going to end up being true.0098

We can only be certain about something once we have proved it; we can only be certain that something is true once we have proof.0102

A proof is an irrefutable logical argument; it is something that very clearly shows (and there is no way to disagree with it)0110

that, given some something, we can show that it is always going to end up working out; it gives us total certainty.0116

This means that, when we notice a pattern in the way things work, we don't know for sure that it will always hold true.0124

We may believe that it will hold, but until we prove it, we cannot be absolutely certain.0129

So, we may believe in something, but we have to go and prove it before we can be absolutely certain.0134

Proof is this really integral part to how mathematics works.0140

As an example, consider the following: in the 1600s, a mathematician named Fermat noticed a pattern.0145

It seemed to him that all numbers of the form below were prime numbers.0150

It is pn, the nth Fermat number, 2 to the 2 to the n plus 1, where n is a natural number0154

(0, 1, 2...working our way up)...if we have p0, then that would be equal to 2 to the 2 to the 0 plus 1.0162

What is 220? Well, 2 to the 0...any number raised to the 0 is 1, so it is 2 to the 1.0168

So, we have 2 to the 2 to the 0 plus 1...2 to the 1, plus 1...that gets us 3; and indeed, 3 is a prime number.0174

Next, the next Fermat number would be 221 + 1; that gets us 5, and indeed, that is a prime number.0181

The next one would be 2 to the 2 to the 2, plus 1; that is going to come out to be 17; indeed, that is a prime number.0189

Now, we are starting to get to a place where we can't immediately see that they are prime.0194

But 223 + 1 is 257; and you can check--that does end up being prime.0197

The next one would be 2 to the 2 to the 4 plus 1, which comes out to be 65537;0203

and indeed, if you work at it, you can eventually check by hand that this does come out to be a prime number, as well.0208

So, Fermat could verify that this was true for the values of 0, 1, 2, 3, and 4--raising 2 to the 2 to the 0, to the 1, to the 2, to the 3, to the 4, plus 1.0214

Each one of these came out to be a prime number.0226

So, he could check by hand that you are able to make primes for these first five Fermat numbers (0, 1, 2, 3, 4).0229

He was able to show for sure that they do make primes.0238

However, the next Fermat number was too large for him to check, and he couldn't figure out a way to prove it prime.0242

The next one is 225, plus 1, which is equal to a huge 4 billion, 294 million, 967 thousand, 297--a big number.0246

That is going to be really hard to check by hand; and Fermat wasn't able to check by hand.0256

So, he couldn't figure out a clever way to prove for sure that it was prime without having to check by hand.0260

And it was too big for him to check by hand, so he couldn't show that it was prime.0265

Nonetheless, he had noticed a pattern; so he made a conjecture, that is, a hypothesis--an expectation,0268

of how things will work: that all numbers of the form 22n + 1 are prime.0274

But noticing a pattern does not necessarily prove it to be true.0281

This was a conjecture, but we didn't know for sure whether it was going to end up being a true conjecture0284

or a false conjecture--if it was going to end up being disproven.0288

It was not until the 1700s that we knew whether or not the conjecture was true.0292

Another mathematician, named Euler, showed that the sixth Fermat number, p5, could be factored.0296

So, 2 to the 2 to the 5, plus 1, which comes out to be 4 billion, 294 million, 967 thousand, 297, can be broken down0303

into the two numbers 641 times 6 million, 700 thousand, 417.0310

So, since that Fermat number can be broken down into two factors, that means that it is not a prime number.0316

Thus, Euler had shown that not all Fermat numbers are prime, because there is at least one of them that can be broken into factors.0323

Thus, he had proven the conjecture false; he had shown that there was a counterexample.0330

So, that conjecture that Fermat had originally thought, that 2 to the 2 to the n plus 1 was prime--that is not true.0334

We have proven it to not be true.0341

It is relatively easy to prove that something is not true; you only need a single counterexample--0344

one counterexample that cancels out and says, "No, here is a way that you can't have that work."0349

That proves that that does not work; but how can we prove that a pattern will hold forever,0353

that we have some sequence of things that is going to always end up being the case?0358

We can do this with mathematical induction.0363

There are other ways to do this; you can make logical arguments in other ways.0365

But a good way to do this is with mathematical induction; it often works well.0368

Before formally stating the principle of mathematical induction, let's look at a metaphor to help us understand how induction works.0372

Here is our metaphor: let's imagine that we have an infinitely long line of dominoes, and they are stood up on their ends, like in this picture here.0379

Domino, domino, domino, domino, domino...it is like if we were setting up a bunch of dominoes0387

to push it over and have (thump, thump, thump, thump, thump, thump, thump...) falling-over dominoes.0391

That is the image that we want to have in our mind.0395

OK, we could name the dominoes, based on their location in line.0397

The very first domino that would start on the line, on the very left side, we could call d1.0401

Here would be our d1, our first domino.0407

The next domino we could call d2; our second domino is d2, and so on.0409

Here would be d3 and d4, and it is going to just continue on in that pattern.0414

So, any domino...there exists some n that we can name any domino with.0418

We talk about some domino: there is some number that we can associate with it,0422

because we can just count up from the beginning and see what number we have to count to, to get to that domino.0425

That means that we can name any given domino.0429

All right, we have two guarantees: consider if we had two guarantees: the first guarantee0432

is that the first domino, d1, will definitely fall over.0440

We are going to be absolutely certain that d1 is going to fall over.0445

Our first domino, d1, is for sure going to fall over; we know that our very first domino in the line is going to fall over.0449

It is going to get pushed somehow; a gust of wind is going to happen...an earthquake...but something will certainly happen.0457

Who knows what it is, but we are guaranteed that it will fall over, for sure.0462

We know that our very first one is going to fall over; that is our first guarantee.0466

Our second guarantee is that, given any sequential pair, any pair of dominoes0470

(we could, for example, talk about some dk and dk + 1 for any positive integer k,0477

some dk in the line, and then the next one would be called dk + 1--0482

if we are at the k spot, the k + 1 would be the next spot), if dk falls,0486

if the domino on the left falls (dk is the domino on the left), then the next domino in line,0490

dk + 1, will also fall; this is our next guarantee.0501

So, if the domino on the left falls, then the next domino will fall, as well.0506

We are going to get falling from the next domino; if dk falls, dk + 1 must fall.0516

We have here that dk falls; and then, at the next one...we have dk falls;0522

if dk falls, dk + 1 must also fall.0527

If one domino falls, the next domino in line is always guaranteed to fall.0531

We have this guarantee that the dominoes do, indeed, always push each other over for any pair of dominoes that we end up looking at.0535

All right, we have these two things for sure: we have two guarantees and this infinite line of dominoes.0543

There is some line of dominoes, and the two guarantees: that the first domino, d1,0549

is definitely going to fall over; and that, if some domino, some dk falls over,0554

it will cause the next domino, dk + 1, to also fall over.0560

Given these two guarantees, we now know that absolutely all of the dominoes in our infinitely long line of dominoes will fall over.0564

We know for sure that all of them are going to fall over.0575

Why? Well, because, by the first guarantee, we know that d1 falls.0578

We know that the very first one in the line has to fall, because we are guaranteed that it is going to fall.0584

Then, by the second guarantee, if some domino falls, then we know that the next domino falls.0588

By our first guarantee, we know that d1 must fall.0594

But by the second guarantee, we know that d2 must fall, because d1 is the one before d2.0597

So, d2 must now fall, as well; then, by our second guarantee, once again,0602

since d2 just fell, we know that d3 must fall.0606

Then, by our second guarantee, again, we know that since d3 just fell, we know that d4 must fall.0609

And then, since d4 just fell, d5 must fall; d6 must fall; d7 must fall;0614

d8, d9, d10, forever and ever and ever.0618

Thus, all of the dominoes must fall over; we know that every single domino must fall over,0620

because we are guaranteed that the first domino is going to fall, and we know that every domino0626

after a domino that has fallen will fall as well.0630

So, since d1 falls, we know that d2 must fall; we know that d3 must fall;0633

and we can work our way out, going forever.0636

This is inductive thinking, step-by-step logic; this is the idea of mathematical induction,0638

that we have this first premise, that the definite thing is going to happen for the first thing;0644

and that, if something happens, we know that the next thing has to happen, as well.0648

We can start at d1, and from that induction idea, we can move forward forever, stepping along.0652

Mathematical induction is extremely similar; this idea of using it in math is very, very much the same thing as this line of dominoes.0658

It is just that, instead of dominoes, we will work with statements; and instead of "falls over," we will say "is true."0666

But other than that, the logic behind it is exactly the same.0673

And I know that that might seem like a crazy thing to say--that we can connect dominoes and statements,0676

and we can connect falling over with being true; but really, the idea behind it is the same.0680

And we will see why in just a second.0684

It is that we have this one thing that starts it, and then we have this other guarantee that says that it keeps going forever and ever and ever.0686

All right, now we are ready to look at the principle.0691

The principle of mathematical induction is: let p1, p2, p3, p4...0694

going on...pn...going on forever, be some infinitely long sequence of statements,0700

or just some sequence of statements, where n is a positive integer.0705

We are stepping forward, one statement at a time.0708

And we are guaranteed two things: if p1 is true, and if pk is true for a positive integer k,0711

then pk + 1 must also be true; then we know that the statement pn is true for all positive integers n.0721

Why is this the case? Well, it is very much the same thing as we just saw with the dominoes.0729

We have p1; it is definitely true--the very first one (we have p1, p2, p3,0732

p4, p5...going on forever; we effectively have this infinitely long line of sequences).0736

And we are guaranteed, by our very first thing, that p1 has to be true; p1 is true.0741

Then, our next guarantee is that, if something is true, the next thing in line must be true.0747

Our first guarantee was that p1 is true; that means that p2,0752

since it is the next thing in line, must also be true.0755

That means, by that same guarantee, that the next thing in line is true, that p3 must be true;0757

p4 must be true; p5 must be true; p6 must be true.0761

And it goes on forever and ever and ever, and that is why we now know that pn is going to be true for all positive integers n.0763

It is because, since the first thing in line was guaranteed by that first guarantee,0771

and the second thing is going to end up happening because of that second guarantee,0775

and then the third one will happen because of the second guarantee again,0778

and then the fourth thing will happen because of the second guarantee again...0782

we can keep using that step, step, step, step, step--that the second guarantee gives us.0784

We are able to step forever and ever and ever; we are able to have that infinitely many of these statements are going to end up being true.0788

All right, we often call the first step (that p1 is true) the base case,0794

because it is establishing the basis that we are working from.0801

It is the very first one in the line of true statements.0803

The second step is often called the inductive step, because it is the thing where the actual induction occurs--0806

that induction being "if 1, then 2," "if 2, then 3," so 1, then 2, then 3, then 4, then 5, then 6...0813

the fact that we can start at one place, and then step forever forward.0821

In the inductive step, the assumption, if pk is true (this part right here, the "if pk is true")0824

is called the inductive hypothesis, because it is the hypothesis that we use to show that pk + 1 will also be true.0831

We have to have this assumption that, if this thing happens, then this other thing will happen.0839

It is just like, with the dominoes, we say, "If some domino falls over, then this thing is going to happen in response."0844

But now, we are talking in terms of truth: "If this thing is true, then the next thing down the line must be true, as well."0849

All right, before we keep going, I want to have a quick remark on statements.0856

The principle of mathematical induction is based on statements.0859

We might be tempted to assume that any statement we see written out will automatically be true.0863

But that is not necessarily the case: just because you see something written out does not mean that you want to assume it will always, always be true.0868

Don't believe everything you read.0873

A statement, like in English, is just a string of words and/or symbols.0875

For example, the statement "Ice cream is made of hair" is most emphatically not true.0879

Ice cream is not made of hair; that is not true.0884

But it is still a statement, albeit a false statement.0887

Just because something is said does not mean that it is always going to end up being true.0891

Similarly, in math, the statement 3 + 5 + 7 = 10 is false; that is not true: 3 + 5 + 7 is not equal to 10.0895

But it is still a statement--just not a true statement.0903

3 + 5 + 7 is actually equal to 15, so we know that this one here is a false statement.0905

Most of the time, when we are working in math, we are always allowed to assume that the statements we are working with are true,0911

because they are given to us directly from the problem, and we are not told to question them.0916

We are saying, "Start with this thing and work with it."0919

Or we are working on the problem from the beginning (like a word problem), and we see, from the information that we are given,0922

that we can use logic to say, "Oh, this must definitely be the case; this must definitely be the case."0926

We are able to work with these things and be certain of their truth.0931

But just because something is said does not necessarily mean that it is always going to be true.0933

Everything that we have dealt with so far in math--we have been able to assume the truth of things,0937

because we know that we weren't being given lies.0941

But now, if we are just talking about statements in general, we have to evaluate their truth before we can trust them.0944

When we are working with mathematical induction, it is our job to not only set up the statements, pn,0950

but to also prove that the statements are going to be true statements.0956

We are not just going to get the statements and assume that they are true.0961

We have to get the statements, and then show for sure that they end up being true.0963

And occasionally, we might discover that the statements we have actually end up being false statements,0967

at which point we will have to go back to the beginning and figure out a way that we can state it truthfully;0971

or that will end up being the answer--the fact that it is actually not true.0974

But generally, we are going to end up showing that it is true.0977

Now, of course, if we want to show that n goes on infinitely, that all pn for any 1, 2, 3, 4, going on forever--0979

that they are all true--we can't prove each one of them by hand, because we can't prove an infinite number of things.0985

We are not going to be able to have an infinite amount of time to prove an infinite number of things.0990

So instead, we have to use some way to be able to show all of them at once.0995

We can either use some sort of clever logical argument, or we can use proof by mathematical induction,0999

where we can show that the first step will end up always being true,1003

and that, if you have some step, the next thing is going to end up being true, to work our way out infinitely,1006

like that line of dominoes, like we were just talking about a few moments ago.1011

All right, how do we use mathematical induction?1015

If we are going to use induction to prove that some statement, pn, is true for all n, we must prove two things:1017

first, the base case, that p1 is true--that our very first statement is a true statement;1022

and then, we have to do the inductive step: that if some pk is true,1029

the next one in line, pk + 1, must also be true.1033

So, that means, when we are working with proof by induction, that we have at least two separate steps.1036

We have two separate things that we have to deal with: proving the base case and proving the inductive step.1042

We have to show each one of these.1048

I am going to strongly recommend noting which one you are working on and making it so that you can keep the parts separate.1049

How you work on the base case normally isn't going to really help you deal with the inductive step.1055

How you work on the inductive step normally isn't really going to help you deal with the base case.1058

So, just write "base case" and prove your base case; then write "inductive step"; then prove your inductive step.1061

It will help you keep track of what you are doing; it will help keep it from being confusing.1066

And it will help other people who read your work in the future to understand what happened there.1069

In general, proving the base case almost always is going to be easier by far.1073

Normally, we just end up simplifying the statement--whatever this p1 statement ends up being;1078

and we verify that it is, indeed, a true statement--it is just making sure that, yes, this is true.1083

The tricky part normally ends up being dealing with the inductive step.1089

To prove the inductive step, we must first assume the inductive hypothesis, "pk is true."1093

We have to start by assuming that if pk is true...we have to say,1098

"OK, pk is true; now let's show that pk + 1 is also going to be true."1102

Once we make this assumption, we somehow have to work to prove that pk + 1 must then also be true.1108

Now, notice: we haven't actually proven pk to be true; we are just asking ourselves,1112

"If pk were true, would pk + 1 also be true?"1118

We are saying, "If we had this place that we could start from, would the next thing be true?"1122

It is like the dominoes: if this domino were to fall over, would the next one in line fall over?1125

That is all we need for mathematical induction: we don't have to prove that the one in the middle will fall over.1130

We just have to say, "Well, if it were to fall over, would the next one fall over, as well?"1133

All right, it helps a lot to somehow include part of the statement for pk when we are writing out pk + 1.1138

This is because we are almost inevitably going to end up using the inductive hypothesis.1146

We have to use this inductive hypothesis, "pk is true."1151

Otherwise, we wouldn't have needed to talk about pk being true, to show that pk + 1 is true.1154

So, we are going to end up using that inductive hypothesis, that pk is true.1159

So, we have to have some way of talking about it in our pk + 1 statement.1163

We can't use our hypothesis about pk unless it somehow appears in pk + 1.1167

That means, when we end up writing out the pk + 1 statement, that we have to figure out some way1175

to make pk, or some portion of pk, show up in some way,1178

so that we can apply that inductive hypothesis and use what we have assumed to be true.1182

It is important to have that end up showing up.1188

We will see how that occurs as we are actually working through problems and examples.1190

All right, all of this is going to make a lot more sense once we see it in action.1194

So, if it seems a little bit confusing right now, just follow it through; it is going to make much more sense as we actually work through what is going on.1197

All right, consider the following formula, which we proved in the lesson Arithmetic Sequences and Series:1203

we proved that adding the numbers 1 + 2 + 3 + ... up until we get to + n, all of the numbers consecutively,1209

from 1 up until some n that we choose, is equal to n times n + 1 divided by 2.1215

Previously, we proved this by a logical argument that involved equations and elimination.1222

Adding up two equations (if you watched that lesson), we were able to prove it through logical argument.1227

But we also could prove it through mathematical induction; let's see another way to prove this, through mathematical induction.1231

We can see that the above equation is effectively our statement, pn; we can turn this into our statement, pn, this right here.1238

How would this work? Well, our first statement, p1, would be if we went from 1 up until an n of 1 (p1, so 1 up until 1).1246

Well, that is just going to end up being 1; so 1 added to itself--is that, indeed, equal to 1 times 1 + 1 over 2?1254

That is the first statement: the first statement is that 1 is equal to 1 times 1 + 1 over 2.1261

Our next statement, at p2, would be 1 +...up until 2, so that is just going to be 1 + 2;1266

and that is going to be equal...the statement says that it is equal;1271

it will be up to us to verify that this actually ends up working out...to 2 times 2 + 1 over 2.1274

And then, the next one, p3, would be equal to 1 + 2 + 3...we get up to the third;1279

and it is saying...the statement is that that is, indeed, equal to 3 times 3 + 1 over 2.1284

And finally, the really interesting one here is pn, which is adding all the numbers from 1 up until n,1288

and that that is equal to n times n + 1 over 2.1294

So, this is our statement, pn--this way of writing it out here.1296

I didn't mean to cut through that 2.1301

To prove by induction that the statement pn = 1 added to all the numbers up until n is equal to n times n + 1 over 2--1303

to prove this as true for all positive integers, if we are going to use proof by induction, we have to prove two things.1310

We have to prove both the base case, p1, and the inductive step, that pk implies pk + 1.1314

The truth of some pk in the middle implies that pk + 1, the next one down the line, also has to be true.1322

Let's begin with the base case; the base case is normally the easier thing, by far.1328

Our p1 statement was that 1 is equal to 1 times 1 + 1 over 2.1331

Now, that is just a statement; once again, it is up to us to verify the truth of the statement.1337

So, we will write in the middle here this little equals sign with a question mark, because we don't actually know for sure that it is equal.1341

The statement said that 1 is equal to 1 times 1 + 1 over 2; but we don't know for sure that that is true.1347

The statement could be lying to us; it is up to us to figure out if this is, indeed, true;1353

are the left side and the right side actually equal to each other?1357

We work this out: we have 1; is it equal to...let's check: 1 times 1 + 1 over 2...1 compared to 1 times 2/2 (1 + 1 is 2), and then1361

that simplifies; the 2's cancel out, and we have 1 = 1; and indeed, that is true.1370

So, that means that our base case checks out; we have shown that the base case is definitely true.1374

Next, we move on to the inductive step: we write "inductive step," so that we see where we are.1380

The very first thing that we always do with the inductive step is write out our inductive hypothesis.1385

We say, "If pk is true..." so we assume that pk (which would be 1 + 2 + 3...1389

all the way up until we get to some k, is equal to k times k + 1 over 2) is true.1394

We are assuming that this thing is true: pk, which is the statement 1 + 2 + 3...up until + k = k + (k + 1)/2--1399

we can just take this as cold, hard fact; it is the assumption that if this domino were to fall,1408

now we just need to work on the next domino falling.1413

We don't have to prove for certain that this one is true; we are allowed to assume it, because it works in combination with the first guarantee.1415

All right, so we have this assumed as true.1421

With the inductive hypothesis in mind, we want to show1423

(our inductive hypothesis is right here; it is up to us to show) that pk + 1 must also be true.1426

We can write out pk + 1 as 1 + 2 + 3 +...up until...well, now we are going up to k + 1,1432

so up until + k + 1...and we can plug in k + 1 times k + 1 + 1, all over 2.1438

So, we see that this is what the statement would be.1444

However, we can't really see how pk shows up in here;1447

how does something in this portion right here show up?--because remember what we talked about before.1450

We are going to have to use our inductive hypothesis; that is what the inductive hypothesis is there for.1455

If we could prove this without an inductive hypothesis, why are we doing induction?1459

So, we have to use that inductive hypothesis somehow to be able to apply it here,1463

so that we can show that pk + 1 must be true.1467

We need to get some way to see some portion of pk appear.1472

We realize that we can rewrite what we have here: we could write pk + 1 as it is above, but we can't easily see pk in it.1476

So instead, we write it out as pk + 1 = 1 + 2 + 3 + ... + k + k + 1.1484

How can we do this? Well, we know that there had to be k in here, because it is all the numbers from 1 up until k + 1.1493

So, k has to be included in there, because it is the number before k + 1.1498

k + 1 minus 1 is k; so it has to be the number before it, so it has to be included somewhere in our ellipsis in our continuing pattern.1502

So, we can write it out; now that means that we have pk showing up right here.1510

1 + 2 + 3...up until k...look, that is this right here; so we can bring this to bear.1516

And we just simplified the right side a little bit; that just ends up being the same thing.1522

k + 1 times k + 1 + 1 is just k + 1 times k + 2, over 2; we just simplified the right side.1526

All right, we have our inductive hypothesis, that 1 + 2 + 3 + ... + k = k times k + 1 over 2.1531

We are assuming that that is true, and it is our job to show that 1 + 2 + 3 up until + k + 1 is equal to k + 1 times k + 2 over 2.1538

So, we want to verify the statement below; we want to show that this is not a question mark--1547

that it is, indeed, that the left side and the right side are equal to each other, for sure.1552

We want to verify this; we want to make that question mark be absolutely an equals sign.1556

What we notice is that we have pk here--our inductive hypothesis, pk.1561

We can substitute pk, our hypothesis; and what we have here is the same thing as what we have here.1567

So, we can plug in; we can swap out this stuff right here.1573

Now, we have gotten our hypothesis into the game.1576

We have been able to plug it in; so now, we can start using it--we can work things out.1579

We are almost absolutely, certainly, going to use that inductive hypothesis; otherwise, we wouldn't need to be doing induction.1582

We bring the hypothesis to bear somehow.1589

We can plug it in, generally; and from here, we just have to simplify the equation.1592

It is not really an equation, because we don't actually know if the two sides are equal to each other, so it is not technically an equation.1596

But we can write it as this idea of "are they equal to each other? Let's see if they are the same thing, on either side."1602

And then, we can just verify that, if it does come out to be clearly the same on both sides, then we will know that pk + 1 is true.1607

If we can get rid of that equals sign in our equation, if we can turn it into just an equals, then we will know that, indeed, pk + 1 is true.1616

And we will have shown that pk + 1 is true from pk, and we will have completed our inductive step.1627

OK, we just worked this out: what we had on the left side was k times k + 1 over 2, plus k + 1.1632

And then, on the right side, we had k + 1 times k + 2 over 2.1638

So, we expand: k times k + 1 gets us k2 + k; we can put this over a fraction, so that we can have them over common denominators.1641

So, we have 2k + 2 over 2.1648

We expand the right side, k + 1 times k + 2; that is going to be k times k, k2, plus 2k + 1k, so 3k, plus 1 times 2, 2.1650

So, we get k2 + 3k + 2, all over 2.1659

Now, we just combine these two fractions here, k2 + k over 2, plus 2k + 2 over 2.1662

It is going to be k2 + k + 2k + 2, all over 2, which simplifies to a nice k2 + 3k + 2, over 2,1667

which is equal to k2 + 3k + 2 over 2, which is, indeed, definitely always going to be true.1674

So, we have just shown that, yes, our inductive step does work; we have proved the inductive step to be true.1679

If we have pk true, then pk + 1 must be true, from our logic.1684

So, we have completed both steps: we have completed the base case (back a while), and we just completed the inductive step.1690

That means that we have completed both of the parts necessary for a proof by induction.1695

We have to prove both of those parts.1699

We now know that pn is true for all n; that is, for any positive integer, we have that 1 + 2 + 3, up until + n, is equal to n times n + 1 over 2.1701

And I like to complete my proofs with a little square, just to say, "We have completed the proof; it is done."1711

And there we are; that is an example of how proof by induction works.1718

All right, at this level in math, you will often be directly told what to prove.1721

You will be given some formula or some statement, and it is going to say, "Go prove this."1725

You will be given something, and it will be your job to prove it, by induction, since this is a thing about proof by induction.1729

But in most of the things, if you are asked to prove something else, it would also just be "here is something; go prove it," like when you were in geometry class.1734

However, sometimes you won't be given a formula.1740

Instead, it is going to be your job to discover a pattern inside of that sequence, inside of what you are looking at;1746

and then create some sort of hypothetical formula that will describe that pattern, and finally to prove that your formula will always work.1753

So, the proof itself can be challenging; that is what we are working on.1760

But sometimes the hardest part isn't the proof that the proof by induction works, but just finding the pattern and turning it into a formula.1763

Sometimes, that is the hardest part: being able to look at what you have, figure out what the pattern here is,1770

and how you can turn this into a formula, how you can turn this into a statement that you can then go on to prove.1775

If you need to do this, and you find it difficult, I recommend checking out "Tips for finding patterns,"1779

which is one of the parts in the lesson Introduction to Sequences.1784

There are a lot of connections between finding the general term of a sequence and finding a formula, because they are both based on a sequence.1787

The formula is based on some sequence of statements, effectively.1794

And a sequence is based on some sequence of numbers; so there is a lot of connection between them.1797

This "Tips for finding patterns" inside of Introduction to Sequences--you will end up seeing a lot of things there.1801

A lot of the ideas there, you can apply to looking at formulas, so that is a really good thing to check out,1807

if you are having to work on that and you find it difficult.1811

All right, we are ready for some examples.1814

Prove that the below...1816

Oh, by the way, if you just skipped directly to the examples, you definitely, definitely, definitely, in this case,1817

want to go back to the working example first; so if you just skipped to this part directly, check out the working example first,1821

because it will explain what is going on here, as opposed to being confusing and just not having any meaning.1826

The working example will explain everything that is going on.1831

If you just watched the whole lesson, I'm sorry; I didn't mean to...I'm sorry about that.1833

Anyway, let's go on.1836

Prove that the below is true for any positive integer n.1837

We have 12 + 22 + 32 + ... + n2 = n times n + 1 over 2n + 1.1840

This is effectively our statement pn...not effectively; this is our statement pn.1849

Adding all of the squares, 12 + 22...up until n2, is equal to n times (n + 1) times (2n + 1), all divided by 6.1854

Our first thing to do is to show that the base case ends up being true.1862

The base case would be what it would be if we plugged in a 1 for n, if it was just the first statement.1867

What would that end up looking like? That is going to be...proving that would be equivalent to showing1871

that these two sides are the same, that 12 is equivalent to 1 (plugging in 1 for our n),1876

1 + 1, plugging in 1 for our n...2 times...plugging in 1 for our n...plus 1...all over 6.1881

Does this end up working out to be the same?1887

12 is 1; what is on our right side? 1 times...1 + 1 is 2; 2 times 1, plus 1, would end up being 3, over 6.1889

Is 1, indeed, equal to 1 times 2 times 3...is 6...over 6?1897

And yes, indeed, that would be 1 = 1; so we just showed that our base case ends up being true.1902

The next thing that we want to work out is the inductive step.1908

What would our inductive step be? Well, always the first thing that happens in the inductive step is that we write out what our hypothesis is.1911

What is the thing we are assuming? The hypothesis: we are assuming that pk,1918

which would be 12 + 22...up until we get to some k21923

(any positive integer k) is equal to k...we plug in k for n...k + 1, times 2k + 1, all over 6.1928

So, we assume that this is true; this is our assumption.1938

We can use this later; we can plug it in.1941

All right, we have our general thing here, pn, 12 + 22 + 32...1944

up until n2, is equal to n times n + 1 times 2n + 1.1948

And our inductive hypothesis is just saying, "What if we looked at some k, and we assumed that at k, it was true?"1951

So now, we want to show--it is our job to now show--that pk + 1 is true.1957

It is our job to show that pk + 1 ends up being true.1963

Showing that pk + 1 is true is going to end up being equivalent to showing that 12 + 22 + ...1967

up until we get to (k + 1)2...now, here is the part...we don't want to put in (k + 1)2,1978

because we want to somehow have our pk show up.1984

We are going to have to apply our hypothesis in there somewhere.1987

So, we want to have it show up.1991

We realize that up in 12 + 22 ... + (k + 1)2, well, what would be right before that?1992

We go back, and instead of using (k + 1)2 as the last thing, it would be easier to see in the pattern1998

what is really there, to make it easier, to substitute this: + k2 + (k + 1)2.2003

I will break this onto a different line, because now we are starting to get a little cramped.2009

We want to show (we don't know for certain; it is up to us to verify) that that would be...2011

swap in k + 1 now for n; so k + 1 times...k + 1 in here would be k + 2, times...k + 1 in here...2 times...k + 1 + 1, all divided by 6.2016

So, at this point, we say, "We have 12 + 22 + ... up until k2,2032

so we can swap that in for what is here at pk, which is this thing right here"--we can now swap that in.2037

Now, we are going to move over here, so we have a little bit more room.2045

k times k + 1 times 2k + 1, all over 6: this is our inductive hypothesis, which we assumed is true, so we can use it as we want;2049

plus...what is the thing that we still have left over?2061

We still have (k + 1)2 left over; we didn't substitute out for that; so, plus k + 1 squared.2062

And it is now our job to show that that is, indeed, equal to what was on the other side, which is k + 1 times k + 2 times 2k + 1 + 1.2069

I will simplify that a little bit: that will be 2k + 2 + 1; so that would be 2k + 3, all over 6.2079

OK, at this point, to show that they end up being the same on either side of that...2086

"maybe-it-is," to show that each side is the same, that the sides are equivalent,2091

we can just end up simplifying each of the sides, working with each side on their own.2095

We work with expanding this part over here; k times...k + 1 times 2k + 1...k times 2k gets us 2k2;2099

k times 1 is k, plus 1 times 2k, so + 3k; 1 times 1...plus 1; all over 6; plus...2107

let's multiply this part by 6/6, because we know that we will want to put them together2115

into a single fraction, so that we can compare the two things;2120

(k + 1)2 is (k + 1) times (k + 1); it becomes k2 + 2k + 1.2122

And is that, indeed, equal to...let's expand the right side; expand the far right first.2129

k + 1 times k + 2 times 2k + 3...k times 2k gets us 2k2; k times 3 is 3k; 2 times 2k is 4k;2133

so 3k + 4k is 7k; 2 times 3 is + 6; all divided by 6.2141

So, we can keep expanding over here; k times 2k2 is 2k3, plus 3k2, plus k, all over 6.2149

Plus...6k2 + 12k + 6, all over 6; and is that equal to (k + 1) times (2k2 + 7k + 6)?2160

OK, how is this one going? I am going to do this one partially in my head.2174

If you get lost here, just write it out, and you will see how it worked.2178

k times 2k2 is going to come out to be 2k3.2181

k times 7k is 7k2; plus...1 times 2k2...7k2 + 2k2 is 9k2;2184

k times 6 is 6k; 1 times 7k is 7k; 7k + 6k is 13k; and 1 times 6 is +6, all over 6.2191

And finally, if we combine our two fractions on the left, then 2k3...2201

everything will be divided by 6 over here...2k3 plus nothing on our other fraction,2206

so that is just that...3k2 + 6k2...we get 9k2;2211

k + 12k + 13k...there are no constants on our left fraction, plus the one on our right fraction, so + 6.2216

And is that, indeed, equal to 2k3 + 9k2?2222

We see that that is, indeed, the exact same thing; thus, our inductive step right here2226

(not our inductive hypothesis, but our inductive step) just checked out.2231

So, we have now shown that the base case checks out; the inductive hypothesis checks out.2234

So, combined, they show that this here is always true.2238

We have just shown that combining these two things (the base case, p1, being true,2245

and if pk is true--our inductive hypothesis--then pk + 1 is true, which we just showed here)--2249

we combined those two things, so now we have shown that pn is true for all things:2255

that 12 + 22 + 32...up until + n2 is equal to n(n + 1)(2n + 1), all divided by 6.2258

We have completed our proof by induction.2265

The second example: Show that, for n = 1, 2, 3...forever, that n3 + 2n is divisible by 3.2269

So really, this is our statement, pn: pn is "n3 + 2n is divisible by 3."2279

The first thing that we always have to do: we have to start by showing the base case.2285

Our base case first: the base case is showing that the p1 statement would be true.2289

Verifying p1 is the same thing as verifying that 13 + 2(1) is divisible by 3.2295

13 + 2(1) is 1 + 2, or 3; that is divisible by 3--that checks out, so our base case just checked out; great.2309

Next, we want to work on the inductive step.2318

Always, the first thing we do in our inductive step is to write what our hypothesis is.2324

What is the assumption that we can work from?2328

Our hypothesis is going to be that pk ends up being true.2331

What is pk? pk would be if we plugged in k for our n here: k3 + 2k is divisible by 3.2336

This is our starting assumption: that k3 + 2k is divisible by 3.2349

At this point, we now want to show that pk + 1 is true.2353

Showing that pk + 1 is true is going to be the same thing as showing2364

that k + 1 (plugging in k + 1 for n now), cubed, plus 2(k + 1) for n now, is divisible by 3.2367

So now, we just need to show...if this is divisible by 3, then we will have proven our inductive step, as well.2378

So, we will have shown the whole thing.2384

From here on, let's just take a close look at (k + 1)3 + 2(k + 1).2385

Hopefully, we will have enough room to work this out.2397

(k + 1)3...well, we can write that as (k + 1)(k + 1)2.2399

What is (k + 1)2? That is k2 + 2k + 1.2402

Plus...2 times (k + 1)...that is 2k + 2.2407

k + 1 times k2 + 2k + 1...well, k times k2 is going to be k3;2411

k times 2k is 2k2, plus 1 times k2, so + 3k2;2416

k times 1...+ 1k; plus 1 times 2k is 2k, so + 3k total; plus 1 times 1 is 1;2421

also, in the next lesson, when we talk about the binomial theorem, we will recognize, "Oh, yes, that is definitely how it has to expand."2428

Plus 2k + 2...OK, so at this point, we can realize, "What was our hypothesis? Our hypothesis was that k3 + 2k is definitely divisible by 3."2433

Look: here is k3; here is 2k; let's bring them together.2444

Now, we have k3 + 2k; and we will put everything else on the other side.2447

So, 3k2 + 3k...and we have a 1 here and a 2 here, so that combines to + 3.2454

Now, we can look at each part of this independently.2461

k3 + 2k is a thing; plus...and over here, we have a 3 here, a 3 here, and a 3 here;2463

so we can pull a 3 out; 3 comes out of k2 + k + 1.2470

Now, at this point, we realize--look, by our inductive hypothesis, we knew that this is divisible by 3.2476

We know that that is divisible by 3; furthermore, we have 3 times k2 + k + 1;2484

well, anything that we end up multiplying by 3 on it...well, that already has a factor of 3 multiplied in.2490

So, it must be divisible by 3; so that means both parts that we are adding together are divisible by 3.2496

If both parts that we add together are divisible by 3, then it must be that the entire thing is divisible by 3.2504

If something over here is divisible by 3, and something over here is divisible by 3, well, that means that I can divide this thing by 3;2510

I can divide this thing by 3; so even when we put them together, I can still divide the thing by 3.2514

Since both parts are divisible by 3, that means that (k + 1)3 + 2(k + 1),2518

which we just showed, has to be divisible by 3.2524

So, we have just shown that, if pk is true, then pk + 1 is true.2526

So, we have now shown the inductive step; since we have shown that p1 is true,2530

and if something in the middle is true, then the next thing is true;2535

then p1 being true implies that p2 must be true, by our inductive step,2538

which implies that p3 must be true, by our inductive step; p4, p5, p6, p7...2541

So, we know that, forever and always, n3 + 2n is divisible by 3; we have completed our proof by induction.2545

The next proof, the last example: Come up with a formula that gives the value of the nth partial sum2554

of the sequence below: 1, 3, 5, 7, 9... then prove that your formula always works.2559

The first few partial sums of the sequence are below.2565

Our first partial sum would be just adding 1 together, so that is 1.2568

Our next partial sum would be adding just 3 onto what we had before, so that would be 1 + 3.2572

The next thing would be 5, so 1 + 3 + 5.2577

The next thing would be 1 + 3 + 5 + 7; the next thing would be 9; let's write that out, as well: 1 + 3 + 5 + 7 + 9.2579

If we were to keep going with this pattern, what would be next?2588

Well, that would be 11 next; we are adding by 2 each time, so 1 + 3 + 5 + 7 + 9 + 11.2590

Let's see if we can figure out what the pattern going on here is.2599

1 on its own--well, that is just 1.2601

1 + 3 is 4; 1 + 3 + 5 is 9; add on another 7: 7 + 9 is 16; add on another 9; that is 25; add on another 11; that is 36.2603

We have an idea of what the formula is: it looks like the nth partial sum is going to be equal to n2; great.2618

What we have here is 1 + 3 + 5 + ... + something...whatever we end on...is equal to n2.2629

We need to figure out what we end on; how do we call out each member of this sequence?2644

Well, we can remember what we did in arithmetic sequences.2648

We see that we have 1 as our starting place; we add by 2 each time.2651

So, we could realize that the nth term here, an, is equal to 2n - 1.2655

We verify this: n at 1 gets us 1; n at 2 would get us 3; n at 3 would get us 5; so this works out.2664

We see that what we are going up to is 2n - 1.2670

So, our statement, the pn statement, is that 1 + 3 + 5, working up until 2n - 1, is equal to n2, for any n.2674

So, that is what we have figured out that our formula is for how we are getting these partial sums.2688

As we add up more and more terms of this sequence, we have now figured out our formula.2694

We have figured out how this pattern of adding things up comes to be.2698

We see that we have n2 coming out, if we do this each time.2705

On the first term, n = 1, we have 1; at n = 2, we have 4; n = 3...2709

We see that, each time, it is just squaring that number.2714

We also have to figure out what the sequence of the things looks like, because we have to be able to figure out what we end on.2717

We have to be able to say what the last thing is, so that we can actually work with having a left side and a right side to our statement's equation.2721

At this point, we are now ready to prove this.2728

All right, so now it is just up to us to prove that this is, indeed, true: that our statement pn is true for any value of n:2731

that 1 + 3 + 5...up until + 2n - 1 is equal to n2, no matter what n we put in, as long as n is a positive integer.2739

So, the first thing to prove: always prove the base case first, because it is almost always easier.2746

It also helps you understand how the thing comes together.2750

So, the base case: showing that p1 is true is going to be the same thing as showing that 1,2752

added up until...well, we just add it up to 1, so that is just 1 on the left side--is that equal to 12?2757

Yes, 1 is equal to 1; that was pretty easy.2764

So, there is our base case, finished.2766

Next, we do the inductive step; now we want to show that the inductive step is going to end up being true.2768

The first thing that we always do: we assume our hypothesis first; what is our hypothesis going to be?2774

Our hypothesis will be that pk is true.2780

What is the statement pk? Well, that would be 1 + 3 + ... up until we get to +...plug in k for n...2k - 1 = k2.2783

So, we are assuming that 1 + 3 + ... + 2k - 1 is equal to k2.2794

OK, with that assumption that this thing is true, we need now to show that k + 1 is going to be true, as well.2800

So now, we want to show that k + 1 is true.2805

Showing that k + 1 is true is going to be equivalent to showing that 1 + 3 + ... + 2k - 1...2811

I'm sorry, it is not 2k - 1; we are going to swap out k + 1 for n here, so 2 times (k + 1) - 1, equals k + 1,2821

swapping out that n here, as well, for k + 1, squared.2830

Now, remember: we want to have our hypothesis show up somewhere.2834

We have to get our hypothesis to show up somewhere.2838

So, we realize that that is really this part up here.2840

So, we can rewrite this as 1 + 3 + ... until we get to back a step of two...so that would be 2k - 1;2843

forward a step by 2...we see that that would be 2k + 1; if we work out this value here,2855

we end up seeing that it is the same thing here; 2k + 2 - 1 is just 2k + 1.2862

And we want to show that that is equal to (k + 1)2.2866

OK, we bring this up here; and on the way, we are going to say, "Right here, from here to here, we assumed up here that this was true."2870

That means that what we have in the thing we are trying to show, pk + 1, that part of it, is going to just be equal to k2, right here.2885

So, we can swap out k2 here; so now we have k2 plus what still remains; that is 2k + 1.2894

And we want to show that this is true, so it is a question mark here.2902

We don't know for sure that it is true yet; it is up to us to show that it ends up being true.2904

Plus what remained there, 2k + 1: is that equal to (k + 1)2?2908

Well, let's just simplify it: we have k2; we expand this; well, k2 + (2k + 1)...that is just 2k + 1;2916

is that equal to...what do we get when we expand (k + 1)2?2923

Well, that is k2 + 2k + 1; we end up seeing that that is indeed true.2926

That is always going to end up being true, so we have shown that our inductive step is true.2933

With this hypothesis in mind, we know that the next thing down the line...2938

with pk being true, we know that pk + 1 must be true.2941

Because we know that our base case is true (p1 is true), and we know that if something is true,2945

then the next thing has to be true; then since p1 is true, the next thing must be true.2949

p2 is true; p3 is true; p4 is true; p5 is true; p6 is true.2953

And the fireworks keep going forever and ever; we see that everything is always true.2957

We have that this statement ends up being true for absolutely every single n that we would plug into it.2961

We have completed the proof; our proof is done--pretty cool.2968

The only really challenging part there--that wasn't that difficult of a proof by induction, compared to the ones that we did previously--2972

the challenging part there was being able to figure out what that formula was in the first place.2977

So, once again, if you have difficulty with that, I recommend checking out the Arithmetic Sequences and Series.2981

There is that section, "Tips on finding patterns," that will really help you see how to find patterns; there is a lot of good stuff in there.2985

All right, we will see you at Educator.com later--goodbye!2991