# Alternating series of compositions of triangular numbers

I'm modeling a process which involves a subset $S$ of a large number $n_A$ of objects - call them balls. Each time I add a ball to $S$, it may dislodge another ball with probability proportional to the fraction of the total balls already in $S$.

I've gotten as far as this expression for the expected number of balls $n_k$ after $k$ additions, and I'm hoping someone might show me how to find a closed form expression for this series, or at least some bounds:

$$\langle n_{k}\rangle=k- \frac{1}{n_{A}}\sum_{a=1}^{k-1}1+ \frac{1}{{n_{A}}^2}\sum_{a=1}^{k-2}\sum_{b=1}^{a}1- \frac{1}{{n_{A}}^3}\sum_{a=1}^{k-3}\sum_{b=1}^{a}\sum_{c=1}^{b}1+ \frac{1}{{n_{A}}^4}\sum_{a=1}^{k-4}\sum_{b=1}^{a}\sum_{c=1}^{b}\sum_{d=1}^{c}1-...$$

• Nested sums all using the same index $i$? – Martin R Apr 26 '16 at 13:07
• Edited, thanks. – JHD Apr 26 '16 at 13:21

Note that $$\sum_{a=1}^{k-4}\sum_{b=1}^{a}\sum_{c=1}^{b}\sum_{d=1}^{c}1= \sum_{a=1}^{k-4}\sum_{b=1}^{a}\sum_{c=1}^{b}\binom c1=\sum_{a=1}^{k-4}\sum_{b=1}^{a}\binom {b+1}2=\sum_{a=1}^{k-4}\binom {a+2}3=\binom {k-1}4$$ and so on.
Hence \begin{align} \langle n_k\rangle &=k- \frac{1}{n_{A}}\sum_{a=1}^{k-1}1+ \frac{1}{{n_{A}}^2}\sum_{a=1}^{k-2}\sum_{b=1}^{a}1- \frac{1}{{n_{A}}^3}\sum_{a=1}^{k-3}\sum_{b=1}^{a}\sum_{c=1}^{b}1+ \frac{1}{{n_{A}}^4}\sum_{a=1}^{k-4}\sum_{b=1}^{a}\sum_{c=1}^{b}\sum_{d=1}^{c}1-...\\ & =k-\frac 1{n_A}\binom {k-1}1+\frac 1{n_A^2}\binom {k-1}2-\frac 1{n_A^3}\binom{k-1}3+\frac 1{n_A^4}\binom {k-1}4-\cdots\\ &=\sum_{r=0}^\infty \binom {k-1}r\left(- \frac 1{n_A}\right)^r\\ &=\sum_{r=0}^{k-1} \binom {k-1}r\left(- \frac 1{n_A}\right)^r \qquad\qquad\text{as } \binom {k-1}r=0 \text { for }r>k-1\\ &=\left(1-\frac1{n_A} \right)^{k-1}\qquad\blacksquare \end{align}
$$\langle n_{k}\rangle=\sum_{r=0}^{k-1} {(-1)^r \frac 1{n_A^r}\binom {k}r}$$
• You're welcome!. FYI the binomial coeff shown in your solution above should be $\binom {k-1}r$ instead of $\binom kr$. – hypergeometric Apr 27 '16 at 2:15