Proving 1! + 2! + ... + k! = a(n) Recursive Series

[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

 

[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)!.

 

[matt grime]

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

 

[gonzo]

Actually, I was looking for the reverse process ... starting with the sum and finding a recursion formula that fits it ... how you could go about doing that.

Odd that the one I provided doesn't work. I didn't bother checking it since I got it from a reference on Math World to the on-line encyclopedia of integer sequences:

http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A033312

 

[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.

 

[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

 

[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).

 

[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)

 

[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.

 

[Muzza]

Your recursion formula contains a factorial, which I want to avoid.

And what if you can't?

 

[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.

 

[Muzza]

You mean this one?

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

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

 

[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)!

 

[gonzo]

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

 

[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.

 

[learningphysics]

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.

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.

 

[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.

 

[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.

 

[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?

 

[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.

 

[gonzo]

I saw this comment on the formula (if that helps):

a(n) gives the index number in any table of permutations of the entry in
which the last n+1 items are reversed. - Eugene McDonnell

Also, there has to be a pretty simple way to derive the formula. Deriving the formula for the sum was posted as an "interesting problem of the month" at a university near me, and these problems always have relatively simple solutions once you see them.

I guess in worst case I'll find out in month from now when the solution is posted, but I was hoping to track down all the pieces myself before then. Oh well.

 

[gonzo]

In case anyone cares, a friend of mine figured it out for me (not using that particular recursion formula, but using recursion techniques). It goes like this:

(k+1)! = (k+1)*k! = k*k! + k!

which leads to the more general case:

(k-n+1)! = (k-n)*(k-n)! + (k-n)!

If we apply this all the way down the line we get:

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

and just rearrange to get the final answer:

(k+1)!-1 = 1*1! + 2*2! + 3*3! + ... + k*k!