Proof by induction | Sequences, series and induction | Precalculus | Khan Academy
Proof by induction | Sequences, series and induction | Precalculus | Khan Academy
Courses on Khan Academy are always 100% free. Start practicing—and saving your progress—now: https://www.khanacademy.org/math/alge…
Proving an expression for the sum of all positive integers up to and including n by induction
Watch the next lesson: https://www.khanacademy.org/math/prec…
Missed the previous lesson?
https://www.khanacademy.org/math/prec…
Precalculus on Khan Academy: You may think that precalculus is simply the course you take before calculus. You would be right, of course, but that definition doesn’t mean anything unless you have some knowledge of what calculus is. Let’s keep it simple, shall we? Calculus is a conceptual framework which provides systematic techniques for solving problems. These problems are appropriately applicable to analytic geometry and algebra. Therefore…precalculus gives you the background for the mathematical concepts, problems, issues and techniques that appear in calculus, including trigonometry, functions, complex numbers, vectors, matrices, and others. There you have it ladies and gentlemen…an introduction to precalculus!
About Khan Academy: Khan Academy offers practice exercises, instructional videos, and a personalized learning dashboard that empower learners to study at their own pace in and outside of the classroom. We tackle math, science, computer programming, history, art history, economics, and more. Our math missions guide learners from kindergarten to calculus using state-of-the-art, adaptive technology that identifies strengths and learning gaps. We’ve also partnered with institutions like NASA, The Museum of Modern Art, The California Academy of Sciences, and MIT to offer specialized content.
For free. For everyone. Forever. #YouCanLearnAnything
Subscribe to Khan Academy’s Precalculus channel:
/ ช่อง
Subscribe to Khan Academy: https://www.youtube.com/subscription_…
Content
0.933 -> I'm going to define a function S of n
5.133 -> and I'm going to define it as
6.759 -> the sum of all positive integers
16.754 -> including N.
22.221 -> And so the domain of this function is really all
24.995 -> positive integers - N has to be a positive integer.
28.533 -> And so we can try this out with a few things, we can
30.467 -> take S of 3, this is going to be equal to 1 plus
35.2 -> 2 plus 3, which is equal to 6. We could take S of
41.071 -> 4, which is going to be 1 plus 2 plus 3 plus 4,
46.61 -> which is going to be equal to 10.
51.225 -> Now what I want to do in this video is prove to you that
57.441 -> I can write this as a function of N, that the sum of all
62.2 -> positive integers up to and including N is equal to
64.2 -> n times n plus one, all of that over 2.
71.4 -> And the way I'm going to prove it to you is by induction.
76.821 -> Proof by induction.
83.785 -> The way you do a proof by induction is first, you prove
87.867 -> the base case. This is what we need to prove.
96.871 -> We're going to first prove it for 1 - that will be our base case.
101.933 -> And then we're going to do the induction step, which
107.4 -> is essentially saying "If we assume it works for some
111 -> positive integer K", then we can prove it's going to work
115.513 -> for the next positive integer, for example K + 1.
119.467 -> And the reason why this works is - Let's say that
121.995 -> we prove both of these. So the base case we're going to prove it for 1.
130.769 -> But it doesn't always have to be 1.
133.8 -> Your statement might be true for everything above 55.
136.908 -> Or everything above some threshold.
138.667 -> But in this case, we are saying this is true for all positive integers.
141.533 -> Our base case is going to be 1.
144.333 -> Then in our induction step, we are going to prove that if you assume that this thing is true,
154.533 -> for sum of k.
157.333 -> If we assume that then it is going to be true for sum of k + 1.
162.533 -> And the reason why this is all you have to do to prove this for all positive integers
168.333 -> it's just imagine:
170 -> Let's think about all of the positive integers right over here.
172 -> 1, 2, 3, 4, 5, 6 you could just keep going on forever.
177.467 -> So we are going to prove it for 1.
180.2 -> We are going to prove that this formula right over here,
182.6 -> this expression right over here applies for the case of 1, when n is 1.
187.067 -> 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
192.867 -> So if we know it is true for 1 in our base case then the second step,
196.333 -> this induction step must be true for 2 then.
199.067 -> Because we proved generally if it's true for k it's going to be true for k + 1.
202.867 -> When it's true for 2, then it must be true for 3,
205.733 -> because we have proved it, when it's true for k, it's true for k + 1.
209.6 -> So if it's true for 2 it's true for 3.
211.667 -> and if it's true for 3 it's going to be true for 4.
214.067 -> You can just keep going on and on forever, which means it's true for everything.
217.667 -> Now spoken in generalaties let's actually prove this by induction.
223.533 -> So let's take the sum of, let's do this function on 1.
231.8 -> that is just going to be the sum of all positive integers
234.533 -> including 1 is just literally going to be 1.
236.8 -> We've just added all of them, it is just 1.
238.4 -> There is no other positive integer up to and including 1.
242 -> And now we can prove that this is the same thing as
244.4 -> 1 times 1 plus 1 all of that over 2.
249.6 -> 1 plus 1 is 2, 2 divided by 2 is 1, 1 times 1 is 1.
254.533 -> So this formula right over here, this expression
257.533 -> it worked for 1, so we have proved our base case.
263.267 -> we have proven it for 1.
264.867 -> Now what I want to do is I want to assume that it works for some number k.
271.385 -> So I will assume true for some number k.
281.467 -> So i'm going to assume that for some number k, that this function at k is going to be equal to
288 -> k times k plus 1 over 2.
292.133 -> So I'm just assuming this is true for that.
294.2 -> Now what I want to do is think about what happens when I try to find this function for k + 1.
301.4 -> This is what I'm assuming.
303.133 -> I'm assuming I know this.
305.133 -> Now let's try to do it for k + 1.
307.2 -> So what is the sum of all of the integers up to and including k + 1?
314.323 -> Well this is going to be 1 plus 2 plus 3 plus all the way up to k.
320.8 -> Plus k plus 1.
323.667 -> Right? this is the sum of everything up to and including k plus 1.
326.933 -> Well we are assuming that we know what this already is.
330.333 -> We are assuming that we already have a formula for this.
332.6 -> We are assuming that this is going to simplify to k times k plus 1 over 2.
339.133 -> We are assuming that we know that.
341 -> So we will just take this part and we will add it to k plus 1.
344.733 -> so we'll add it to k plus 1 over here.
350.19 -> And if you find the common denominator, the common denominator is going to be 2.
355.467 -> So this is going to be equal to...
358.667 -> I'll write the part in magenta first.
360.6 -> so this is k times k plus 1 over 2 plus 2 times k plus 1 over 2.
370.667 -> This thing in blue is the same thing as that thing in blue.
373.533 -> The 2's would cancel out, I'd just wrote it this way so I have a common denominator.
376.533 -> So this is going to be equal to...
380.615 -> We have a common denominator of 2 and I'll write this in a different colour here.
385.8 -> So we are going to have k times k plus 1 plus 2 times k plus 1.
392.4 -> Now at this step right over here you can factor out a k plus 1.
396.867 -> Both of these terms are divisible by k + 1.
399.267 -> So let's factor this out.
401 -> So if you factor out a k + 1, you get k plus 1 times
406.4 -> refractoring out over here, if you factor out k + 1 you'd just have a k.
410.867 -> Over here if you factor out k + 1 you would just have a 2.
414.252 -> Let me colour code those.
415.225 -> So you would know what I'm doing.
416.8 -> So this 2 is this 2 right over there and this k is this k right over there.
426.667 -> We factored it out.
428.533 -> These k+1's we factored out is this k+1 over there.
432.533 -> And it's going to be all of this over 2.
437.267 -> Now, we can rewrite this. This is the same thing.
441.533 -> This is equal to.
443.333 -> This is the same thing as k plus 1, that's this part right over here.
451.867 -> Times k plus 1 plus 1.
457.2 -> Right? This is clearly the same thing as k + 2.
459.8 -> All of that over 2.
463.692 -> Why is this interesting to us?
466.141 -> Well we have just proven it.
467.538 -> If we assume that this is true and if we use that assumption we get
476.467 -> that the sum of all positive integers up to and including k + 1 is equal to k + 1 times k + 1 + 1 over
485.769 -> 2.
486.415 -> We are actually showing that the original formula applies to k+1 as well.
493.133 -> If you would take k + 1 and put it in for n you got exactly the result that we got over here.
500.867 -> So we showed , we proved our base case.
504.2 -> This expression worked for the sum for all of positive integers up to and including 1.
509.533 -> And it also works if we assume that it works for everything up to k.
514.867 -> Or if we assume it works for integer k it also works for the integer k plus 1.
519.533 -> And we are done. That is our proof by induction.
522.467 -> That proves to us that it works for all positive integers.
525 -> Why is that?
526.4 -> We have proven it for 1 and we have proven it that if it works for some integer
531.2 -> it will work for the next integer.
536.385 -> So if you assume it worked for 1 then it can work for 2.
539.477 -> Well we have already proven that it works for 1 so we can assume it works for 1.
543.267 -> So it definitely will work for 2.
545.067 -> So we get 2 checked.
546.8 -> But since we can assume it works for 2 we can now assume it works for 3.
550.333 -> Well if it works for 3 well then we have proven it works for 4.
554 -> You see how this induction step is kinda like a domino,
556.6 -> it cascades and we can go on and on forever so it works for all positive integers.
Source: https://www.youtube.com/watch?v=wblW_M_HVQ8