# Iterated sums

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

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

$\displaystyle \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, 02:38 PM
Plato
Quote:

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

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

$\displaystyle \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
$\displaystyle \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 $\displaystyle \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$$\displaystyle =\prod\limits_{j = 1}^{k_{n - 1} } {\left( {k_j + 1} \right)}$
• Oct 14th 2009, 04:13 PM
Aileys.
Yes the indices are supposed top be like that, - that's why it's messy!

For example $\displaystyle \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, 04:30 PM
awkward
Quote:

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

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

$\displaystyle \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
$\displaystyle 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 $\displaystyle n$ taken from a set of $\displaystyle k_1$ objects,

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