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

  • Context: Undergrad 
  • Thread starter Thread starter gonzo
  • Start date Start date
  • Tags Tags
    Series
Click For Summary

Discussion Overview

The discussion revolves around proving the relationship between the sum of factorials, specifically the expression 1*1! + 2*2! + ... + k*k!, and a recursive series defined by a(n) = a(n-1)*(n-1) + a(n-1) + n-1. Participants explore various approaches to derive a recursion formula from the sum and examine the validity of different proposed formulas.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant seeks to prove that 1*1! + 2*2! + ... + k*k! equals a recursive series.
  • Another participant argues that the proposed recursion does not hold for k=2, providing counterexamples.
  • Some participants suggest that a(n) = 1*1! + 2*2! + ... + n*n! is a solution to a different recursion involving a(n + 1) = a(n) + (n + 1)(n + 1)!.
  • There is mention of a closed form for the sum, specifically that it equals (k+1)! - 1.
  • Participants discuss the challenge of deriving a recursion formula from the sum without introducing factorials.
  • One participant reflects on the possibility that the result may have been guessed or derived from observing patterns in initial terms.
  • A later reply outlines a method to derive the sum formula through recursive techniques, leading to the conclusion that (k+1)! - 1 equals the sum of the factorials.

Areas of Agreement / Disagreement

Participants express differing views on the validity of the proposed recursion formulas and the methods to derive them. There is no consensus on a single approach or formula, and multiple competing views remain throughout the discussion.

Contextual Notes

Some participants note that the recursion formulas may be "off by one" in their indexing, which affects their validity. There are also unresolved mathematical steps and assumptions regarding the derivation of the formulas.

Who May Find This Useful

This discussion may be of interest to those studying combinatorial mathematics, recursion, and factorials, as well as individuals looking to understand the derivation of recursive relationships from summations.

gonzo
Messages
277
Reaction score
0
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
 
Mathematics news on Phys.org
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:
And the sum to k.k! is (k+1)! - 1, if you're interested
 
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.
 
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
 
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).
 
If you know the a(n) is a sum , a good starting point is just to consider the difference a(n)-a(n-1)
 
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
Your recursion formula contains a factorial, which I want to avoid.

And what if you can't?
 
  • #11
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
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).
 
  • #13
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
and I had a typo in the other one anyway ... it shoudl be n^2/(n-1) at the end
 
  • #15
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
gonzo said:
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.
 
  • #17
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
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
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
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.
 
  • #21
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.
 
  • #22
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!
 

Similar threads

Insights Reduction of Order For Recursions
  • · Replies 4 ·
Replies
4
Views
3K
Graduate Is this Recursive Pattern in the Collatz Sequence Known?
  • · Replies 3 ·
Replies
3
Views
1K
Graduate Proving Goldbach's conjecture by induction (or why it doesn't seem to work)
  • · Replies 10 ·
Replies
10
Views
3K
High School Is this method of estimating Pi too similar to Archimedes' method?
  • · Replies 13 ·
Replies
13
Views
2K
Undergrad Alternating Harmonic Numbers are cool, spread the word!
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Is this a proof of the Collatz Conjecture?
  • · Replies 8 ·
Replies
8
Views
3K
High School Popularizing a property for n-bonacci numbers without publishing it?
  • · Replies 12 ·
Replies
12
Views
2K
High School How to prove this for every Arithmetic Progression?
  • · Replies 12 ·
Replies
12
Views
2K
Undergrad [ASK] Mathematical Induction: Prove 7^n-2^n is divisible by 5.
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Trig Manipulations I'm Not Getting
  • · Replies 1 ·
Replies
1
Views
2K