Iterated sums

**Aileys.** · October 14th 2009, 02:03 PM

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

**Plato** · October 14th 2009, 02:38 PM

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)}$

**Aileys.** · October 14th 2009, 04:13 PM

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

**awkward** · October 14th 2009, 04:30 PM

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}$ .

Thread: Iterated sums

LinkBack

Thread Tools

Display

Iterated sums

Similar Math Help Forum Discussions

Iterated sup

Iterated integrals

iterated integral

Iterated Integrals

iterated integrals

Search Tags