Hi. In this video, we're going to talk about sums of numbers and we'll invent a short formula to compute sums of integer numbers really fast. But first, I will tell you a story. This man, Carl Friedrich Gauss, is often called the Prince of Mathematicians because of many things that he proved and many theories that he developed. His impact on mathematics is huge. The story is actually about his childhood. When he studied in school, his teacher was often annoyed by this boy who was always solving all the problems, always raising his hand, always talking, and he wanted to actually try to teach other students in his class. And so, he wanted to somehow get rid from Gauss for some time to explain something to students which are not so quick. He came up with an idea, and he gave Gauss what he thought was a pretty hard problem. Not so hard in terms that Gauss wouldn't be able to solve it, but hard in terms that it will keep him busy for some time. So, he asked him to sum all the numbers from 1 to 100. What teacher imagined was that Gauss will have to sum these numbers one by one, and he will make mistakes in the middle, and he will use all of paper to do that. And then, it'll keep him busy probably for the whole lesson. So the teacher will be free to actually explain something to other students. But, it didn't happen that way. Actually, after thinking for maybe two minutes, Gauss came up with an answer. Teacher was very suspicious about getting this answer because he didn't know the way to get the sum so fast. But then, he checked the solution and it turned out to be correct. We're going to solve this problem, but we're going to generalize a little. We're going to solve the problem of what is the sum of all integer numbers from one to n, for any n. And the theorem below says that the sum of these integers from one to n can be computed using this simple formula with one multiplication and one division; n times n plus one, divided by two. We are going to prove this theorem now. To do that we will use proof by induction, which we already know from the previous two videos. To proof something by induction we need two things; to prove induction base and induction step. Induction base in this case is for n equals one. If n equals one, then the sum of numbers from one to n, one plus two plus and so on up to n, is actually just one. Just one summant. The formula gives us the answer that the sum should be equal to one times two, divided by two. This is actually correct. So, for the easy case, for any closed one, we have proven our theorem. This is true. Now, let us make the induction step from n to n plus one. We assume that the formula works for sum n. That the sum of numbers from one to n, is equal to n times n plus one over two. And we want to prove the same thing for n plus one. So what happen is, we'll write down the sum from one to n plus one, and then we use the assumption of the induction that the sum of the first n numbers is equal to n times one plus one over two. So, this exclamation mark above the equality sign is the marking that we used the assumption of the induction. And also, we need not forget the last summant which is n plus one. So add n times one plus one over two, plus n plus one. We get both summants to the common denominator two, and in the numerator we get n times one plus one, plus two times n plus one. Now, we have a common multiple there, n plus one, and we can rewrite this numerator as n plus one times n plus two, and the denominator is two. So, we see that the formula is the same, but just for n plus one instead of n. And so, we have proven the induction step from n to n plus one. And now, our theorem is already proven because we're proved both the induction base for n equals one, and the induction step from n to n plus one. So, we can go from one to two, to three, to four and to any integer number. So, our theorem is true. And now, we can understand how did Gauss compute the answer so fast. But, the question is, how do you actually come up with this formula in the first place? So when we know the formula, it was relatively easy. We could prove it using mathematical induction, and then we can use it to find the answer. But, how did Gauss come up with this, and how can you come up with this? Well, the answer is the following. The Gauss's idea was to write the sum of numbers from 1 to 100, in the forward direction, and then below it, in the backward direction. So that, number 100 in the backward direction, is directly below number one in the forward direction. Number 99, is exactly below number two and so on. Number two in the backward direction, is exactly below number 99 in the forward direction, and one is directly below 100. So we have these 100 columns. In the first one we get one and 100, in the second we get two and 99 and so on. And now, we want to compute the sum of these two equations. On the left part, we will get S plus S, where S is some unknown sum of all the numbers between 1 and 100. So it will get two S on the left side, and on the right side, we can sum the columns independently, and we can notice that some of the numbers in every column is exactly 101. One plus 100 is 101, 2 plus 99 is 101 and so on. So we have exactly 100 columns, with number 101 written in each column. So the sum of those numbers is obviously just 100 times 101. And so to get S which is unknown, we should just divide this by two because the left part is two S, and to get just S, we need to divide by two. So, the answer is 100 times 101 divided by 2. And this week, I already computed on paper, and it turns out that the answer is 5,050. Actually, if we changed 100 to n in this slide, and we made all the same statements, and we made all the same arrangements in the forward direction and the backward direction. Then, we would get the formula n times n plus one over two directly. It actually would be another way to prove the same formula, without mathematical induction and it happens. So, in this case, that we actually don't need to use mathematical induction to prove this fact. We can just go directly to the formula, we can see what is the formula, and we will get the proof immediately without proving the induction base and induction step. It sometimes happens that you can prove the same statement different ways, and sometimes it also happens that before you can apply mathematical induction, first you have to come up with the formula. In this case, while you're coming up with the formula, you can also prove the statement itself. This is a beautiful example of how children can be very inventive, and come up with ideas that older people just don't know of. And this is a beautiful mathematical problem which shows that you can use mathematical induction to prove statements, but you can also come up with different inventive ways and proofs statements directly.
