[SOUND] Hi! This is the final video about mathematical induction. And we are going to consider a harder problem here. And this is actually a good example of a problem where it is unclear how to solve it without using mathematical induction. The problem is the following. We need to prove the equality of an alternating sum and a regular sum. The alternating sum on the left is 1-1 over 2, + 1 over 3,- 1 over 4, and so on with alternating pluses and minuses up to 1 over 99- 1 over 100. And the sum on the right is from 1/51 + 1/52 and up to 1/100. It is really unclear how to solve this problem directly, because we could of course try to get all the fractions to the common denominator. But this common denominator will be a product of 100 numbers, and it will be huge. And in the numerator we will have an alternating sum of products, of 99 numbers, pluses and minuses and we'll have to do a lot of computations with really huge numbers. And instead of that, we're going to avoid computations with big numbers at all. But first we're going to use generalization, so instead of solving this initial problem, let's solve a more general problem actually. We're going to prove that the alternating sum 1- 1 over 2 + 1 over 3- 1 over 4, and up to 1 over 2k-1, minus 1 over 2k for some integer k Is always equal to 1 over k + 1 + 1 over k + 2, and up to 1 over 2k. And you should notice that for k = 50, this is exactly the same as the initial problem because the alternating sum on the left goes from 1- 1 over 2, up to 1 over 2k-1 is 91, 1 over 99- 1 over 100. So, this is the same alternating sum. And on the right, the sum starts with 1 over k+1, which is 1 over 51. And the last summand is 1 over 2k, which is 1 over 100, which is the same as in the initial problem. So, this is indeed a more general problem. And now that we see it is a more general problem, we can actually prove it for any k using mathematical induction. And to do that, we'll first prove the induction base for k = 1. For k = 1, the alternating sum on the left has exactly two summands, 1- 1 or 2. And the right part just has one sum and 1 over k + 1, where k is the gold one, so it is 1 over 2. And we see that the alternating sum is equal to the right part. So, we prove the induction base for k = 1. And now we want to prove the induction step. To move from k to k + 1. And to avoid writing really long formulas, let's see what changes in the left and the right part when k increases by one. So we know that for k, the left part is equal to the right part. And we want to prove that for k + 1 the left part will also be equal to the right part. Instead of comparing the whole left and right part for k + 1, we'll just compare the differences in the left part and in the right part. And if the initially the left part is equal to the right part, and the differences are equal than the left part and right part for k + 1 are also equal. So for the alternating sum, when we increase k by 1, we always get two more summands. We get one with plus and one with minus. So with plus we have 1 over 2k + 1, and with minus we have 1 over 2(k + 1). So this is by how much the left part will increase when we increase k by 1. Now let's look at k + 1 and the right part. So the right part for k + 1 starts with 1 over k + 2, and goes up to 1 over 2k + 1. But I also explicitly wrote the last three summands. 1 over 2k, 1 over 2k + 1, and 1 over 2 times k+ 1. Now what we can do is a magical trick in math, is we can add 0 to anything and it will stay the same. And to add 0 we can actually subtract something and add something. So in the left we subtract 1 over k+1 and add it back. And so nothing changes and so we have a equality of the first line and the second line. Now I want to rearrange our summands. We want to notice that starting from the second sum and in the second line, we get the right part for K. We get the sum from 1 over k + 1, 1 over k + 2 plus 1 over k + 3 and up to 1 over 2k. And then we have three more summands which are not in this sum. Two of them are the two last summands for k + 1. Those are 1 over 2k + 1 plus 1 over 2 times k + 1. And also there is the summand that we subtracted in the second line. 1 over k + 1. So the right part changes by exactly these three last summands. I over 2k + 1 plus 1 over 2 times k + 1 minus 1 over k + 1. And we can actually simplify this expression, if we notice that 1 over 2 times 2k + 1- 1 over k + 1 is the same as -1 over 2 x k + 1. And so actually, when we rewrite it and simplify it, we see that the right part, changes from k to k + 1 by the same value. 1 over 2k + 1- 1 over 2 times k + 1 as the left part. So left part and right part change by the same amount, and they were the same for k, so they are the same for k + 1. And we have proven the induction step. And as we have proven both the induction base and the induction step from k to k + 1. We have proven the general statement, and we know that the alternating sum on the left is equal to the sum on the right for any k. In particular, it is also true for k equal 50, and so we solve their problem. As I said, this is the last video about mathematical induction so it's time to make some conclusions. We see that mathematical induction is a powerful proof method because we solved a lot of problems with it. And some of the problems couldn't be solved without it. To apply it, we first need to reformulate problem in mathematical terms, then we need to prove induction base. Which is basically the proof of our statement for several small values of n. In most cases just for one smallest value of n. Then we need to prove the induction step, and in the simple case, in the weak induction, we just prove from n to plus 1, assuming that this statement is true for n, we prove that it is also true for n plus 1. But sometimes we need to apply a strong induction, or complete induction, when we use induction step from several values of n to n plus 1. And in this case, we need to remember to also prove induction base for the corresponding number of smallest values of n, not just for one but for many as we use in the induction step. Also, sometimes for induction we often need to come up with a formula somehow before, proving this formula. We saw this example in the girl's teacher's problem. And also, as we saw in this last lecture, we sometimes need to generalize our problem before we can see that induction can be applied. So in this problem, we were proving something for a formula with a alternating sum of 100 summands and the regular sum with 50 summands. We generalize it for alternating sum with 2k summands and the regular sum with k summands. And then we were able to apply induction and prove it for all values of k. In particular for k equals 50. So sometimes you need to generalize, and this makes your problem harder from one point of view. But it actually makes it simple because then you can apply mathematical induction and this powerful proof method solves their problem. See you next week. [SOUND] [MUSIC]
