# K*k! question

1. Dec 10, 2004

### gonzo

Can someone explain how to prove/derive the following (sorry I don't know how to input math symbols):

1*1! + 2*2! + .... + k*k!

is equal to the recursive series:

a(n) = a(n-1)*(n-1) + a(n-1) + n-1

2. Dec 10, 2004

### Muzza

I take it that you want to show that a(n) = 1*1! + 2*2! + ... + n*n! is the ("closed form") solution of the recursion

{ a(n) = a(n-1)*(n-1) + a(n-1) + n-1,
{ a(1) = 1.

But that's not true. If k = 2, 1*1! + 2*2! + .... + k*k! evaluates to 1 + 2*2! = 5, but using the recursion formula, we get

a(2) = a(1)*(1) + a(1) + 2-1 = 1 + 1 + 2 - 1 = 3.

However, a(n) = 1*1! + 2*2! + .... + n*n! is the solution to

{ a(n + 1) = a(n) + (n + 1)(n + 1)!,
{ a(1) = 1.

It's easily proved with induction. It's true for n = 1. Suppose it's true for n = k, then

a(k + 1) = a(k) + (k + 1)(k + 1)! = 1*1! + 2*2! + .... + k*k! + (k + 1)(k + 1)!.

Last edited: Dec 10, 2004
3. Dec 10, 2004

### matt grime

And the sum to k.k! is (k+1)! - 1, if you're interested

4. Dec 10, 2004

### gonzo

5. Dec 10, 2004

### gonzo

Thanks, Matt, but yes, I already saw that on Math World. I was trying to understand all the steps in arriving at that solution, and from the references it seemed to be derived from the recursion formula (I assume using standard solution techniques for recursion formulas). I was looking for the missing step on going from the sum to the recursion formula so I could understand the whole process more completely.

6. Dec 10, 2004

### gonzo

I just looked over the formula a little closer, and realized it does work, it is just "off by one" in the index a(n) = sum up to n-1 not n and then it works, so that

a(0)=0 and a(1)=0 and a(2)=1 and a(3)=5 and so on

7. Dec 10, 2004

### Muzza

Well, if a(n) = 1*1! + ... + k*k!, then a(n + 1) = 1*1! + ... + k*k! + (k + 1)(k + 1)! = a(n) + (k + 1)(k + 1)!. It's all about recognizing things.

Another example, take a(n) = 2^n. Then a(n + 1) = 2^(n + 1) = 2 * 2^n = 2 * a(n).

8. Dec 10, 2004

### matt grime

If you know the a(n) is a sum , a good starting point is just to consider the difference a(n)-a(n-1)

9. Dec 10, 2004

### gonzo

I tried that first Matt, but I didn't get very far. I ended up with something like:

a(n)=a(n-1) + (a(n-1)-a(n-2))*n/(n-1)

Which is a mess ... but it did get rid of the factorials at least. It didn't seem to lead anywhere though. The straight subtraction you suggest leads to just n*n!, which doesn't seem to help either in getting final formula, at least not that I can see (which is why I'm asking for help).

And Muzza, I'm still looking for the original formula now that I know it is correct with the right indexing. Your recursion formula contains a factorial, which I want to avoid.

10. Dec 10, 2004

### Muzza

And what if you can't?

11. Dec 10, 2004

### gonzo

But the other formula I gave doesn't have a factorial, so I can. So I'm trying to understand how to arrive at that formula starting with the sum.

12. Dec 10, 2004

### Muzza

You mean this one?

It doesn't work (try n = 3).

13. Dec 10, 2004

### gonzo

No, I mean the first one I gave, which I already pointed out uses a slightly different indexing.

{ a(n) = a(n-1)*(n-1) + a(n-1) + n-1,
{ a(0) = 0

which should give the sum to (n-1)*(n-1)!

14. Dec 10, 2004

### gonzo

and I had a typo in the other one anyway ... it shoudl be n^2/(n-1) at the end

15. Dec 14, 2004

### gonzo

Matt, I was wondering if you could help me out with this a little bit more. I was playing around with the recursion formulae trying to reverse engineer it, but all I ended up with was the final formula of (k+1)! - 1 for the total sum.

I tried what you said and considered a(n)-a(n-1), but couldn't find a way to get rid of the factorial without creating a second order recursion formulae as I mentioned above.

I just can't see how they derived that relatively simple one with no factorials in it for the sum.

16. Dec 14, 2004

### learningphysics

Well, I used the result Matt gave:
the sum to (n-1) of k!*k = n!-1

So a(n)=n!-1

a(n+1)=(n+1)!-1= (n+1)n!-1=(n+1)(n!-1)+(n+1)-1=(n+1)a(n)+n

This is your series, where a(0)=0.

17. Dec 15, 2004

### gonzo

Yes, but the point was that I want to know how that result was derived. That's my main goal, to understand how the formula for the sum is derived. As far as I can tell, it was derived from that recursion formula, so I now am trying to understand how that formula was derived. It can't be derived from the result it was used to prove.

18. Dec 15, 2004

### matt grime

Perhaps you'll have to accept that the result was just guessed (it's not unusual) and that there isn't a larger reason. Perhaps someone just worked out the first few terms and saw the pattern and tried to prove it and lo and behold it worked. Or maybe it came up in some cobinatorial way and the two expressions are different ways of counting the same things. That's probably more likely as it at least offers an explanation of why write it down in the first place.

19. Dec 15, 2004

### gonzo

I guess that's the best I can do without digging up the orginal paper on it. Do you know any other proofs for the (k+1)!-1 formula?

20. Dec 15, 2004

### matt grime

Off the top of my head, no. I doubt there are any papers on it, it's just a nice formula, and not too hard to show. You could try thinking of ways that r.r! might arise in counting things.