# Iterated sums

• Oct 14th 2009, 03:03 PM
Aileys.
Iterated sums
Sorry if this is the wrong forum.

Is there a "nice" formula for the following? :

$\sum_{k_2=0}^{k_1}\sum_{k_3=0}^{k_2}\sum_{k_4=0}^{ k_3} ... \sum_{k_n=0}^{k_{n-1}}1$

I do the first few iterations and it just seems to get messy :S

Thanks for any help
• Oct 14th 2009, 03:38 PM
Plato
Quote:

Originally Posted by Aileys.
Sorry if this is the wrong forum.

Is there a "nice" formula for the following? :

$\sum_{k_2=0}^{k_1}\sum_{k_3=0}^{k_2}\sum_{k_4=0}^{ k_3} ... \sum_{k_n=0}^{k_{n-1}}1$

You are using the same indices more than once.
Do you mean
$\sum_{j_2=0}^{k_1}\sum_{j_3=0}^{k_2}\sum_{j_4=0}^{ k_3} ... \sum_{j_n=0}^{k_{n-1}}1$?

If not how can the indices change like that?
What am I missinng?

Edit
I will say that $\sum_{j_2=0}^{k_1}\sum_{j_3=0}^{k_2}\sum_{j_4=0}^{ k_3} ... \sum_{j_n=0}^{k_{n-1}}1$ $=\prod\limits_{j = 1}^{k_{n - 1} } {\left( {k_j + 1} \right)}$
• Oct 14th 2009, 05:13 PM
Aileys.
Yes the indices are supposed top be like that, - that's why it's messy!

For example $\sum_{k_2=0}^{k_1}\sum_{k_3=0}^{k_2}1 = \sum_{k_2=0}^{k_1}(k_2+1) = \frac{k_1(k_1+1)}{2}-(k_1+1)$

Perhaps I'm abusing notation... if so, sorry! But hopefully that^ explains what I'm trying to do
• Oct 14th 2009, 05:30 PM
awkward
Quote:

Originally Posted by Aileys.
Sorry if this is the wrong forum.

Is there a "nice" formula for the following? :

$\sum_{k_2=0}^{k_1}\sum_{k_3=0}^{k_2}\sum_{k_4=0}^{ k_3} ... \sum_{k_n=0}^{k_{n-1}}1$

I do the first few iterations and it just seems to get messy :S

Thanks for any help

The sum is the same as the number of sequences
$0 \leq k_n \leq k_{n-1} \leq \dots \leq k_2 \leq k_1$,

which is the same as the number of multisets of size $n$ taken from a set of $k_1$ objects,

which is
$\binom{k_1 +n -1}{n}$.