Proving an expression for the sum of all positive integers up to and including n by induction. Created by Sal Khan.
Want to join the conversation?
- what is the meaning of induction..??(33 votes)
- Mathematical induction is a method of mathematical proof typically used to establish a given statement for all natural numbers. It is done in two steps. The first step, known as the base case, is to prove the given statement for the first natural number. The second step, known as the inductive step, is to prove that the given statement for any one natural number implies the given statement for the next natural number. From these two steps, mathematical induction is the rule from which we infer that the given statement is established for all natural numbers.(30 votes)
- How does someone come up with a formula like this? How do I derive it?
Is this something obtained simply through observation that if you take a number and multiply it by the integer of adding one to it, and dividing by two that you obtain the sum of the integers up to and including itself; trial and error?
And is this process of trial and error common as you continue to progress towards more advanced theories like this one?
Thank you.(16 votes)
- Not a general method, but I came up with this formula by thinking geometrically. Summing integers up to n is called "triangulation". This is because you can think of the sum as the number of dots in a stack where n dots are on the bottom, n-1 are in the next row, n-2 are in the next row, and so on. The result is a triangle:
. . .
. . . .
So we need a general formula for the number of dots in this triangle if we know the size of the base. 1/2*base*height doesn't quite work because of the jagged edge on the right, but the big insight is that you can copy the triangle, flip it upside down, then fit the two together to get an n*(n+1) rectangle. So the original triangle has half the dots of this rectangle, or n*(n+1)/2.(42 votes)
- I greatly appreciate these videos. But I'm not sure that I'm really getting the hang of it, though. Would it be possible to include a few exercises, giving us the opportunity to practice this a bit?(17 votes)
- Induction always took a little while for me to fully get used to. Doing a ton of practice problems really really helps.
Here's a link to some problems with their solutions. I suggest you try to do these problems without looking at the solutions first :)
Hope this helps you in some way.(29 votes)
- How would you prove 1+3+5+...+(2n-1)=n^2 by induction?(11 votes)
- You would solve for k=1 first. So on the left side use only the (2n-1) part and substitute 1 for n. On the right side, plug in 1. They should both equal 1. Then assume that k is part of the sequence. And replace the n with k. Then solve for k+1.
The right hand side simplifies to (k+1)^2(20 votes)
- This is a very different kind of maths compared to calculus, in my opinion much more abstract because I like to SEE what something means. The process of mathematical induction confuses me quite a bit because I cannot seem to reason with myself as to how to go about getting to the solution. Why do we use the character "k" and not stick with "n", would the answer not be the same, and furthermore, would a better name for this process not simply be "substitution"?(8 votes)
- Henry, in mathematical induction, we do not use the n when solving from this because the symbol n is be being used already to signify the function. We use k to reduce the confusion between the two and k resembles a constant which you may use in calculus math.(9 votes)
- me and my dad tried this sum of mathematical induction for over 1hr but were still unsuccessful. Could anyone help me in this?
1^2 + 2^2 + 3^2 +..............+ n^2= 1/6 * n(n+1)(2n+1)(4 votes)
- Show it is true for a base case
∑ a^2 from a=1 to 1 = 1/6 * 1 * (1+1) * (2*1+1)
1^2 = 1/6 * 1 * 2 * 3
1 = 1 √ (that's a check)
Show that if it is true for k it is also true for k+1
∑ a^2, a=1...k+1 = 1/6 * (k+1) * (k+1+1) * (2t(k+1)+1)
(1^2 + 2^2 + 3^2 + ... + k^2) + (k+1)^2 = (This is the key step)
(k)(k+1)(2k+1)/6 + (k+1)^2 =
(k+1) * [(k)(2k+1)/6 + (k+1)] =
(k+1)/6 * [(k)(2k+1) + 6(k+1)] =
(k+1)/6 * (2k^2+k+6k+6) =
(k+1)/6 * (2k^2+7k+6) =
(k+1)/6 * (2k+3)(k+2) = (k+1)(k+2)(2k+3)/6 √
Where I said "this is the key step" was the key step (obviously). With these sum induction problems, it is typically best to group the first k addends and replace them with your assumed form. From there, it's just algebra.(11 votes)
- how would you solve 2+4+6+8+....2n=n(n+1) by induction?(3 votes)
- First step base case2:02, n=1: 2=1*(1+1), seems like works. Next let's assume that n is equal to some k (step 2): 2+4+...+2*k=k*(k+1). Now time to proof for n=k+1 elements, if it works for n=k elements and for (k+1) then it works for the whole series (2:23), ok lets put (k+1):
2+4+..+2*k +2*(k+1)=(k+1)*((k+1)+1), BUT we assumed earlier that 2+4+..+2*k=k*(k+1), so we put to cut our series to:
k*(k+1)+2*(k+1)=(k+1)*((k+1)+1), now lets prove that left part is equal to right:(k+1)*(k+2)=(k+1)*((k+1)+1)
(k+1)*((k+1)+1)=(k+1)*((k+1)+1), so now I can say that if we need to count sum of 2+4+6+8+..+2*n elements (n=10000 for example) this is the same thing as count it through equation n*(n+1), which is much faster and easier.(11 votes)
- If n=1 does not work, then does it mean that the series cannot be proven?(4 votes)
- If n=1 does not work, then n=1 is a counter example and therefore you cannot prove it with the method you are using(3 votes)
- What is Induction actually?(3 votes)
- Whilst I understand the process I'm still unsure why step one works the way it does, at least in the way it is phrased in my textbook. Say we have to prove 1+3+5+7+...+(2n-1)=n^2. I know first you prove for n=1 and to do so you equate the final term of LHS with RHS, but I'm just confused why you can ignore all the previous terms (1+3+5+7...)?(2 votes)
- There are no previous terms. The notation is just sloppy. They write 1+3+5+7+...+(2n-1) to establish the pattern but what they really mean is
When you learn Sigma notation you'll have a better way of writing 1+3+5+7+...+(2n-1) without making it look like the first term is n = 5.(2 votes)
I'm going to define a function S of n and I'm going to define it as the sum of all positive integers including N. And so the domain of this function is really all positive integers - N has to be a positive integer. And so we can try this out with a few things, we can take S of 3, this is going to be equal to 1 plus 2 plus 3, which is equal to 6. We could take S of 4, which is going to be 1 plus 2 plus 3 plus 4, which is going to be equal to 10. Now what I want to do in this video is prove to you that I can write this as a function of N, that the sum of all positive integers up to and including N is equal to n times n plus one, all of that over 2. And the way I'm going to prove it to you is by induction. Proof by induction. The way you do a proof by induction is first, you prove the base case. This is what we need to prove. We're going to first prove it for 1 - that will be our base case. And then we're going to do the induction step, which is essentially saying "If we assume it works for some positive integer K", then we can prove it's going to work for the next positive integer, for example K + 1. And the reason why this works is - Let's say that we prove both of these. So the base case we're going to prove it for 1. But it doesn't always have to be 1. Your statement might be true for everything above 55. Or everything above some threshold. But in this case, we are saying this is true for all positive integers. Our base case is going to be 1. Then in our induction step, we are going to prove that if you assume that this thing is true, for sum of k. If we assume that then it is going to be true for sum of k + 1. And the reason why this is all you have to do to prove this for all positive integers it's just imagine: Let's think about all of the positive integers right over here. 1, 2, 3, 4, 5, 6 you could just keep going on forever. So we are going to prove it for 1. We are going to prove that this formula right over here, this expression right over here applies for the case of 1, when n is 1. And then we are going to prove that if we know it is true for any given k that is true for the next one So if we know it is true for 1 in our base case then the second step, this induction step must be true for 2 then. Because we proved generally if it's true for k it's going to be true for k + 1. When it's true for 2, then it must be true for 3, because we have proved it, when it's true for k, it's true for k + 1. So if it's true for 2 it's true for 3. and if it's true for 3 it's going to be true for 4. You can just keep going on and on forever, which means it's true for everything. Now spoken in generalaties let's actually prove this by induction. So let's take the sum of, let's do this function on 1. that is just going to be the sum of all positive integers including 1 is just literally going to be 1. We've just added all of them, it is just 1. There is no other positive integer up to and including 1. And now we can prove that this is the same thing as 1 times 1 plus 1 all of that over 2. 1 plus 1 is 2, 2 divided by 2 is 1, 1 times 1 is 1. So this formula right over here, this expression it worked for 1, so we have proved our base case. we have proven it for 1. Now what I want to do is I want to assume that it works for some number k. So I will assume true for some number k. So i'm going to assume that for some number k, that this function at k is going to be equal to k times k plus 1 over 2. So I'm just assuming this is true for that. Now what I want to do is think about what happens when I try to find this function for k + 1. This is what I'm assuming. I'm assuming I know this. Now let's try to do it for k + 1. So what is the sum of all of the integers up to and including k + 1? Well this is going to be 1 plus 2 plus 3 plus all the way up to k. Plus k plus 1. Right? this is the sum of everything up to and including k plus 1. Well we are assuming that we know what this already is. We are assuming that we already have a formula for this. We are assuming that this is going to simplify to k times k plus 1 over 2. We are assuming that we know that. So we will just take this part and we will add it to k plus 1. so we'll add it to k plus 1 over here. And if you find the common denominator, the common denominator is going to be 2. So this is going to be equal to... I'll write the part in magenta first. so this is k times k plus 1 over 2 plus 2 times k plus 1 over 2. This thing in blue is the same thing as that thing in blue. The 2's would cancel out, I'd just wrote it this way so I have a common denominator. So this is going to be equal to... We have a common denominator of 2 and I'll write this in a different colour here. So we are going to have k times k plus 1 plus 2 times k plus 1. Now at this step right over here you can factor out a k plus 1. Both of these terms are divisible by k + 1. So let's factor this out. So if you factor out a k + 1, you get k plus 1 times refractoring out over here, if you factor out k + 1 you'd just have a k. Over here if you factor out k + 1 you would just have a 2. Let me colour code those. So you would know what I'm doing. So this 2 is this 2 right over there and this k is this k right over there. We factored it out. These k+1's we factored out is this k+1 over there. And it's going to be all of this over 2. Now, we can rewrite this. This is the same thing. This is equal to. This is the same thing as k plus 1, that's this part right over here. Times k plus 1 plus 1. Right? This is clearly the same thing as k + 2. All of that over 2. Why is this interesting to us? Well we have just proven it. If we assume that this is true and if we use that assumption we get that the sum of all positive integers up to and including k + 1 is equal to k + 1 times k + 1 + 1 over 2. We are actually showing that the original formula applies to k+1 as well. If you would take k + 1 and put it in for n you got exactly the result that we got over here. So we showed , we proved our base case. This expression worked for the sum for all of positive integers up to and including 1. And it also works if we assume that it works for everything up to k. Or if we assume it works for integer k it also works for the integer k plus 1. And we are done. That is our proof by induction. That proves to us that it works for all positive integers. Why is that? We have proven it for 1 and we have proven it that if it works for some integer it will work for the next integer. So if you assume it worked for 1 then it can work for 2. Well we have already proven that it works for 1 so we can assume it works for 1. So it definitely will work for 2. So we get 2 checked. But since we can assume it works for 2 we can now assume it works for 3. Well if it works for 3 well then we have proven it works for 4. You see how this induction step is kinda like a domino, it cascades and we can go on and on forever so it works for all positive integers.