For more information, please see full course syllabus of Pre Calculus
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
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, foreverit 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 neverending line of dominoes. If we have two guarantees,
 The first domino will fall over;
 If a domino falls over, it will cause the next domino to fall over as well;
 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 P_{1}, P_{2}, P_{3}, P_{4}, ..., P_{n}, ... be some sequence of statements where n is a positive integer. If
 P_{1} is true, and
 If P_{k} is true for a positive integer k, then P_{k+1} must also be true,
 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 P_{k} is true" is called the inductive hypothesis, because we must use this hypothesis to show P_{k+1} will also be true.
 It helps a lot to somehow include part of the statement for P_{k} when we are writing out P_{k+1}. This is because we will almost inevitably wind up using our inductive hypothesis (P_{k} is true) to show that P_{k+1} is also true. But we can't use our hypothesis about P_{k} unless it somehow appears in P_{k+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

 A statement is just a string of words and/or symbols. In the case of the above statement, P_{n} is a statement that varies depending on the specific value used for n.
 To find out what P_{1}, P_{7}, P_{k}, and P_{k+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 P_{1}, we have n=1, so substitute for every value of n in the general statement:
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 haveP_{1}: Buying 1 loaves of bread costs $(2.20 ·1). P_{1}: Buying 1 loaf of bread costs $2.20.  To find the other statements, we just plug in the appropriate value for n:
P_{7}: Buying 7 loaves of bread costs $(2.20 ·7). P_{k}: Buying k loaves of bread costs $(2.20 ·k).
For each of these, the grammar is correct (we almost always treat variables as if they indicate the plural). For P_{7}, 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 P_{k+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.P_{k+1}: Buying (k+1) loaves of bread costs $(2.20 ·(k+1)). P_{k+1}: Buying (k+1) loaves of bread costs $(2.20·k + 2.20).

 A statement is just a string of words and/or symbols. In the case of the above statement, P_{n} is a statement that varies depending on the specific value used for n.
 To find out what P_{1}, P_{7}, P_{k}, and P_{k+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 P_{1}, we have n=1, so substitute for every value of n in the general statement:
The above is fine: although we could simplify the expression (1^{3}−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.P_{1}: The number (1^{3}−1+2) is divisible by 2.  To find the other statements, we just plug in the appropriate value for n:
P_{7}: The number (7^{3}−7+2) is divisible by 2. P_{k}: The number (k^{3}−k+2) is divisible by 2. P_{k+1}: The number ((k+1)^{3}−(k+1)+2) is divisible by 2.
[Once again, like for the statement P_{1}, the above statement P_{k+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.]

 A statement is just a string of words and/or symbols. In the case of the above statement, P_{n} is a statement that varies depending on the specific value used for n.
 To find out what P_{1}, P_{7}, P_{k}, and P_{k+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 P_{1}, 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 1^{5} + 2^{5} + 3^{5} + … + n^{5} means that we start off with 1^{5}, then we add the next number up raised to the fifth (2^{5}), then the next number up raised to the fifth (3^{5}), and we continue to repeat this process until we reach n and add n^{5}. However, for P_{1}, we have n=1. Thus the summation process ends as soon as it starts. The very first value of 1^{5} means we have already reached n^{5}, so we only have one term on the left for P_{1}:P_{1}: 1^{5} = 1^{2}·(2·1^{2}+2·1−1)·(1+1)^{2} 12  To find the other statements, we just plug in the appropriate value for n:
P_{7}: 1^{5} + 2^{5} + 3^{5} + … + 7^{5} = 7^{2}·(2·7^{2}+2·7−1)·(7+1)^{2} 12P_{k}: 1^{5} + 2^{5} + 3^{5} + … + k^{5} = k^{2}·(2k^{2}+2k−1)·(k+1)^{2} 12P_{k+1}: 1^{5} + 2^{5} + 3^{5} + … + (k+1)^{5} = (k+1)^{2}·(2(k+1)^{2}+2(k+1)−1)·((k+1)+1)^{2} 12
[Remarks: The above statement P_{k+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 P_{k+1} to somehow be connected to P_{k}. We could do this by rewriting the leftside sum to show the connection:
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 P_{k} is connected to P_{k+1}, which would allow us to plug in from the statement of P_{k}. However, we weren't asked to prove this by induction, so we're fine to leave it in the original form for now.]1^{5} + 2^{5} + 3^{5} + … + (k+1)^{5} = 1^{5} + 2^{5} + 3^{5} + … + k^{5} + (k+1)^{5}

 (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 P_{n} 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:
P_{n}: 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 P_{1} is true. First, let us see what P_{1} is: plugging in n=1 into our general statement, we get
[If you're confused by why the leftside is simply `2', remember that the leftside 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'.]P_{1}: 2 = 1·(1+1)  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:
 P_{1}: 2 = 1·(1+1)
P_{1}: 2 = 1·(2)
P_{1}: 2 = 2  Great, the statement P_{1} 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 P_{k} is true. Inductive Step: We assume our inductive hypothesis:
Using this inductive hypothesis, we now show that the next statement (P_{k+1}) must be true as well. That is, using our above assumption, we want to show the below is true:Inductive HypothesisP_{k}: 2 + 4 + 6 + … + 2k = k(k+1) is true. P_{k+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 P_{k} to somehow prove that P_{k+1} will be true as well. Thus, we need to make some portion of P_{k} appear in P_{k+1} so that we can apply our hypothesis. Notice that we can rewrite the above formulation of P_{k+1} to make it easier to see P_{k} in it:
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 ofP_{k+1}: 2 + 4 + 6 + … + 2k + 2(k+1) = (k+1) · ⎛
⎝(k+1)+1 ⎞
⎠
Let us plug in. We haveP_{k}: 2 + 4 + 6 + … + 2k = k(k+1).
and we can clearly replace the bracketed [ ] part with what we know from our inductive hypothesis:P_{k+1}: ⎡
⎣2 + 4 + 6 + … + 2k ⎤
⎦+ 2(k+1) = (k+1) · ⎛
⎝(k+1)+1 ⎞
⎠, ⎡
⎣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)
k^{2}+k + 2k+2 = (k+1) ·(k+2)
k^{2} + 3k + 2 = k^{+} 3k + 2  Excellent! Thus, from our inductive hypothesis that P_{k} is true, we have shown that P_{k+1} must also be true.
Therefore, by showing the base case and inductive step, the principle of mathematical induction says that the statement P_{n} 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)

 (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 P_{n} 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:
P_{n}: 1 + 6 + 11 + … + (5n−4) = n 2(5n−3)  Now that we have our general statement of P_{n}, we need to show that the base case of P_{1} is true. Base Case:
Just simplify the equation and verify that it is true.P_{1}: 1 = 1 2·(5·1 −3)  1 = [1/2] ·(5·1 −3)
1 = [1/2] ·(2)
1 = 1 Great, the statement P_{1} 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 P_{k} is true. Inductive Step: We assume our inductive hypothesis:
Using this inductive hypothesis, we now show that the next statement (P_{k+1}) must be true as well. That is, using our above assumption, we want to show the below is true:Inductive HypothesisP_{k}: 1 + 6 + 11 + … + (5k−4) = k 2(5k−3) is true. P_{k+1}: 1 + 6 + 11 + … + (5k−4) + ⎛
⎝5(k+1)−4 ⎞
⎠= k+1 2⎛
⎝5(k+1)−3 ⎞
⎠  Notice how we wrote P_{k+1} so that it included an easily recognizable part from our inductive hypothesis of P_{k}. This allows us to apply our hypothesis.
We can easily substitute the bracketed portion [ ] for what we know from our inductive hypothesis P_{k}. Plug in:P_{k+1}: ⎡
⎣1 + 6 + 11 + … + (5k−4) ⎤
⎦+ ⎛
⎝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:⎡
⎣k 2(5k−3) ⎤
⎦+ ⎛
⎝5(k+1)−4 ⎞
⎠= k+1 2⎛
⎝5(k+1)−3 ⎞
⎠  [(5k^{2}−3k)/2] + (5k + 5 −4) = [(k+1)/2] (5k+5−3)
[(5k^{2}−3k)/2] + (5k+1) = [(k+1)/2] (5k+2)
[(5k^{2}−3k)/2] + [(10k+2)/2] = [((k+1))/2] ·[((5k+2))/1]
[(5k^{2} + 7k + 2)/2] = [(5k^{2}+7k+2)/2] Excellent! Thus, from our inductive hypothesis that P_{k} is true, we have shown that P_{k+1} must also be true.
Therefore, by showing the base case and inductive step, the principle of mathematical induction says that the statement P_{n} 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)

 (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 P_{n} 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:
P_{n}: ⎛
⎝1 + 1 1⎞
⎠⎛
⎝1 + 1 2⎞
⎠⎛
⎝1 + 1 3⎞
⎠… ⎛
⎝1 + 1 n⎞
⎠= n+1  Now that we have our general statement of P_{n}, we need to show that the base case of P_{1} is true. Base Case:
Just simplify the equation and verify that it is true:P_{1}: ⎛
⎝1 + 1 1⎞
⎠= 1+1  (1 + [1/1]) = 1+1
(1 + 1) = 2
2 = 2 Great, the statement P_{1} 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 P_{k} is true. Inductive Step: We assume our inductive hypothesis:
Using this inductive hypothesis, we now show that the next statement (P_{k+1}) must be true as well. That is, using our above assumption, we want to show the below is true:Inductive HypothesisP_{k}: ⎛
⎝1 + 1 1⎞
⎠⎛
⎝1 + 1 2⎞
⎠⎛
⎝1 + 1 3⎞
⎠… ⎛
⎝1 + 1 k⎞
⎠= k+1 is true. P_{k+1}: ⎛
⎝1 + 1 1⎞
⎠⎛
⎝1 + 1 2⎞
⎠⎛
⎝1 + 1 3⎞
⎠… ⎛
⎝1 + 1 k⎞
⎠⎛
⎝1 + 1 k+1⎞
⎠= (k+1)+1  Notice how we wrote P_{k+1} so that it included an easily recognizable part from our inductive hypothesis of P_{k}. This allows us to apply our hypothesis.
We can easily substitute the bracketed portion [ ] for what we know from our inductive hypothesis P_{k}. Plug in:P_{k+1}: ⎡
⎣⎛
⎝1 + 1 1⎞
⎠⎛
⎝1 + 1 2⎞
⎠⎛
⎝1 + 1 3⎞
⎠… ⎛
⎝1 + 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+1 ⎤
⎦⎛
⎝1 + 1 k+1⎞
⎠= (k+1)+1  ( 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 P_{k} is true, we have shown that P_{k+1} must also be true.
Therefore, by showing the base case and inductive step, the principle of mathematical induction says that the statement P_{n} 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

 (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 P_{n} 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:
P_{n}: n
∑
i=11 i(i+1)= n n+1  Now that we have our general statement of P_{n}, we need to show that the base case of P_{1} is true. Base Case:
Just simplify the equation and verify that it is true:P_{1}: 1
∑
i=11 i(i+1)= 1 1+1  ∑_{i=1}^{1} [1/(i(i+1))] = [1/(1+1)]
[1/(1(1+1))] = [1/2]
[1/2] = [1/2] Great, the statement P_{1} 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 P_{k} is true. Inductive Step: We assume our inductive hypothesis:
Using this inductive hypothesis, we now show that the next statement (P_{k+1}) must be true as well. That is, using our above assumption, we want to show the below is true:Inductive HypothesisP_{k}: k
∑
i=11 i(i+1)= k k+1is true. P_{k+1}: k+1
∑
i=11 i(i+1)= k+1 (k+1)+1  At this point, since both statements P_{k} and P_{k+1} are written in sigma notation (Σ), it's hard to see how we can apply our hypothesis of P_{k} to P_{k+1}. To deal with this, let's expand both of them into versions using an ellipsis (…) to see the pattern:
P_{k}: k
∑
i=11 i(i+1)= k k+1⇒ 1 1(1+1)+ 1 2(2+1)+ … + 1 k(k+1)= k k+1P_{k+1}: k+1
∑
i=11 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 P_{k+1} so that it included an easily recognizable part from our inductive hypothesis of P_{k}. This allows us to apply our hypothesis.
We can easily substitute the bracketed portion [ ] for what we know from our inductive hypothesis P_{k}. Plug in:P_{k+1}: ⎡
⎣1 1(1+1)+ 1 2(2+1)+ … + 1 k(k+1)⎤
⎦+ 1 (k+1) ⎛
⎝(k+1)+1 ⎞
⎠= k+1 (k+1)+1⎡
⎣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 leftside 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)]
[(k^{2}+2k+1)/((k+1)(k+2))] = [(k+1)/(k+2)] Finally, notice that we can factor the leftside 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 P_{k} is true, we have shown that P_{k+1} must also be true.
Therefore, by showing the base case and inductive step, the principle of mathematical induction says that the statement P_{n} must be true for all positive integers n. Thus we have shown that the below is true for all positive integers n:n
∑
i=11 i(i+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 P_{n} 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.
Notice how the above is just a restatement 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.P_{n}: The number (n^{2}+3n) is an even number.  Now that we have our general statement of P_{n}, we need to show that the base case of P_{1} is true. Base Case:
To verify that P_{1} is true, let's look at the number:P_{1}: The number (1^{2}+3·1) is an even number.
We know the number 4 is an even number, so the statement P_{1} is clearly true and the base case is complete.(1^{2}+3·1) = 1 + 3 = 4  Once the base case is complete, we move on to the inductive step. The inductive step begins with the inductive hypothesis, the assumption that P_{k} is true. Inductive Step: We assume that our inductive hypothesis is true:
Using this inductive hypothesis, we now show that the next statement (P_{k+1}) must be true as well. That is, using our above assumption, we want to show the below is true:Inductive HypothesisP_{k}: The number (k^{2}+3k) 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 P_{k+1}.P_{k+1}: The number ⎛
⎝(k+1)^{2}+3(k+1) ⎞
⎠is an even number.  Unlike previous problems, we don't have a clear way to plug in and use the hypothesis of P_{k}. Previously, all the statements were twosided equations, and one of the sides contained a part that looked like part of the hypothesis P_{k}, 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 P_{k} appear in the statement of P_{k+1}. We can do this by expanding the number P_{k+1} is based on, then hopefully seeing the number P_{k} is based on contained in that. Try expanding P_{k+1}'s number:
⎛
⎝(k+1)^{2}+3(k+1) ⎞
⎠k^{2}+2k +1 + 3k+3
At this point, remember that the number from P_{k} was (k^{2}+3k). Notice that we can pull that part to one "side" in the number from P_{k+1}:k^{2} + 5k + 4 k^{2} + 5k + 4 = ⎡
⎣k^{2}+3k ⎤
⎦+ 2k+4  At this point, we can finally use our inductive hypothesis. The hypothesis P_{k} guaranteed that (k^{2}+3) is an even number. We have shown that the number from P_{k+1} can be written as
Thus, this number is made from adding up three numbers:⎡
⎣k^{2}+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 P_{k+1} is even as well. From the inductive hypothesis P_{k}, we know (k^{2}+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 P_{k+1} is even, which verifies the statement we set out to show and completes the inductive step.[k^{2}+3k], 2k, 4
Therefore, by showing the base case and inductive step, the principle of mathematical induction says that the statement P_{n} must be true for all positive integers n. Thus we have shown that the below is true for all positive integers n:The number (n^{2}+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 P_{n} 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.
Notice how the above is just a restatement 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.]P_{n}: The number (9^{n}−2^{n}) is divisible by 7.  Now that we have our general statement of P_{n}, we need to show that the base case of P_{1} is true. Base Case:
To verify that P_{1} is true, let's look at the number:P_{1}: The number (9^{1}−2^{1}) is divisible by 7.
The number 7 is clearly divisible by 7, so the statement P_{1} is true and the base case is complete.(9^{1}−2^{1}) = 9−2 = 7  Once the base case is complete, we move on to the inductive step. The inductive step begins with the inductive hypothesis, the assumption that P_{k} is true. Inductive Step: We assume that our inductive hypothesis is true:
Using this inductive hypothesis, we now show that the next statement (P_{k+1}) must be true as well. That is, using our above assumption, we want to show the below is true:Inductive HypothesisP_{k}: The number (9^{k}−2^{k}) is divisible by 7.
In other words, we must show that ( 9^{k+1} − 2^{k+1} ) is indeed divisible by 7, thus verifying the statement P_{k+1}.P_{k+1}: The number ( 9^{k+1} − 2^{k+1} ) is divisible by 7.  Unlike past problems, we don't have a clear way that we can plug part of P_{k} in to the expression we have for P_{k+1}. However, we know that we somehow need to have the number from P_{k} appear in the number for P_{k+1} so we can use our inductive hypothesis. With this in mind, look for a way to rearrange the number for P_{k+1} so that the number from P_{k} (that is, 9^{k}−2^{k}) will appear:
First, we need to have 9^{k} and 2^{k} appear, so take the exponents down by one by "popping out" a multiplier of the appropriate base:P_{k+1} ⇒ 9^{k+1} − 2^{k+1}
Next, we need to get the expression (9^{k}−2^{k}) to appear. We can do this by moving things around cleverly:9^{k+1} − 2^{k+1} = 9^{k}·9 − 2^{k}·2
Finally, we cause it to clearly appear by using the distributive property in reverse:9^{k}·9 − 2^{k}·2 = 9^{k} ·2 + 9^{k} ·7 − 2^{k} ·2 = 9^{k}·2 − 2^{k} ·2 + 9^{k} ·7 9^{k}·2 − 2^{k} ·2 + 9^{k} ·7 = 2·( 9^{k} − 2^{k} ) + 9^{k} ·7  Now we have the number from P_{k+1} expressed in such a way that we can use our inductive hypothesis from P_{k}. However, to formally prove this, we need a way to talk about what our inductive hypothesis is saying. Notice that the below
is equivalent to the statement thatP_{k}: The number (9^{k}−2^{k}) is divisible by 7,
Why? If there is some integer a where 9^{k}−2^{k} = 7 ·a, then (9^{k}−2^{k}) must be divisible by 7 since (7·a) is clearly divisible by 7. And if no such number a existed that would work, then (9^{k}−2^{k}) could not be divisible by 7, so we know the a must exist (even if we don't know its value).There exists some integer number a such that 9^{k}−2^{k} = 7 ·a.  With this restatement of P_{k} in terms of (7·a) in mind, let's look again at the number from P_{k+1}:
Swap out the ( 9^{k} − 2^{k} ) for (7·a):P_{k+1} ⇒ ( 9^{k+1} − 2^{k+1} ) = 2·( 9^{k} − 2^{k} ) + 9^{k} ·7
We can now pull out a 7 from both terms to get2·(7 ·a) + 9^{k} ·7
which must be divisible by 7, because we clearly have a factor of 7 contained in the number. Thus we have shown that P_{k+1} is divisible by 7, which completes the inductive step.7 · (2 ·a + 9^{k}),
Therefore, by showing the base case and inductive step, the principle of mathematical induction says that the statement P_{n} must be true for all positive integers n. Thus we have shown that the below is true for all positive integers n:The number (9^{n}−2^{n}) is divisible by 7.
Theorem: All horses are the same color. "Proof" (by mathematical induction): Let the general statement be




 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, stepbystep.
 To begin with, the general statement P_{n} 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 P_{1}:
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 colorthe color of the horse in the group.P_{1}: A group of 1 horse is all the same color.  Now we move on to the inductive step. The "proof" begins by putting all (k+1) horses from P_{k+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 subgroups 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 subgroups, and since it's ordered, we can easily choose what goes into each subgroup.
 Finally, we make it to where the mistake occurs: the next part of the "proof" says that these two subgroups 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 subgroups, where each subgroup 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 subgroups 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.
*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 screencaptured 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
Precalculus with Limits Online Course
Transcription: Mathematical Induction
Hiwelcome 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 truththat we start with some things that we can just take for granted,0030
absolutely certainlythese axiomatic truths that we looked at in geometry, for example, previouslyyou 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 p_{n}, the n^{th} 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 p_{0}, then that would be equal to 2 to the 2 to the 0 plus 1.0162
What is 2^{20}? 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 2^{21} + 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 2^{23} + 1 is 257; and you can checkthat 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 4raising 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 2^{25}, plus 1, which is equal to a huge 4 billion, 294 million, 967 thousand, 297a 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 hypothesisan expectation,0268
of how things will work: that all numbers of the form 2^{2n} + 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 conjectureif 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, p_{5}, 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 primethat 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 counterexample0344
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...) fallingover 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 d_{1}.0401
Here would be our d_{1}, our first domino.0407
The next domino we could call d_{2}; our second domino is d_{2}, and so on.0409
Here would be d_{3} and d_{4}, 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, d_{1}, will definitely fall over.0440
We are going to be absolutely certain that d_{1} is going to fall over.0445
Our first domino, d_{1}, 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 d_{k} and d_{k + 1} for any positive integer k,0477
some d_{k} in the line, and then the next one would be called d_{k + 1}0482
if we are at the k spot, the k + 1 would be the next spot), if d_{k} falls,0486
if the domino on the left falls (d_{k} is the domino on the left), then the next domino in line,0490
d_{k + 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 d_{k} falls, d_{k + 1} must fall.0516
We have here that d_{k} falls; and then, at the next one...we have d_{k} falls;0522
if d_{k} falls, d_{k + 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, d_{1},0549
is definitely going to fall over; and that, if some domino, some d_{k} falls over,0554
it will cause the next domino, d_{k + 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 d_{1} 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 d_{1} must fall.0594
But by the second guarantee, we know that d_{2} must fall, because d_{1} is the one before d_{2}.0597
So, d_{2} must now fall, as well; then, by our second guarantee, once again,0602
since d_{2} just fell, we know that d_{3} must fall.0606
Then, by our second guarantee, again, we know that since d_{3} just fell, we know that d_{4} must fall.0609
And then, since d_{4} just fell, d_{5} must fall; d_{6} must fall; d_{7} must fall;0614
d_{8}, d_{9}, d_{10}, 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 d_{1} falls, we know that d_{2} must fall; we know that d_{3} must fall;0633
and we can work our way out, going forever.0636
This is inductive thinking, stepbystep 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 d_{1}, 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 saythat 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 p_{1}, p_{2}, p_{3}, p_{4}...0694
going on...p_{n}...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 p_{1} is true, and if p_{k} is true for a positive integer k,0711
then p_{k + 1} must also be true; then we know that the statement p_{n} 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 p_{1}; it is definitely truethe very first one (we have p_{1}, p_{2}, p_{3},0732
p_{4}, p_{5}...going on forever; we effectively have this infinitely long line of sequences).0736
And we are guaranteed, by our very first thing, that p_{1} has to be true; p_{1} 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 p_{1} is true; that means that p_{2},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 p_{3} must be true;0757
p_{4} must be true; p_{5} must be true; p_{6} must be true.0761
And it goes on forever and ever and ever, and that is why we now know that p_{n} 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, stepthat 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 p_{1} 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 occurs0806
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 p_{k} is true (this part right here, the "if p_{k} is true")0824
is called the inductive hypothesis, because it is the hypothesis that we use to show that p_{k + 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 statementjust 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 mathwe 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, p_{n},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 answerthe 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 p_{n} for any 1, 2, 3, 4, going on forever0979
that they are all truewe 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, p_{n}, is true for all n, we must prove two things:1017
first, the base case, that p_{1} is truethat our very first statement is a true statement;1022
and then, we have to do the inductive step: that if some p_{k} is true,1029
the next one in line, p_{k + 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 statementwhatever this p_{1} statement ends up being;1078
and we verify that it is, indeed, a true statementit 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, "p_{k} is true."1093
We have to start by assuming that if p_{k} is true...we have to say,1098
"OK, p_{k} is true; now let's show that p_{k + 1} is also going to be true."1102
Once we make this assumption, we somehow have to work to prove that p_{k + 1} must then also be true.1108
Now, notice: we haven't actually proven p_{k} to be true; we are just asking ourselves,1112
"If p_{k} were true, would p_{k + 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 p_{k} when we are writing out p_{k + 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, "p_{k} is true."1151
Otherwise, we wouldn't have needed to talk about p_{k} being true, to show that p_{k + 1} is true.1154
So, we are going to end up using that inductive hypothesis, that p_{k} is true.1159
So, we have to have some way of talking about it in our p_{k + 1} statement.1163
We can't use our hypothesis about p_{k} unless it somehow appears in p_{k + 1}.1167
That means, when we end up writing out the p_{k + 1} statement, that we have to figure out some way1175
to make p_{k}, or some portion of p_{k}, 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, p_{n}; we can turn this into our statement, p_{n}, this right here.1238
How would this work? Well, our first statement, p_{1}, would be if we went from 1 up until an n of 1 (p_{1}, so 1 up until 1).1246
Well, that is just going to end up being 1; so 1 added to itselfis 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 p_{2}, 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, p_{3}, 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 p_{n}, 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, p_{n}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 p_{n} = 1 added to all the numbers up until n is equal to n times n + 1 over 21303
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, p_{1}, and the inductive step, that p_{k} implies p_{k + 1}.1314
The truth of some p_{k} in the middle implies that p_{k + 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 p_{1} 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 p_{k} is true..." so we assume that p_{k} (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: p_{k}, which is the statement 1 + 2 + 3...up until + k = k + (k + 1)/21399
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 p_{k + 1} must also be true.1426
We can write out p_{k + 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 p_{k} 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 p_{k + 1} must be true.1467
We need to get some way to see some portion of p_{k} appear.1472
We realize that we can rewrite what we have here: we could write p_{k + 1} as it is above, but we can't easily see p_{k} in it.1476
So instead, we write it out as p_{k + 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 p_{k} 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 mark1547
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 p_{k} hereour inductive hypothesis, p_{k}.1561
We can substitute p_{k}, 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 itwe 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 p_{k + 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, p_{k + 1} is true.1616
And we will have shown that p_{k + 1} is true from p_{k}, 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 k^{2} + 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, k^{2}, plus 2k + 1k, so 3k, plus 1 times 2, 2.1650
So, we get k^{2} + 3k + 2, all over 2.1659
Now, we just combine these two fractions here, k^{2} + k over 2, plus 2k + 2 over 2.1662
It is going to be k^{2} + k + 2k + 2, all over 2, which simplifies to a nice k^{2} + 3k + 2, over 2,1667
which is equal to k^{2} + 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 p_{k} true, then p_{k + 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 p_{n} 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 Sequencesyou 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 1^{2} + 2^{2} + 3^{2} + ... + n^{2} = n times n + 1 over 2n + 1.1840
This is effectively our statement p_{n}...not effectively; this is our statement p_{n}.1849
Adding all of the squares, 1^{2} + 2^{2}...up until n^{2}, 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 1^{2} 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
1^{2} 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 p_{k},1918
which would be 1^{2} + 2^{2}...up until we get to some k^{2}1923
(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, p_{n}, 1^{2} + 2^{2} + 3^{2}...1944
up until n^{2}, 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 showit is our job to now showthat p_{k + 1} is true.1957
It is our job to show that p_{k + 1} ends up being true.1963
Showing that p_{k + 1} is true is going to end up being equivalent to showing that 1^{2} + 2^{2} + ...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 p_{k} 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 1^{2} + 2^{2} ... + (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: + k^{2} + (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 1^{2} + 2^{2} + ... up until k^{2},2032
so we can swap that in for what is here at p_{k}, 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
"maybeitis," 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 2k^{2};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 k^{2} + 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 2k^{2}; 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 2k^{2} is 2k^{3}, plus 3k^{2}, plus k, all over 6.2149
Plus...6k^{2} + 12k + 6, all over 6; and is that equal to (k + 1) times (2k^{2} + 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 2k^{2} is going to come out to be 2k^{3}.2181
k times 7k is 7k^{2}; plus...1 times 2k^{2}...7k^{2} + 2k^{2} is 9k^{2};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 2k^{3}...2201
everything will be divided by 6 over here...2k^{3} plus nothing on our other fraction,2206
so that is just that...3k^{2} + 6k^{2}...we get 9k^{2};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 2k^{3} + 9k^{2}?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, p_{1}, being true,2245
and if p_{k} is trueour inductive hypothesisthen p_{k + 1} is true, which we just showed here)2249
we combined those two things, so now we have shown that p_{n} is true for all things:2255
that 1^{2} + 2^{2} + 3^{2}...up until + n^{2} 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 n^{3} + 2n is divisible by 3.2269
So really, this is our statement, p_{n}: p_{n} is "n^{3} + 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 p_{1} statement would be true.2289
Verifying p_{1} is the same thing as verifying that 1^{3} + 2(1) is divisible by 3.2295
1^{3} + 2(1) is 1 + 2, or 3; that is divisible by 3that 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 p_{k} ends up being true.2331
What is p_{k}? p_{k} would be if we plugged in k for our n here: k^{3} + 2k is divisible by 3.2336
This is our starting assumption: that k^{3} + 2k is divisible by 3.2349
At this point, we now want to show that p_{k + 1} is true.2353
Showing that p_{k + 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 k^{2} + 2k + 1.2402
Plus...2 times (k + 1)...that is 2k + 2.2407
k + 1 times k^{2} + 2k + 1...well, k times k^{2} is going to be k^{3};2411
k times 2k is 2k^{2}, plus 1 times k^{2}, so + 3k^{2};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 k^{3} + 2k is definitely divisible by 3."2433
Look: here is k^{3}; here is 2k; let's bring them together.2444
Now, we have k^{3} + 2k; and we will put everything else on the other side.2447
So, 3k^{2} + 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
k^{3} + 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 k^{2} + k + 1.2470
Now, at this point, we realizelook, 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 k^{2} + 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 p_{k} is true, then p_{k + 1} is true.2526
So, we have now shown the inductive step; since we have shown that p_{1} is true,2530
and if something in the middle is true, then the next thing is true;2535
then p_{1} being true implies that p_{2} must be true, by our inductive step,2538
which implies that p_{3} must be true, by our inductive step; p_{4}, p_{5}, p_{6}, p_{7}...2541
So, we know that, forever and always, n^{3} + 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 n^{th} 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 ownwell, 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 n^{th} partial sum is going to be equal to n^{2}; great.2618
What we have here is 1 + 3 + 5 + ... + something...whatever we end on...is equal to n^{2}.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 n^{th} term here, a_{n}, 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 p_{n} statement, is that 1 + 3 + 5, working up until 2n  1, is equal to n^{2}, 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 n^{2} 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 p_{n} is true for any value of n:2731
that 1 + 3 + 5...up until + 2n  1 is equal to n^{2}, 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 p_{1} 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 sideis that equal to 1^{2}?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 p_{k} is true.2780
What is the statement p_{k}? Well, that would be 1 + 3 + ... up until we get to +...plug in k for n...2k  1 = k^{2}.2783
So, we are assuming that 1 + 3 + ... + 2k  1 is equal to k^{2}.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, p_{k + 1}, that part of it, is going to just be equal to k^{2}, right here.2885
So, we can swap out k^{2} here; so now we have k^{2} 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 k^{2}; we expand this; well, k^{2} + (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 k^{2} + 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 p_{k} being true, we know that p_{k + 1} must be true.2941
Because we know that our base case is true (p_{1} is true), and we know that if something is true,2945
then the next thing has to be true; then since p_{1} is true, the next thing must be true.2949
p_{2} is true; p_{3} is true; p_{4} is true; p_{5} is true; p_{6} 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 donepretty cool.2968
The only really challenging part therethat wasn't that difficult of a proof by induction, compared to the ones that we did previously2972
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 latergoodbye!2991
Start Learning Now
Our free lessons will get you started (Adobe Flash^{®} required).
Sign up for Educator.comGet immediate access to our entire library.
Membership Overview