Hello everyone, so in this video we're going to talk about finding a closed form expression for a value,
and we're going to prove it's true by induction for all n.
So this expression, j times j factorial,
looks pretty complicated.
And it is, it's going to be tough to compute these by hand, but we're going to do our best and
hope that we can succeed.
Okay, so the way to
start off is you have to play around with this sum.
If you don't understand really what it is, then it's going to be very
tough to prove by induction that this works, okay?
I'm also going to go through this sort of
giving you an idea of what really induction is and how it's really…
or how it's really used.
So first, let's start playing around with things.
So let's evaluate this when n equals 1,
and let's see what we get. So we're going to get…
So for n equals 1 - well okay this isn't really mysterious.
We're going to get exactly 1, right? It's going to be - there's only one term in this summation.
Okay, so here when we plug in n equals 1, we're going to get
the sum from 1 to 1. Well it's only one term,
right, namely the 1 term. So it's 1 times 1 factorial, and that's equal to 1.
Okay so let's do this now for n equals 2,
and let's see what we get. So for n equals 2, we get
it'll be the sum of two terms,
and that is equal to…
okay so for n equals 2, what are we going to get?
Well so again it’s - oops, wrong order.
The sum is not from 2 to 1, it's from 1 to 2.
Let's fix that up.
So the sum from 1 to 2 of j times j factorial,
well it's 1 times 1 factorial plus 2 times 2 factorial.
2 factorial is 2, 2 times 2 is 4,
the other term we already computed was 1, 1 plus 4 is 5.
Well let's do it for n equals 3.
so we're going to get 1 times 1 factorial, plus 2 times 2 factorial, plus 3 times 3 factorial.
1 plus 4 plus… well 3 times 3 factorial.
3 factorial is 6, 6 times 3 should be 18.
18, 4, and 1 that's 23.
Okay I don't see the pattern yet, so I'm going to go with another one.
So for n equals 4…
so 4 -
starting to get a little bit crowded, but that's okay.
I'm going to get 4 cdot 24,
and what's that going to be?
So 1 plus 5 plus 18, plus 4 times 24,
and that's going to be equal to…
1 plus 4 plus 18 we already know was 23, plus
plus 4 times 24 should be 96, should be
119, I hope.
So now I'm looking, 1, 5, 23, 119.
I still don't really see the pattern yet, so I'm going to do
one more case.
I'm going to cry a little bit while doing it but that's okay, let's do it.
And let's see it, n equals 5.
So the n equals 5 case so,
1 times 1 factorial, plus 2 times 2 factorial, plus 3 times 3 factorial,
plus 4 times 4 factorial, plus 5 times 5 factorial.
Now again notice that we've already computed the first four, right?
This is kind of how induction works, by the way right,
so you're using the previous information, so the fact that we had the first four,
and we said the first four was 119,
right, so…let's change this to 119
plus 5 cdot 120.
Right, because that's 5 times 5 factorial, 5 factorial is 120
and so if we do this arithmetic, we should get
a big number, let's see.
5 times 120 is 600
so we’re going to get…
719? Did I do this right?
Let's hope I did this right.
That actually looks correct, okay.
Alright, now after we've done 5 cases, there's got to be a pattern here.
So let's try to find it, okay?
There's a lot of numbers on the page but there's some that start to look
really familiar, right? So 119
was over here, right, 119 over here and there's this 120 over here, right,
and if you look back here, there was this 23 over here,
and this 96 which came from 24,
right, and 24 remember is 4 factorial.
So the 23 here is 4 factorial minus 1,
the 119 here well that's 5 factorial, 120, minus 1,
719 well 6 factorial happens to be 720,
and 720 minus 1 is 719. So
this gives a pretty good indication as to what the pattern should be.
So the claim is now that this sum
should be equal to n plus 1 factorial minus 1.
This one's not so easy to see that this was the case,
but
hopefully you notice that the numbers started to repeat,
and they were true before as well, but because I skipped steps
it's not hard to see. Remember 18 was 6
times 3, right, and 6 minus 1 is 5, right?
But okay, so now we have our claim. So now we can at least
attempt to get through the proof.
Now how is this going to work? So let's look at some of these cases, right?
I want to show you - let me show you the 5 to 6
example. So I know it's true for n equals 5, now I'm going to show you
how to get from n equals 6…
or how to get to n equals 6 from n equals 5.
So I'm going to call this an aside.
I'm going to - the reason why I'm doing this is I want to show you
sort of why induction works in a very concrete example.
So to get form, no. Let's just try to get from,
n equals 5 to n equals 6, let's try it.
To get from n equals 5 to n equals 6,
what are we going to do? Well remember from before, right, we were taking the first
three terms, and we had already computed those, so we grouped those together.
Here in the 5 step, we grouped the first four terms together
because we computed that in the n equals 4 case.
In the n equals 6 case, well we're going to group the first
five terms together because we've already computed that.
Now in doing that, you have this extra term.
So you have this extra term that comes out. So we’re grouping the first five terms together
and the sixth term is being pulled off, okay?
The first five terms we already know, right?
We said that that was
6 factorial
minus 1.
So these - this
sum of the first five terms was equal to 6 factorial minus 1, remember 719, right?
That's what that was, and now you have
plus 6 times 6 factorial. Well if I group the 6 factorials together,
right then I have one 6 factorial plus six 6 factorials,
so either by factoring or just
noticing that 6 factorial is just some number,
we are getting 7 times 6 factorial
minus 1.
Well 7 times 6 factorial minus 1, well 7 times 6 that's
just - 7 times 6 factorial that's just, by definition, 7 factorial.
Okay? And that's how we can show from n equals 5 to n equals 6, okay?
So that's pretty much the idea here,
right? Now this is basically the induction step
except I did it just from 5 to 6. Now you can do this in
general, and that's what we're going to do to sort of finish up our proof, okay?
So I'm going to do this
again just using induction because we only needed the one previous step to do this,
and I'm probably going to start this on a new page just so that it's a little bit clearer.
Alright so this is our claim that this sum is equal to this value.
Solution, let P at n
be the statement that…
so let P of n be the given statement.
We prove P at n
is true for all n in [natural numbers]
by Mathematical Induction.
Okay, so now let's do the base cases and stuff.
Well we've already done the base case, so I guess I'm just going to copy it down
When n equals 1, well we already did that. We plugged it in,
that's equal to 1, and if we look at the right-hand side
it's going to be the same as 1 plus 1 factorial minus 1.
1 plus 1 factorial is 2 and 2 minus 1 is 1.
So left-hand side equals the right-hand side so we're good in the base case.
Induction hypothesis,
so now what are we assuming? We're going to assume that
P k is true for some k in [natural numbers].
That is, we assume that…
So that we assume that
this is true.
Now maybe I’ll make a note of this since I'm in the middle of this proof,
some people ask me, “Well can I do this for k minus 1 and show it's true for k?”
And you can, but you have to be careful of where your k lives, right?
So the reason why we do this for k and k plus 1 is because
usually we're proving something is true for all natural numbers n
and it's just easier to write that k is a natural number.
Okay, so this is our induction hypothesis.
I put a period so that I’m not being too, too sloppy,
and now we need to do the induction step.
Now suppose that
n equals k plus 1,
okay, so now what we're doing
is we're going to show that this is true for k plus 1. We need
to show that…
what do we need to show?
So we need to show
that this sum
so j equals 1 to k plus 1 is equal to,
well I'm going to plug in k plus 1 to the right so let me just
reword this like this. k plus 2 factorial minus 1, okay?
To do this, we start with the summation
and see that…
what we're going to do? So we're going to take this…
okay so this is our goal and we need to use the induction hypothesis, right?
So let's start with this sum and I'm going to scroll up now.
Just like what we did for the 5 to 6 case, we're going to do the same thing, right?
So remember what we did from the 5 to 6 case, right, we had sum up to 6,
we split off the terms up to 5, we used
the fact that we knew what the sum up to 5 was,
grouped, rearranged,
right? This step here would be the induction hypothesis step.
So let's try to do this now with variables, okay?
This is equal to…
so the sum of to k plus k plus 1,
k plus 1 factorial.
That's just breaking off the term,
now we use the induction hypothesis. So this thing we knew was
k plus 1 factorial minus 1, that's
right here. So we know that sum is the induction hypothesis for that,
plus k plus 1, k plus 1 factorial.
So there we go, now this was the induction hypothesis, right?
Again just replace that sum with the induction hypothesis.
Now we're going to group the last two terms,
so we have k plus 1 k factorials, and one more k factorial, so you going to have
k plus 2 k factorials.
You know what, I'll do it a different way this time.
I'm just going to rearrange the terms and then factor
just that you can see it in a different way.
So I'm going to rearrange the terms
defined by commutativity of addition.
Rearrange the terms,
factor out the k plus 1 factorial,
that's k plus 2, I'm going to rearrange the terms and simplify,
and that's k plus 2 factorial
minus 1. That's exactly what I wanted to show.
Hence, P at k plus 1
is true,
hence
P n is true
for all n in
the natural numbers by Mathematical Induction.
And again Mathematical Induction should probably be capitalized
since it is a theorem name, so let's capitalize it.
Okay.
So hence P k plus 1 is true, hence
P n is true for all natural numbers n by Mathematical Induction.
This last sentence is really important, right, just because
I mean this is the Principle of Mathematical Induction you're using, so you really need to
write it down and invoke it, okay?
And that's basically it. So hopefully this gives you an idea
of what happens -
or how to find a closed form and then how to prove it, okay?
There's a lot going on in this video, again I apologize for its length but
this is really just one problem.
Again once you get better at this, this will become faster
and this needs to be as automatic as possible.
Induction is sort of this “follow your nose” sort of thing, right,
You have your little formula and you basically just follow it.
Previous cases imply the next cases suggest that you should be using Mathematical Induction.
Again thank you for listening. I hope this video helps
get you started, and
yeah have a - good luck.