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$.
Find a closed form expression for
$$\sum_{j=1}^n j \cdot j!$$and prove it is true by induction for all $n\in\mathbb{N}$
So this expression, $\displaystyle\sum_{j=1}^n j \cdot j!$, 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 used.
So first, let's start playing around with things. So let's evaluate this when $n=1$, and let's see what we get.
$$n=1:\sum_{j=1}^n j\cdot j!=\sum_{j=1}^1 j\cdot j!=1\cdot 1!=1$$Okay so let's do this now for $n=2$, and let's see what we get.
$$n=2: \sum_{j=1}^n j\cdot j!=\sum_{j=1}^2 j\cdot j!=1\cdot 1!+2\cdot 2!=1+4=5$$Well let's do it for $n=3$.
$$n=3: \sum_{j=1}^n j\cdot j!=\sum_{j=1}^3 j\cdot j!=1\cdot 1!+2\cdot 2!+3\cdot 3!=1+4+18=23$$Okay I don't see the pattern yet, so I'm going to go with another one.
$n=4:$
$$\begin{align*} \sum_{j=1}^n j\cdot j!&=\sum_{j=1}^4 j\cdot j!=1\cdot 1!+2\cdot 2!+3\cdot 3!+4\cdot 4!\\ &=1+4+18+4\cdot 4!=23+96=119 \end{align*}$$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.
$n=5:$
$$\begin{align*} \sum_{j=1}^n j\cdot j!&=\sum_{j=1}^5 j\cdot j!=1\cdot 1!+2\cdot 2!+3\cdot 3!+4\cdot 4!+5\cdot 5!\\ &=1+4+18+96+5\cdot 5!=119+5\cdot 120=719 \end{align*}$$Now again notice that we've already computed the first $4$, 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 sum of the first $4$, and we said the first $4$ was $119$.
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 was the sum when $n=4$, and there's this $120$ in the sum when $n=5$ because $5!=120$. If you look back at $n=3$, we have that it equals $23$, and if you look at $n=4$, we have a $24$ there because it is $4!$. So the $23$ from $n=3$ is $4!-1$, the $119$ from $n=4$ is $5!-1$, the $719$ from $n=5$ well $6!=720$, and $720-1=719$. So this gives a pretty good indication as to what the pattern should be.
Claim: $\displaystyle\sum_{j=1}^n j\cdot j!=(n+1)!-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. 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? Let me show you the $n=5$ to $n=6$ example. So I know it's true for $n=5$, now I'm going to show you how to get to $n=6$ from $n=5$.
So I'm going to call this an aside. The reason why I'm doing this is I want to show you sort of why induction works in a very concrete example.
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 $n=5$ step, we grouped the first four terms together because we computed that in the $n=4$ case. In the $n=6$ case, well we're going to group the first five terms together because we've already computed that.
$$\begin{align*} \sum_{j=1}^n j\cdot j!&=\sum_{j=1}^6 j\cdot j!\\ &=\sum_{j=1}^5 j\cdot j!+6\cdot 6! \end{align*}$$Now in doing that, 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. The first five terms we already know, right? We said that that was $6!-1$
$$\begin{align*} \sum_{j=1}^n j\cdot j!&=\sum_{j=1}^6 j\cdot j!\\ &=\sum_{j=1}^5 j\cdot j!+6\cdot 6!\\ &=6!-1+6\cdot 6!\\ &=7\cdot 6!-1\\ &=7!-1 \end{align*}$$That's how we can show from $n=5$ to $n=6$. 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. So what am I doing? Alright so this is our claim: $\displaystyle\sum_{j=1}^n j\cdot j!=(n-1)!-1$.
Solution: Let $P(n)$ be the statement that
$$\displaystyle\sum_{j=1}^n j\cdot j!=(n+1)!-1$$We prove $P(n)$ is true for all $n\in\mathbb{N}$ by Mathematical Induction.
So now let's do the base cases. Well we've already done the base case, right?
When $n=1$,
$$\sum_{j=1}^n j\cdot j!=\sum_{j=1}^1 j\cdot j!=1\cdot 1!=1=(1+1)!-1$$So left-hand side equals the right-hand side so we're good in the base case.
Assume that $P(k)$ is true for some $k\in\mathbb{N}$. That is, we assume that $\displaystyle\sum_{j=1}^k j\cdot j!=(k+1)!-1$
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-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+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.
Now we need to do the induction step. Suppose that $n=k+1$. We need to show that:
$$\sum_{j=1}^{k+1} j\cdot j!=((k+1)+1)!-1=(k+2)!-1$$So that is our goal and we need to use the induction hypothesis, right? 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 use the fact that we knew what the sum up to $5$ was, grouped, rearranged. The third step we did would be the induction hypothesis step.
So let's try to do this now with variables.
$$\begin{align*} \sum_{j=1}^{k+1} j\cdot j!&=\sum_{j=1}^{k} j\cdot j!+(k+1)(k+1)!\\ &=(k+1)!-1+(k+1)(k+1)!&&\text{Induction Hypothesis}\\ &=(k+1)!+(k+1)(k+1)-1!\\ &=(k+1)!(1+k+1)-1\\ &=(k+2)(k+1)!-1\\ &=(k+2)!-1 \end{align*}$$That's exactly what I wanted to show.
Hence, $P(k+1)$ is true. Hence $P(n)$ is true for all $n\in\mathbb{N}$ by Mathematical Induction.$\quad\blacksquare$
This last sentence is really important, right, 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 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, good luck.