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

  • Thread starter gonzo
  • Start date
  • Tags
    Series
In summary, the conversation is about trying to understand the process of deriving a formula for a recursive series. The initial formula proposed is incorrect, but a different formula is found to be the solution. The conversation then focuses on trying to reverse engineer the formula and understand how it was derived. Ultimately, it is suggested that the formula may have been guessed or discovered through combinatorial reasoning.
  • #1
gonzo
277
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
  • #2
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:
  • #3
And the sum to k.k! is (k+1)! - 1, if you're interested
 
  • #4
  • #5
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
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
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
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
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!
 

1. What is a recursive series?

A recursive series is a mathematical sequence where each term is defined by the previous terms. This means that the value of a term is dependent on the value of the previous term, and so on.

2. How do you prove that 1! + 2! + ... + k! = a(n) in a recursive series?

To prove this, you can use mathematical induction. First, show that the equation holds for a base case, typically when k = 1. Then, assume that the equation holds for some value of k, and use this assumption to prove that it also holds for k + 1. This will show that the equation holds for all values of k.

3. What is the significance of proving a recursive series?

Proving a recursive series can provide a deeper understanding of the underlying mathematical principles involved. It can also help verify the accuracy of the equation and its application in various mathematical problems.

4. Can you provide an example of a recursive series?

One example of a recursive series is the Fibonacci sequence, where each term is the sum of the two previous terms (starting with 0 and 1). So, the sequence would go 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.

5. Are there any real-life applications of recursive series?

Yes, recursive series can be found in various fields such as computer science, physics, and economics. For example, in computer programming, recursive algorithms are used to solve problems by breaking them down into smaller sub-problems. In physics, the Law of Gravitation is a recursive series as it involves the sum of gravitational forces between two bodies.

Similar threads

Insights Reduction of Order For Recursions
    • General Math
Replies
4
Views
2K
I Prove series identity (Alternating reciprocal factorial sum)
    • General Math
Replies
4
Views
1K
I Infinite Series of Infinite Series
    • General Math
Replies
7
Views
1K
I Alternating Harmonic Numbers are cool, spread the word!
    • General Math
Replies
4
Views
405
B Can We Simplify the Taylor Series Expansion for e^(f(x,y))?
    • General Math
Replies
3
Views
700
B Is this method of estimating Pi too similar to Archimedes' method?
    • General Math
Replies
13
Views
1K
I Is this a proof of the Collatz Conjecture?
    • General Math
Replies
8
Views
2K
B Popularizing a property for n-bonacci numbers without publishing it?
    • General Math
Replies
12
Views
939
A Limit of ##i^\frac{1}{n}## as ##n \to \infty##
    • General Math
Replies
14
Views
1K
I Trig Manipulations I'm Not Getting
    • General Math
Replies
1
Views
256

Hot Threads

Recent Insights

Back
Top