1 00:00:00,000 --> 00:00:04,966 Hello everyone, so in this video we're going to talk 
about finding a closed form expression for a value, 2 00:00:04,966 --> 00:00:08,000 and we're going to prove 
it's true by induction for all n. 3 00:00:08,000 --> 00:00:09,100 4 00:00:09,100 --> 00:00:11,733 So this expression, j times j factorial, 5 00:00:11,733 --> 00:00:14,000 looks pretty complicated. 6 00:00:14,000 --> 00:00:15,433 7 00:00:15,433 --> 00:00:20,000 And it is, it's going to be tough to compute these 
by hand, but we're going to do our best and 8 00:00:20,000 --> 00:00:21,933 hope that we can succeed. 9 00:00:21,933 --> 00:00:23,433 10 00:00:23,433 --> 00:00:26,100 Okay, so the way to 11 00:00:26,100 --> 00:00:28,666 start off is you have to play around with this sum. 12 00:00:28,666 --> 00:00:31,200 If you don't understand really 
what it is, then it's going to be very 13 00:00:31,200 --> 00:00:33,766 tough to prove by induction 
that this works, okay? 14 00:00:33,766 --> 00:00:35,800 15 00:00:35,800 --> 00:00:38,433 I'm also going to go through this sort of 16 00:00:38,433 --> 00:00:42,466 giving you an idea of what really 
induction is and how it's really… 17 00:00:42,466 --> 00:00:44,600 or how it's really used. 18 00:00:44,600 --> 00:00:46,466 19 00:00:46,466 --> 00:00:49,300 So first, let's start playing around with things. 20 00:00:49,300 --> 00:00:52,000 So let's evaluate this when n equals 1, 21 00:00:52,000 --> 00:00:55,100 and let's see what we get. 
So we're going to get… 22 00:00:55,100 --> 00:00:59,200 23 00:00:59,200 --> 00:01:02,733 So for n equals 1 - well okay 
this isn't really mysterious. 24 00:01:02,733 --> 00:01:05,366 25 00:01:05,366 --> 00:01:10,233 We're going to get exactly 1, right? It's going to 
be - there's only one term in this summation. 26 00:01:10,233 --> 00:01:11,233 27 00:01:11,233 --> 00:01:13,400 Okay, so here when we plug in 
n equals 1, we're going to get 28 00:01:13,400 --> 00:01:15,500 the sum from 1 to 1. Well it's only one term, 29 00:01:15,500 --> 00:01:19,466 right, namely the 1 term. So it's 1 
times 1 factorial, and that's equal to 1. 30 00:01:19,466 --> 00:01:24,100 31 00:01:24,100 --> 00:01:26,866 Okay so let's do this now for n equals 2, 32 00:01:26,866 --> 00:01:28,833 33 00:01:28,833 --> 00:01:32,800 and let's see what we get. 
So for n equals 2, we get 34 00:01:32,800 --> 00:01:35,333 it'll be the sum of two terms, 35 00:01:35,333 --> 00:01:40,200 36 00:01:40,200 --> 00:01:43,300 and that is equal to… 37 00:01:43,300 --> 00:01:44,000 38 00:01:44,000 --> 00:01:46,733 okay so for n equals 2, 
what are we going to get? 39 00:01:46,733 --> 00:01:48,433 40 00:01:48,433 --> 00:01:52,100 Well so again it’s - oops, wrong order. 41 00:01:52,100 --> 00:01:54,600 The sum is not from 2 to 1, it's from 1 to 2. 42 00:01:54,600 --> 00:01:57,033 43 00:01:57,033 --> 00:01:58,800 Let's fix that up. 44 00:01:58,800 --> 00:02:00,966 So the sum from 1 to 2 of j times j factorial, 45 00:02:00,966 --> 00:02:03,866 well it's 1 times 1 factorial 
plus 2 times 2 factorial. 46 00:02:03,866 --> 00:02:05,766 2 factorial is 2, 
2 times 2 is 4, 47 00:02:05,766 --> 00:02:08,433 the other term we already 
computed was 1, 1 plus 4 is 5. 48 00:02:08,433 --> 00:02:11,133 49 00:02:11,133 --> 00:02:13,700 50 00:02:13,700 --> 00:02:16,133 Well let's do it for n equals 3. 51 00:02:16,133 --> 00:02:16,266 52 00:02:16,266 --> 00:02:16,700 53 00:02:16,700 --> 00:02:21,566 so we're going to get 1 times 1 factorial, plus 
2 times 2 factorial, plus 3 times 3 factorial. 54 00:02:21,566 --> 00:02:24,700 1 plus 4 plus… well 3 times 3 factorial. 55 00:02:24,700 --> 00:02:28,300 3 factorial is 6, 6 times 3 should be 18. 56 00:02:28,300 --> 00:02:31,633 18, 4, and 1 that's 23. 57 00:02:31,633 --> 00:02:32,200 58 00:02:32,200 --> 00:02:36,700 Okay I don't see the pattern yet, so I'm going to go with another one. 59 00:02:36,700 --> 00:02:39,800 60 00:02:39,800 --> 00:02:41,266 61 00:02:41,266 --> 00:02:43,766 So for n equals 4… 62 00:02:43,766 --> 00:02:44,366 63 00:02:44,366 --> 00:02:46,800 so 4 - 64 00:02:46,800 --> 00:02:50,366 starting to get a little bit crowded, but that's okay. 65 00:02:50,366 --> 00:02:51,066 66 00:02:51,066 --> 00:02:54,533 I'm going to get 4 cdot 24, 67 00:02:54,533 --> 00:02:56,200 68 00:02:56,200 --> 00:02:58,366 and what's that going to be? 69 00:02:58,366 --> 00:02:58,833 70 00:02:58,833 --> 00:02:59,200 71 00:02:59,200 --> 00:03:02,466 So 1 plus 5 plus 18, plus 4 times 24, 72 00:03:02,466 --> 00:03:05,066 73 00:03:05,066 --> 00:03:07,900 and that's going to be equal to… 74 00:03:07,900 --> 00:03:11,600 1 plus 4 plus 18 we already 
know was 23, plus 75 00:03:11,600 --> 00:03:12,900 76 00:03:12,900 --> 00:03:17,366 plus 4 times 24 should be 96, should be 77 00:03:17,366 --> 00:03:19,566 119, I hope. 78 00:03:19,566 --> 00:03:24,633 79 00:03:24,633 --> 00:03:30,300 So now I'm looking, 1, 5, 23, 119. 80 00:03:30,300 --> 00:03:33,466 81 00:03:33,466 --> 00:03:38,466 I still don't really see the pattern yet, so I'm going to do 82 00:03:38,466 --> 00:03:40,833 one more case. 83 00:03:40,833 --> 00:03:44,666 I'm going to cry a little bit while doing it but that's okay, let's do it. 84 00:03:44,666 --> 00:03:45,700 85 00:03:45,700 --> 00:03:45,733 86 00:03:45,733 --> 00:03:48,066 And let's see it, n equals 5. 87 00:03:48,066 --> 00:03:49,333 88 00:03:49,333 --> 00:03:51,500 So the n equals 5 case so, 89 00:03:51,500 --> 00:03:54,333 1 times 1 factorial, plus 2 times 
2 factorial, plus 3 times 3 factorial, 90 00:03:54,333 --> 00:03:57,633 plus 4 times 4 factorial, 
plus 5 times 5 factorial. 91 00:03:57,633 --> 00:04:00,733 Now again notice that we've already 
computed the first four, right? 92 00:04:00,733 --> 00:04:03,266 This is kind of how induction works, by the way right, 93 00:04:03,266 --> 00:04:07,833 so you're using the previous information, 
so the fact that we had the first four, 94 00:04:07,833 --> 00:04:10,400 and we said the first four was 119, 95 00:04:10,400 --> 00:04:14,366 right, so…let's change this to 119 96 00:04:14,366 --> 00:04:18,400 plus 5 cdot 120. 97 00:04:18,400 --> 00:04:22,133 98 00:04:22,133 --> 00:04:25,300 Right, because that's 5 times 
5 factorial, 5 factorial is 120 99 00:04:25,300 --> 00:04:29,866 and so if we do this 
arithmetic, we should get 100 00:04:29,866 --> 00:04:30,866 101 00:04:30,866 --> 00:04:33,566 a big number, let's see. 102 00:04:33,566 --> 00:04:35,833 5 times 120 is 600 103 00:04:35,833 --> 00:04:38,366 so we’re going to get… 104 00:04:38,366 --> 00:04:41,866 105 00:04:41,866 --> 00:04:44,166 719? Did I do this right? 106 00:04:44,166 --> 00:04:46,333 Let's hope I did this right. 107 00:04:46,333 --> 00:04:48,333 108 00:04:48,333 --> 00:04:51,033 That actually looks correct, okay. 109 00:04:51,033 --> 00:04:51,700 110 00:04:51,700 --> 00:04:51,933 111 00:04:51,933 --> 00:04:56,233 Alright, now after we've done 5 cases, 
there's got to be a pattern here. 112 00:04:56,233 --> 00:04:58,600 So let's try to find it, okay? 113 00:04:58,600 --> 00:04:59,466 114 00:04:59,466 --> 00:05:03,000 There's a lot of numbers on the page 
but there's some that start to look 115 00:05:03,000 --> 00:05:05,700 really familiar, right? So 119 116 00:05:05,700 --> 00:05:06,633 117 00:05:06,633 --> 00:05:10,033 was over here, right, 119 over here 
and there's this 120 over here, right, 118 00:05:10,033 --> 00:05:13,500 and if you look back here, 
there was this 23 over here, 119 00:05:13,500 --> 00:05:16,200 and this 96 which came from 24, 120 00:05:16,200 --> 00:05:18,866 right, and 24 remember is 4 factorial. 121 00:05:18,866 --> 00:05:22,466 So the 23 here is 4 factorial minus 1, 122 00:05:22,466 --> 00:05:23,666 123 00:05:23,666 --> 00:05:28,500 the 119 here well that's 
5 factorial, 120, minus 1, 124 00:05:28,500 --> 00:05:32,400 719 well 6 factorial happens to be 720, 125 00:05:32,400 --> 00:05:35,266 and 720 minus 1 is 719. So 126 00:05:35,266 --> 00:05:39,733 this gives a pretty good indication 
as to what the pattern should be. 127 00:05:39,733 --> 00:05:41,933 128 00:05:41,933 --> 00:05:45,100 So the claim is now that this sum 129 00:05:45,100 --> 00:05:49,500 130 00:05:49,500 --> 00:05:53,466 should be equal to n 
plus 1 factorial minus 1. 131 00:05:53,466 --> 00:05:58,100 132 00:05:58,100 --> 00:06:01,833 This one's not so easy to 
see that this was the case, 133 00:06:01,833 --> 00:06:04,366 134 00:06:04,366 --> 00:06:05,866 but 135 00:06:05,866 --> 00:06:08,700 hopefully you notice that the 
numbers started to repeat, 136 00:06:08,700 --> 00:06:11,933 and they were true before as well, 
but because I skipped steps 137 00:06:11,933 --> 00:06:14,433 it's not hard to see. 
Remember 18 was 6 138 00:06:14,433 --> 00:06:17,366 times 3, right, and 6 minus 1 is 5, right? 139 00:06:17,366 --> 00:06:21,366 140 00:06:21,366 --> 00:06:24,500 But okay, so now we have our 
claim. So now we can at least 141 00:06:24,500 --> 00:06:27,500 attempt to get through the proof. 142 00:06:27,500 --> 00:06:30,366 143 00:06:30,366 --> 00:06:34,800 Now how is this going to work? So let's 
look at some of these cases, right? 144 00:06:34,800 --> 00:06:37,166 145 00:06:37,166 --> 00:06:40,500 I want to show you - let 
me show you the 5 to 6 146 00:06:40,500 --> 00:06:45,400 example. So I know it's true for n 
equals 5, now I'm going to show you 147 00:06:45,400 --> 00:06:47,733 how to get from n equals 6… 148 00:06:47,733 --> 00:06:49,066 149 00:06:49,066 --> 00:06:52,200 or how to get to n equals 
6 from n equals 5. 150 00:06:52,200 --> 00:06:54,200 So I'm going to call this an aside. 151 00:06:54,200 --> 00:06:55,233 152 00:06:55,233 --> 00:06:55,500 153 00:06:55,500 --> 00:06:59,466 I'm going to - the reason why I'm 
doing this is I want to show you 154 00:06:59,466 --> 00:07:03,766 sort of why induction works 
in a very concrete example. 155 00:07:03,766 --> 00:07:07,133 So to get form, no. Let's just try to get from, 156 00:07:07,133 --> 00:07:10,066 n equals 5 to n equals 6, let's try it. 157 00:07:10,066 --> 00:07:10,633 158 00:07:10,633 --> 00:07:10,866 159 00:07:10,866 --> 00:07:13,866 To get from n equals 5 to n equals 6, 160 00:07:13,866 --> 00:07:17,366 what are we going to do? Well remember 
from before, right, we were taking the first 161 00:07:17,366 --> 00:07:20,900 three terms, and we had already computed those, so we grouped those together. 162 00:07:20,900 --> 00:07:23,533 Here in the 5 step, we grouped 
the first four terms together 163 00:07:23,533 --> 00:07:25,900 because we computed that 
in the n equals 4 case. 164 00:07:25,900 --> 00:07:28,566 In the n equals 6 case, well 
we're going to group the first 165 00:07:28,566 --> 00:07:31,900 five terms together because 
we've already computed that. 166 00:07:31,900 --> 00:07:34,400 167 00:07:34,400 --> 00:07:37,133 Now in doing that, you 
have this extra term. 168 00:07:37,133 --> 00:07:40,766 169 00:07:40,766 --> 00:07:44,333 So you have this extra term that comes out. 
So we’re grouping the first five terms together 170 00:07:44,333 --> 00:07:46,866 and the sixth term is being pulled off, okay? 171 00:07:46,866 --> 00:07:50,166 The first five terms we already know, right? 172 00:07:50,166 --> 00:07:52,533 We said that that was 173 00:07:52,533 --> 00:07:54,300 174 00:07:54,300 --> 00:07:56,733 6 factorial 175 00:07:56,733 --> 00:07:58,666 minus 1. 176 00:07:58,666 --> 00:07:59,233 177 00:07:59,233 --> 00:07:59,866 178 00:07:59,866 --> 00:08:01,866 So these - this 179 00:08:01,866 --> 00:08:06,766 sum of the first five terms was equal to 
6 factorial minus 1, remember 719, right? 180 00:08:06,766 --> 00:08:09,100 That's what that was, and now you have 181 00:08:09,100 --> 00:08:13,100 plus 6 times 6 factorial. Well if 
I group the 6 factorials together, 182 00:08:13,100 --> 00:08:17,100 right then I have one 6 
factorial plus six 6 factorials, 183 00:08:17,100 --> 00:08:17,866 184 00:08:17,866 --> 00:08:19,900 so either by factoring or just 185 00:08:19,900 --> 00:08:23,333 noticing that 6 factorial is just some number, 186 00:08:23,333 --> 00:08:26,700 187 00:08:26,700 --> 00:08:29,900 we are getting 7 times 6 factorial 188 00:08:29,900 --> 00:08:32,433 189 00:08:32,433 --> 00:08:34,766 minus 1. 190 00:08:34,766 --> 00:08:37,800 Well 7 times 6 factorial minus 1, well 7 times 6 that's 191 00:08:37,800 --> 00:08:41,100 just - 7 times 6 factorial that's 
just, by definition, 7 factorial. 192 00:08:41,100 --> 00:08:45,100 193 00:08:45,100 --> 00:08:46,400 194 00:08:46,400 --> 00:08:51,266 Okay? And that's how we can show 
from n equals 5 to n equals 6, okay? 195 00:08:51,266 --> 00:08:54,033 196 00:08:54,033 --> 00:08:57,033 So that's pretty much the idea here, 197 00:08:57,033 --> 00:08:59,066 right? Now this is basically the induction step 198 00:08:59,066 --> 00:09:01,333 except I did it just from 5 to 
6. Now you can do this in 199 00:09:01,333 --> 00:09:04,733 general, and that's what we're going to 
do to sort of finish up our proof, okay? 200 00:09:04,733 --> 00:09:06,400 201 00:09:06,400 --> 00:09:08,133 So I'm going to do this 202 00:09:08,133 --> 00:09:12,700 again just using induction because we only 
needed the one previous step to do this, 203 00:09:12,700 --> 00:09:16,933 and I'm probably going to start this on a 
new page just so that it's a little bit clearer. 204 00:09:16,933 --> 00:09:17,133 205 00:09:17,133 --> 00:09:21,066 Alright so this is our claim that
this sum is equal to this value. 206 00:09:21,066 --> 00:09:21,733 207 00:09:21,733 --> 00:09:25,000 Solution, let P at n 208 00:09:25,000 --> 00:09:29,133 be the statement that… 209 00:09:29,133 --> 00:09:31,766 so let P of n be the given statement. 210 00:09:31,766 --> 00:09:36,633 211 00:09:36,633 --> 00:09:40,066 We prove P at n 212 00:09:40,066 --> 00:09:43,766 is true for all n in [natural numbers] 213 00:09:43,766 --> 00:09:46,300 214 00:09:46,300 --> 00:09:50,366 by Mathematical Induction. 215 00:09:50,366 --> 00:09:51,066 216 00:09:51,066 --> 00:09:51,300 217 00:09:51,300 --> 00:09:54,933 Okay, so now let's do 
the base cases and stuff. 218 00:09:54,933 --> 00:09:57,066 219 00:09:57,066 --> 00:10:00,633 Well we've already done the base case, 
so I guess I'm just going to copy it down 220 00:10:00,633 --> 00:10:01,333 221 00:10:01,333 --> 00:10:04,366 When n equals 1, well we already 
did that. We plugged it in, 222 00:10:04,366 --> 00:10:08,300 that's equal to 1, and if we 
look at the right-hand side 223 00:10:08,300 --> 00:10:09,100 224 00:10:09,100 --> 00:10:14,066 it's going to be the same as 
1 plus 1 factorial minus 1. 225 00:10:14,066 --> 00:10:19,233 226 00:10:19,233 --> 00:10:22,100 1 plus 1 factorial is 2 
and 2 minus 1 is 1. 227 00:10:22,100 --> 00:10:25,666 So left-hand side equals the right-hand 
side so we're good in the base case. 228 00:10:25,666 --> 00:10:26,633 229 00:10:26,633 --> 00:10:27,133 230 00:10:27,133 --> 00:10:29,566 Induction hypothesis, 231 00:10:29,566 --> 00:10:33,000 so now what are we assuming? 
We're going to assume that 232 00:10:33,000 --> 00:10:39,700 P k is true for some k in [natural numbers]. 233 00:10:39,700 --> 00:10:42,966 That is, we assume that… 234 00:10:42,966 --> 00:10:43,333 235 00:10:43,333 --> 00:10:43,700 236 00:10:43,700 --> 00:10:46,333 So that we assume that 237 00:10:46,333 --> 00:10:48,500 238 00:10:48,500 --> 00:10:50,300 this is true. 239 00:10:50,300 --> 00:10:52,666 240 00:10:52,666 --> 00:10:54,800 Now maybe I’ll make a note of this 
since I'm in the middle of this proof, 241 00:10:54,800 --> 00:11:00,133 some people ask me, “Well can I do this 
for k minus 1 and show it's true for k?” 242 00:11:00,133 --> 00:11:02,733 And you can, but you have to be 
careful of where your k lives, right? 243 00:11:02,733 --> 00:11:05,100 So the reason why we do this 
for k and k plus 1 is because 244 00:11:05,100 --> 00:11:07,900 usually we're proving something 
is true for all natural numbers n 245 00:11:07,900 --> 00:11:10,766 and it's just easier to write 
that k is a natural number. 246 00:11:10,766 --> 00:11:14,733 247 00:11:14,733 --> 00:11:17,733 Okay, so this is our induction hypothesis. 248 00:11:17,733 --> 00:11:20,600 I put a period so that I’m 
not being too, too sloppy, 249 00:11:20,600 --> 00:11:21,366 250 00:11:21,366 --> 00:11:24,133 and now we need to 
do the induction step. 251 00:11:24,133 --> 00:11:24,466 252 00:11:24,466 --> 00:11:27,700 Now suppose that 253 00:11:27,700 --> 00:11:29,400 254 00:11:29,400 --> 00:11:32,166 n equals k plus 1, 255 00:11:32,166 --> 00:11:34,400 okay, so now what we're doing 256 00:11:34,400 --> 00:11:39,533 is we're going to show that this 
is true for k plus 1. We need 257 00:11:39,533 --> 00:11:41,933 to show that… 258 00:11:41,933 --> 00:11:44,066 259 00:11:44,066 --> 00:11:46,666 what do we need to show? 260 00:11:46,666 --> 00:11:47,200 261 00:11:47,200 --> 00:11:48,900 So we need to show 262 00:11:48,900 --> 00:11:50,900 263 00:11:50,900 --> 00:11:52,900 that this sum 264 00:11:52,900 --> 00:11:55,200 so j equals 1 to k plus 1 is equal to, 265 00:11:55,200 --> 00:11:57,866 well I'm going to plug in k plus 
1 to the right so let me just 266 00:11:57,866 --> 00:11:59,266 267 00:11:59,266 --> 00:12:03,600 reword this like this. k plus 
2 factorial minus 1, okay? 268 00:12:03,600 --> 00:12:04,333 269 00:12:04,333 --> 00:12:05,066 270 00:12:05,066 --> 00:12:09,733 To do this, we start with the summation 271 00:12:09,733 --> 00:12:11,800 and see that… 272 00:12:11,800 --> 00:12:17,266 273 00:12:17,266 --> 00:12:20,100 what we're going to do? 
So we're going to take this… 274 00:12:20,100 --> 00:12:25,733 275 00:12:25,733 --> 00:12:28,933 okay so this is our goal and we need to use the induction hypothesis, right? 276 00:12:28,933 --> 00:12:32,533 So let's start with this sum 
and I'm going to scroll up now. 277 00:12:32,533 --> 00:12:37,133 Just like what we did for the 5 to 6 case, 
we're going to do the same thing, right? 278 00:12:37,133 --> 00:12:40,566 So remember what we did from the 5 
to 6 case, right, we had sum up to 6, 279 00:12:40,566 --> 00:12:43,666 we split off the terms up to 5, we used 280 00:12:43,666 --> 00:12:46,200 the fact that we knew 
what the sum up to 5 was, 281 00:12:46,200 --> 00:12:49,100 grouped, rearranged, 282 00:12:49,100 --> 00:12:49,766 283 00:12:49,766 --> 00:12:53,733 right? This step here would be 
the induction hypothesis step. 284 00:12:53,733 --> 00:12:55,100 285 00:12:55,100 --> 00:12:57,733 So let's try to do this 
now with variables, okay? 286 00:12:57,733 --> 00:12:58,466 287 00:12:58,466 --> 00:13:00,566 This is equal to… 288 00:13:00,566 --> 00:13:04,266 289 00:13:04,266 --> 00:13:08,766 so the sum of to k plus k plus 1, 290 00:13:08,766 --> 00:13:11,233 k plus 1 factorial. 291 00:13:11,233 --> 00:13:12,333 292 00:13:12,333 --> 00:13:14,233 That's just breaking off the term, 293 00:13:14,233 --> 00:13:18,700 now we use the induction hypothesis. 
So this thing we knew was 294 00:13:18,700 --> 00:13:22,166 k plus 1 factorial minus 1, that's 295 00:13:22,166 --> 00:13:23,533 296 00:13:23,533 --> 00:13:27,233 right here. So we know that sum is 
the induction hypothesis for that, 297 00:13:27,233 --> 00:13:28,333 298 00:13:28,333 --> 00:13:32,300 plus k plus 1, k plus 1 factorial. 299 00:13:32,300 --> 00:13:32,566 300 00:13:32,566 --> 00:13:32,866 301 00:13:32,866 --> 00:13:35,766 So there we go, now this was the induction hypothesis, right? 302 00:13:35,766 --> 00:13:38,333 Again just replace that sum 
with the induction hypothesis. 303 00:13:38,333 --> 00:13:41,133 Now we're going to group the last two terms, 304 00:13:41,133 --> 00:13:44,700 so we have k plus 1 k factorials, and one 
more k factorial, so you going to have 305 00:13:44,700 --> 00:13:46,800 k plus 2 k factorials. 306 00:13:46,800 --> 00:13:48,133 307 00:13:48,133 --> 00:13:50,100 You know what, I'll do it a 
different way this time. 308 00:13:50,100 --> 00:13:53,066 I'm just going to rearrange 
the terms and then factor 309 00:13:53,066 --> 00:13:55,133 just that you can see it in a different way. 310 00:13:55,133 --> 00:13:56,900 311 00:13:56,900 --> 00:13:59,666 So I'm going to rearrange the terms 312 00:13:59,666 --> 00:14:01,866 defined by commutativity of addition. 313 00:14:01,866 --> 00:14:02,166 314 00:14:02,166 --> 00:14:04,100 315 00:14:04,100 --> 00:14:06,100 Rearrange the terms, 316 00:14:06,100 --> 00:14:08,333 factor out the k plus 1 factorial, 317 00:14:08,333 --> 00:14:11,500 that's k plus 2, I'm going to 
rearrange the terms and simplify, 318 00:14:11,500 --> 00:14:13,333 and that's k plus 2 factorial 319 00:14:13,333 --> 00:14:15,866 minus 1. That's exactly 
what I wanted to show. 320 00:14:15,866 --> 00:14:17,033 321 00:14:17,033 --> 00:14:19,933 Hence, P at k plus 1 322 00:14:19,933 --> 00:14:21,666 323 00:14:21,666 --> 00:14:24,233 is true, 324 00:14:24,233 --> 00:14:26,666 hence 325 00:14:26,666 --> 00:14:29,300 P n is true 326 00:14:29,300 --> 00:14:31,500 for all n in 327 00:14:31,500 --> 00:14:37,400 the natural numbers by 
Mathematical Induction. 328 00:14:37,400 --> 00:14:39,000 329 00:14:39,000 --> 00:14:41,600 And again Mathematical Induction 
should probably be capitalized 330 00:14:41,600 --> 00:14:44,500 since it is a theorem name, 
so let's capitalize it. 331 00:14:44,500 --> 00:14:45,600 332 00:14:45,600 --> 00:14:47,366 Okay. 333 00:14:47,366 --> 00:14:49,633 So hence P k plus 1 is true, hence 334 00:14:49,633 --> 00:14:52,800 P n is true for all natural numbers 
n by Mathematical Induction. 335 00:14:52,800 --> 00:14:55,433 This last sentence is really 
important, right, just because 336 00:14:55,433 --> 00:14:58,700 I mean this is the Principle of Mathematical 
Induction you're using, so you really need to 337 00:14:58,700 --> 00:15:00,933 write it down and invoke it, okay? 338 00:15:00,933 --> 00:15:03,633 339 00:15:03,633 --> 00:15:07,333 And that's basically it. So 
hopefully this gives you an idea 340 00:15:07,333 --> 00:15:08,233 341 00:15:08,233 --> 00:15:09,966 of what happens - 342 00:15:09,966 --> 00:15:12,766 or how to find a closed form and 
then how to prove it, okay? 343 00:15:12,766 --> 00:15:14,533 344 00:15:14,533 --> 00:15:18,533 There's a lot going on in this video, again I apologize for its length but 345 00:15:18,533 --> 00:15:20,900 this is really just one problem. 346 00:15:20,900 --> 00:15:25,133 Again once you get better at 
this, this will become faster 347 00:15:25,133 --> 00:15:29,166 and this needs to be as automatic as possible. 348 00:15:29,166 --> 00:15:33,300 Induction is sort of this “follow your nose” sort of thing, right, 349 00:15:33,300 --> 00:15:36,833 You have your little formula 
and you basically just follow it. 350 00:15:36,833 --> 00:15:41,166 Previous cases imply the next cases suggest that 
you should be using Mathematical Induction. 351 00:15:41,166 --> 00:15:42,333 352 00:15:42,333 --> 00:15:44,800 Again thank you for listening. 
I hope this video helps 353 00:15:44,800 --> 00:15:47,900 get you started, and 354 00:15:47,900 --> 00:15:50,300 yeah have a - good luck.