For example, if we start with

n å i=1

1

we find that the solution is equal to n. We can then do a recursive sum,

n å j=1

j å i=1

1

. This will then reduce to

n å j=1

n

which then reduces to n(n+1)/2. Adding a third sum will amount to

n å k=1

k(k+1)/2=1/2

n å k=1

k2+1/2

n å k=1

k=1/2[n(n+1)(2n+1)/6 +n(n+1)/2]=n(n+1)(n+2)/6

The equation can be specified as

n å j=1

j å i=1

ir-2

where r is an arbitrary number of summations with the first being

n å i=1

1

. As it turns out, r is also the order of the algebraic answer as well.

Right now I know two ways that this can be solved with a given r. The first is to build up the equations like I showed above for the case r=3.

The second way would seem to involve plugging r into the equation above and use whatever method one could use to find a formula for a sum. Depending on r, this seems the more difficult of the two.

Anyway, is there a method for solving this problem that is similar (or dissimilar) to the arbitrary power of sums problem that has already been discussed? I'm assuming that the solution would have a similar form with the coefficients being determined by a sequence similar to the Bernoulli sequence. Thanks for the help.

Have you tried writing out Pascal's triangle? You may find it illuminating. I'll not give you any clearer hints yet - see what you find. If you get stuck write back.

David

Alternatively, you can write:

n å ik=1

ik å ik-1=1

¼

i2 å i1=1

1

as

n å ik=1

n å ik-1=1

n å i1=1

I(i1 £ i2 £ ¼ £ ik)

where I is the indicator function. (In other words I(X)=1 if X is true and I(X)=0 if X is false.)

Therefore the k-fold sum is equal to the number of ordered k-tuples (i₁,¼,i_k) where each i_r is an integer in [1,n], and i₁ £ ¼ £ i_k.

Letting j_r=i_r+r it is clear that the answer is the number of ordered k-tuples of integers (j₁,¼,j_k) such that j_r is in [1+r,n+r] and j₁ < j₂ < ¼ < j_k. A bit of thought shows this is the number of unordered k-tuples of distinct integers in [2,n+k] (can you see a bijection between the two sets?) This of course is equal to the binomial coefficient C(n+k-1,k). Therefore:

n å ik=1

ik å ik-1=1

¼

i2 å i1=1

1=n(n+1)¼ (n+k-1)/k!

Alternatively you can get this answer in one line by induction on k.

I must apologize for being obtuse, but I didn't understand that proof at all. I did try to use:

where C(k,i) is the binomial coefficient and

Sr=

n å i=1

ir

. From there, I was able to iterate through the various recursive sums with S R_k+1 equal to

n å ik+1=1

S Rk

, which could be written in terms of the various S_r sums. (Clarification, S_r is the sum of i^r while S R_k is the recursive sum carried out k times of 1). This obviously got me nowhere since I had to keep track of both the i^r sums and the recursive sums. I believe this method could be described as an exercise in futility.
The basic thing is that I don't understand how to start the proof. I didn't understand what Michael was saying about the indicator function. My mind immediately jumped to boolean logic with the zeros and ones, and from there it wouldn't let go. Thanks for the help.

Yes, it was a bit rushed. Here is another way of writing out the proof. We want to evaluate:

S=

n å ik=1

ik å ik-1=1

¼

i2 å i1=1

1

where n, k are fixed natural numbers.

We can write this as:

S=

n+k å jk=k+1

jk-1 å jk-1=k

¼

j2-1 å j1=2

1

where j_r=i_r+r

Let A be the set of all ordered k-tuples (j₁,¼,j_k) of integers such that j_k is in [k+1,n+k], j_k-1 is in [k,j_k-1], j_k-2 is in [k-1,j_k-1-1], ..., j₁ is in [2,j₂-1]. In other words j_r is in [r+1,j_r+1-1] if 1 £ r < k.

Let B be the set of all subsets R of {2,¼,n+k} such that |R|=k.

For instance one element of B would be {2,3,4,5,¼,k,k+1}. Note that this is not different from {3,2,4,5,¼,k,k+1} - they are the same subset.

We claim that S=|A|. (|A| means the number of elements in A.) It is easy to see why this is true. The k-iterated sum S counts ''one'' for every (j₁,¼,j_k) such that 2 £ j₁ £ j₂+1, 3 £ j₂ £ j₃+1, ..., k £ j_k-1 £ j_k+1 and k+1 £ j_k £ n+k. So S counts one for every element of A, in other words S=|A|.

We now claim that |A|=|B|. We do this by giving a bijection from A to B. The bijection is a very simple one: we take an ordered k-tuple (j₁,¼, j_k) in A and map it to the subset {j₁,¼,j_k}. Note that this subset is in B. It has k distinct elements (since j_r is strictly increasing) and it is clear that each element is in [2,n+k]. To show it is a bijection we must show it is:

(i) injective

(ii) surjective

(i) is clear. If two ordered k-tuples in A map to the sameelement of B then they must be the same k-tuple (since all k-tuples(j₁,¼,j_k) in A have j₁ < ¼ < j_k).

(ii) We have to show that for every subset R of[2,n+k] of size k, we can find an ordered k-tuple (j₁,¼,j_k) in A such that R={j₁,¼,j_k}. Well define j₁ to be the smallest element of R, j₂ to be the second smallest element of R, ... and j_k to be the largest element in R. Then since 2 £ j₁ < j₂ < ¼ < j_k-1 < j_k £ n+k and j_r are integers so r+1 £ j_r. It is clear that j_r £ j_r+1-1 if r < k-1 and it is also obvious that j_k £ n+r. Hence (j₁,¼,j_k) is indeed in A and the bijection isestablished.

Therefore S=|A|=|B|. But B is the set of k-sized subsets of {2,¼, n+k} so by definition of the binomial coefficient, |B|=C(n+k-1,k). So S=n(n+1)¼(n+k-1)/k!

Alternatively, you can prove the result much quicker by noting that:

n(n+1)¼(n+k-1)/k!=n(n+1)¼(n+k)/(k+1)!-(n-1)n¼(n+k-1)/(k+1)!

Summing this from n=1to n=N gives:

N å n=1

n(n+1)¼(n+k-1)/k!=N(N+1)¼(N+k)/(k+1)!

So if S(n,k)=n(n+1)¼(n+k-1)/k! then:

N å n=1

S(n,k)=S(N,k+1)

It is now easy to iterate this, to get the answer. This is practically the same as David's method.

As for your method I'm a bit confused about where your first equation comes from. It is going to be hard to get the required result by expanding and using the result for

n å r=1

rs

. One interesting thingthat could come out of your approach though might besome interesting identities concerning theBernoulli numbers. I'll have another look later.

I thank you for the explination. It is now much clearer. One of the problems that I faced was that my focus is in engineering, not math. The proof makes sense now, but I did need some time to wrap my brain around the problem.

where

Sj=

n å k=1

kj

, which of course means S₀=n, S₁=n(n+1)/2, S₂¼
Set the two lines equal to each other, and it should be what I typed previously.

There may be some link between the Bernoulli numbers and the binomial coefficients, but exactly what that is, I haven't got a clue.

Thanks for all your help.