Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.