Recursive Sums

By Adam Ring on Wednesday, September 26, 2001 - 05:34 pm:

I seem to have found a problem that is similar to

\sum_{i = 1}^{n} n^{r}

where

r

is an arbitrary value. I have found the very helpful threads about this topic along with the discussion that one can find the coefficients using Bernoulli numbers. My problem, however, involves an arbitrary number of recursions.

For example, if we start with $\sum_{i = 1}^{n} 1$ we find that the solution is equal to $n$ . We can then do a recursive sum, $\sum_{j = 1}^{n} \sum_{i = 1}^{j} 1$ . This will then reduce to $\sum_{j = 1}^{n} n$ which then reduces to $n (n + 1) / 2$ . Adding a third sum will amount to

$\sum_{k = 1}^{n} k (k + 1) / 2 = 1 / 2 \sum_{k = 1}^{n} k^{2} + 1 / 2 \sum_{k = 1}^{n} k = 1 / 2 [n (n + 1) (2 n + 1) / 6 + n (n + 1) / 2] = n (n + 1) (n + 2) / 6$

The equation can be specified as $\sum_{j = 1}^{n} \sum_{i = 1}^{j} i^{r - 2}$ where $r$ is an arbitrary number of summations with the first being $\sum_{i = 1}^{n} 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.

By David Loeffler on Thursday, September 27, 2001 - 10:33 pm:

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

By Michael Doré on Friday, September 28, 2001 - 05:49 pm:

Alternatively, you can write:

$\sum_{i_{k} = 1}^{n} \sum_{i_{k - 1} = 1}^{i_{k}} \dots \sum_{i_{1} = 1}^{i_{2}} 1$

as $\sum_{i_{k} = 1}^{n} \sum_{i_{k - 1} = 1}^{n} \sum_{i_{1} = 1}^{n} I (i_{1} \leq i_{2} \leq \dots \leq i_{k})$

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_{1}, \dots, i_{k})$ where each $i_{r}$ is an integer in $[1, n]$ , and $i_{1} \leq \dots \leq i_{k}$ .

Letting $j_{r} = i_{r} + r$ it is clear that the answer is the number of ordered $k$ -tuples of integers $(j_{1}, \dots, j_{k})$ such that $j_{r}$ is in $[1 + r, n + r]$ and $j_{1} < j_{2} < \dots < 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:

$\sum_{i_{k} = 1}^{n} \sum_{i_{k - 1} = 1}^{i_{k}} \dots \sum_{i_{1} = 1}^{i_{2}} 1 = n (n + 1) \dots (n + k - 1) / k!$

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

By Adam Ring on Friday, September 28, 2001 - 11:39 pm:

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

n^{k} + C (n, 1) n^{(k - 1)} + C (n, 2) n^{(k - 2)} + \dots + C (n, n - 1) n = C (n, 1) S_{(k - 1)} + C (n, 2) S_{(k - 2)} + \dots + C (n, n - 1) S_{1} + n

where $C (k, i)$ is the binomial coefficient and $S_{r} = \sum_{i = 1}^{n} i^{r}$ . From there, I was able to iterate through the various recursive sums with $S R_{k + 1}$ equal to $\sum_{i^{k + 1} = 1}^{n} S R_{k}$ , 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.

By Michael Doré on Saturday, September 29, 2001 - 02:15 pm:

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

$S = \sum_{i_{k} = 1}^{n} \sum_{i_{k - 1} = 1}^{i_{k}} \dots \sum_{i_{1} = 1}^{i_{2}} 1$

where $n$ , $k$ are fixed natural numbers.

We can write this as:

$S = \sum_{j_{k} = k + 1}^{n + k} \sum_{j_{k - 1} = k}^{j_{k} - 1} \dots \sum_{j_{1} = 2}^{j_{2} - 1} 1$

where $j_{r} = i_{r} + r$

Let $A$ be the set of all ordered $k$ -tuples $(j_{1}, \dots, 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_{1}$ is in $[2, j_{2} - 1]$ . In other words $j_{r}$ is in $[r + 1, j_{r + 1} - 1]$ if $1 \leq r < k$ .

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

For instance one element of $B$ would be ${2, 3, 4, 5, \dots, k, k + 1}$ . Note that this is not different from ${3, 2, 4, 5, \dots, 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_{1}, \dots, j_{k})$ such that $2 \leq j_{1} \leq j_{2} + 1$ , $3 \leq j_{2} \leq j_{3} + 1$ , ..., $k \leq j_{k - 1} \leq j_{k} + 1$ and $k + 1 \leq j_{k} \leq 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_{1}, \dots, j_{k})$ in $A$ and map it to the subset ${j_{1}, \dots, 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_{1}, \dots, j_{k})$ in $A$ have $j_{1} < \dots < 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_{1}, \dots, j_{k})$ in $A$ such that $R = {j_{1}, \dots, j_{k}}$ . Well define $j_{1}$ to be the smallest element of $R$ , $j_{2}$ to be the second smallest element of $R$ , ... and $j_{k}$ to be the largest element in $R$ . Then since $2 \leq j_{1} < j_{2} < \dots < j_{k - 1} < j_{k} \leq n + k$ and $j_{r}$ are integers so $r + 1 \leq j_{r}$ . It is clear that $j_{r} \leq j_{r + 1} - 1$ if $r < k - 1$ and it is also obvious that $j_{k} \leq n + r$ . Hence $(j_{1}, \dots, 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, \dots, n + k}$ so by definition of the binomial coefficient, $| B | = C (n + k - 1, k)$ . So $S = n (n + 1) \dots (n + k - 1) / k!$

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

$n (n + 1) \dots (n + k - 1) / k! = n (n + 1) \dots (n + k) / (k + 1)! - (n - 1) n \dots (n + k - 1) / (k + 1)!$

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

$\sum_{n = 1}^{N} n (n + 1) \dots (n + k - 1) / k! = N (N + 1) \dots (N + k) / (k + 1)!$

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

$\sum_{n = 1}^{N} 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 $\sum_{r = 1}^{n} r^{s}$ . One interesting thingthat could come out of your approach though might besome interesting identities concerning theBernoulli numbers. I'll have another look later.

By Adam Ring on Monday, October 01, 2001 - 04:33 pm:

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.

The answer to where I got the first equation in my previous post was from

\sum_{k = 1}^{n} [(k + 1)^{r} - k^{r}]

. This can be expanded two ways. The first is a telescoping series that reduces to

(n+1)^r - 1 = n^r + C(r,1)n^r-1 + ... + C(r,r-1)n

and the second expansion is

\sum_{k = 1}^{n} [C (r, 1) k^{r - 1} + \dots + C (r, r - 1) k + 1] = C (r, 1) S_{r - 1} + \dots + C (r, r - 1) S_{1} + S_{0}

where $S_{j} = \sum_{k = 1}^{n} k^{j}$ , which of course means $S_{0} = n$ , $S_{1} = n (n + 1) / 2$ , $S_{2} \dots$
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.