# Partial sums of partial sums

$$s_0[n] = 1, 1, 1, 1, ...$$ $$s_1[n] = \sum_{i=1}^{n}s_0[i]=1,2,3,4,...$$ $$s_2[n] = \sum_{i=1}^{n}s_1[i]=1,3,6,10,...$$ $$s_k[n] = \sum_{i=1}^{n}s_{k-1}[i]$$

can anyone please remind me what the closed form for $s_k[n]$ is?

-

Write out all of the values and then turn them $45^{\circ}$. You'll see Pascal's triangle appear, and it's not hard to prove that this is actually Pascal's triangle. After a little fiddling it follows that the closed form is

$$s_k[n] = {n+k \choose n}$$

(at least if you index your series starting with $0$). The partial sum relation you give is known as the hockey-stick identity and has a fairly straightforward combinatorial proof.

A very general method for finding partial sums is the following: suppose $f_n$ is a sequence whose generating function $$F(x) = \sum_{n \ge 0} f_n x^n$$

you know, and you are interested in the sequence of partial sums $\displaystyle s_n = \sum_{k=0}^n f_k$. Then $$\sum_{n \ge 0} s_n x^n = \frac{F(x)}{1 - x}.$$

See e.g. Wilf's generatingfunctionology for details.

-

$s_k[n]={{n+k}\choose k}$ if you start with $n=0$.

-

Note: $s_k[n] = s_k[n-1] + s_{k-1}[n]$, so this is the same as Pascal's triangle (i.e. $S(k,n) = S(k,n-1) + S(k-1,n)$ ) and so the answer is going to be something like $xCy$. Since $s_0[n] = 1$ and $s_k[0] = 1$, these define the two sides of Pascal's triangle and so we have
$$s_k[n] = (n+k)Ck = (n+k)!/(n!k!).$$

-