1 00:00:00,025 --> 00:00:09,877 [music] Sometimes, you'll see a Greek restaurant with a name like this. 2 00:00:09,878 --> 00:00:17,385 So, it's g, r, sigma, sigma, K restaurant. And my little rant here is that this does 3 00:00:17,385 --> 00:00:22,788 not say Greek restaurant. It says grssk restaurant. 4 00:00:22,788 --> 00:00:26,016 That sigma is really a letter S. Right? 5 00:00:26,016 --> 00:00:30,632 Sigma makes the s sound. Yeah, so grssk restaurant. 6 00:00:30,632 --> 00:00:36,333 Well, this sigma makes an s sound, right? So, you know, forget this Greek restaurant 7 00:00:36,333 --> 00:00:38,512 story. What's another word that actually does 8 00:00:38,512 --> 00:00:42,460 start with s? Alright, a word that starts with s is Sum. 9 00:00:42,460 --> 00:00:46,550 So, we're going to use that giant sigma for sums. 10 00:00:46,550 --> 00:00:50,174 Let's see an example. So, I'll write a big sigma for sum, and 11 00:00:50,174 --> 00:00:53,546 then below the sigma, I'll write what I want to start at. 12 00:00:53,546 --> 00:00:56,300 Above the sigma, I'll right what I want to end at. 13 00:00:56,300 --> 00:01:01,400 And here's what I want to add up. So, in this example, I first plug in n 14 00:01:01,400 --> 00:01:02,816 equals 1. Right? 15 00:01:02,817 --> 00:01:07,279 And 2 times 1 minus 1 is 1. Then, I plug in n equals 2. 16 00:01:07,279 --> 00:01:12,219 2 times 2 minus 1 is 3. Then, I plug in n equals 3. 17 00:01:12,219 --> 00:01:16,837 2 times 3 minus 1 is 5. Then, I plug in n equals 4. 18 00:01:16,837 --> 00:01:21,799 2 times 4 minus 1 is 7. Then, I plug in n equals 5. 19 00:01:21,799 --> 00:01:27,932 2 times 5 minus 1 is 9. And I keep on doing this, right, until I 20 00:01:27,932 --> 00:01:33,983 plug in n equals 10. Which is 2 times 10 minus 1 which is 19. 21 00:01:33,983 --> 00:01:40,518 So, to evaluate this sum, right, the meaning of these symbols is just to add up 22 00:01:40,518 --> 00:01:44,553 1 plus 3 plus 5 plus 7, and so on, until I get to 19. 23 00:01:44,553 --> 00:01:47,057 We can compute this. Well, here we go. 24 00:01:47,058 --> 00:01:54,397 Alright, 1 plus 3 is 4. 4 plus 5 is 9. 25 00:01:54,398 --> 00:02:04,728 Alright, 9 plus 7 is 16. 16 plus 9 is 25. 26 00:02:04,729 --> 00:02:08,769 25 plus, what's the next number in this list, is 11. 27 00:02:08,769 --> 00:02:14,866 25 plus 11 is 36. 36 plus the next number that would come 28 00:02:14,866 --> 00:02:19,648 after 11 and this is 13. 36 plus 13 is 49. 29 00:02:19,649 --> 00:02:26,412 49 plus, the next number is 15. 49 plus 15 is 64. 30 00:02:26,412 --> 00:02:32,484 64 plus 17 is the next number, right before 19. 31 00:02:32,484 --> 00:02:38,807 64 plus 17 is 81. And 81 plus 19 is 100. 32 00:02:38,807 --> 00:02:42,493 So, yeah. If I add up 1 plus 3 plus 5 plus 7 plus 9 33 00:02:42,493 --> 00:02:48,197 all the way up 19, by just adding up the odd numbers between 1 and 19, I get 100 34 00:02:48,197 --> 00:02:53,309 and that's the value of this sum. If you have some programming experience, 35 00:02:53,309 --> 00:02:58,218 you can think of these sums as like loops. Formally, what does this notation mean, 36 00:02:58,218 --> 00:03:01,594 right? So, I put a big summation symbol, a big 37 00:03:01,594 --> 00:03:04,625 sigma. N goes from a to b, a and b are whole 38 00:03:04,625 --> 00:03:07,091 numbers. And then, I've got some expression 39 00:03:07,091 --> 00:03:09,420 involving n which I can write as a function of n. 40 00:03:09,420 --> 00:03:13,836 And what this notation means is just to plug in all the numbers between a and b, 41 00:03:13,836 --> 00:03:18,045 the whole numbers between a and b including a and b, into this expression, 42 00:03:18,045 --> 00:03:19,773 and then sum them all up. Right? 43 00:03:19,774 --> 00:03:23,611 Giant sigma for sum. You know, so if I wanted to expand this 44 00:03:23,611 --> 00:03:28,923 out, if I want to right out what this is doing, you know, I first plug in a, then I 45 00:03:28,923 --> 00:03:33,820 plug in a plus 1, then I add to that a, whatever I get when I plug in a plus 2, 46 00:03:33,820 --> 00:03:37,104 and then dot, dot, dot, I keep on going, right. 47 00:03:37,104 --> 00:03:41,449 And then, I get closer to the n. Right before the n, I plug in b minus 1. 48 00:03:41,449 --> 00:03:46,363 And then, I finish by plugging in b and I add up all these things and that's the 49 00:03:46,363 --> 00:03:50,090 value of this sum. Alright that's what this notation means. 50 00:03:50,090 --> 00:03:53,707 There's one easy case where we can figure out the whole story. 51 00:03:53,708 --> 00:03:57,000 What happens if we take the sum of just a constant? 52 00:03:57,000 --> 00:04:01,324 Some expression that doesn't depend on the indexing variable at all. 53 00:04:01,325 --> 00:04:06,920 For instance, what is the sum, as n goes from a to b, of just the constant C, 54 00:04:06,920 --> 00:04:10,719 right? This is you know, sort of expression that 55 00:04:10,719 --> 00:04:15,320 doesn't involve n at all. So, to compute this, all we have to know 56 00:04:15,320 --> 00:04:18,615 is how many times C is being added into itself. 57 00:04:18,615 --> 00:04:23,900 Right, so this is C plus C plus, and it keeps on going, you know, plus C. 58 00:04:23,900 --> 00:04:28,337 But the whole issue is just how many times C appears. 59 00:04:28,338 --> 00:04:35,254 And C appears b minus a plus 1 times. That, that plus 1 maybe is a little bit 60 00:04:35,254 --> 00:04:37,980 confusing. But you can see that the plus 1 really 61 00:04:37,980 --> 00:04:42,119 belongs there, if you plug in some specific values for, for b and a. 62 00:04:42,120 --> 00:04:47,285 So, if I add C to itself, b minus a plus 1 times, this sum is really just a 63 00:04:47,285 --> 00:04:51,424 multiplication problem, right. Repeated addition is called 64 00:04:51,424 --> 00:04:56,293 multiplication. It's C times b minus a plus 1. 65 00:04:56,293 --> 00:05:10,386 So, the sum of C as n goes from a to b is just C times b minus a plus 1.