3
$\begingroup$

$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?

3 Answers 3

7

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.

0

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

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!).$