# General formula for iterated cumulative sum

Consider the sequence $$S_0$$ consisting of ones:

$$1,1,1,1,1,1,\ldots$$

Now compute the cumulative sum of this sequence, and call the resulting sequence $$S_1$$:

$$1,2,3,4,5,6,\ldots$$

Proceed iteratively to generate sequence $$S_2$$:

$$1,3,6,10,15,21,\ldots$$

then $$S_3$$:

$$1,4,10,20,35,56,\ldots$$

and so on.

It is well known that each sequence $$S_k$$ can be represented by a $$k$$-degree polynomial $$P_k(n)$$. For the above sequences the polynomials are $$P_0(n) = 1$$ $$P_1(n) = n$$ $$P_2(n) = \frac{n^2+n}{2}$$ $$P_3(n) = \frac{n^3+3n^2+2n}{6}$$

My question: Is there a general formula for coefficients of the polynomial $$P_k$$? Or more generally, is there a formula to compute $$S_k(n)$$ as a function of $$n$$ and $$k$$? I mean a closed formula $$S_k(n) = f(k,n)$$ (not an iterative procedure such as the construction method I just described).

If that helps, actually I'm not interested in $$S_k(n)$$, but rather in the quotient $$S_k(n)/S_k(n+1)$$.

• Just a test to see if I have understood: in $S_1$ should the last term be $21$? – User3773 Feb 26 '15 at 17:39
• @Cla Oops. Yes, sorry. Corrected! – Luis Mendo Feb 26 '15 at 17:40

The numbers in sequence $S_k$ are the binomial coefficients $\binom{m}{k}$; the $n$-th term of $S_k$ is $\binom{n-1+k}{k} = \frac{(n-1+k)!}{(n-1)!k!}$. One can prove this by using that $$\binom{i}{i} + \binom{i+1}{i} + \cdots + \binom{i+j}{i} = \binom{i+j+1}{i+1}$$ for any $i,j \geq 0$.

For $k=1$ we find $P_1(n) = \binom{n-1+1}{1} = \binom{n}{1} = n$, for $k=2$ we find $P_2(n) = \binom{n-1+2}{2} = \binom{n+1}{2} = \frac{n(n+1)}{2}$, for $k=3$ we find $P_3(n) = \binom{n-1+3}{3} = \binom{n+2}{3} = \frac{n(n+1)(n+2)}{6}$, etcetera.

• Wow. It was really simple! Could you provide any reference? – Luis Mendo Feb 26 '15 at 17:43
• Thanks a lot for your help. I've posted a related question here – Luis Mendo Feb 26 '15 at 18:47

We can generalize your problem to arbitrary initial sequences.

Let $a_n\,(n=0,1,2,3,...)$ be a sequence of numbers. Define its iterated partial sums using the recurrence $$S^{(0)}_n=a_n,\quad S^{(k+1)}_n=\sum_{m=0}^n S^{(k)}_m,\tag1$$ so that we have, for example, $$\small\begin{array} &S^{(0)}_0=\color{green}{a_0}, &S^{(0)}_1=\color{blue}{a_1}, &S^{(0)}_2=\color{maroon}{a_2},&...\\ S^{(1)}_0=\color{green}{a_0}, &S^{(1)}_1=\color{green}{a_0}+\color{blue}{a_1}, &S^{(1)}_2=\color{green}{a_0}+\color{blue}{a_1}+\color{maroon}{a_2},&...\\ S^{(2)}_0=\color{green}{a_0}, &S^{(2)}_1=\color{green}{a_0}+(\color{green}{a_0}+\color{blue}{a_1}), &S^{(2)}_2=\color{green}{a_0}+(\color{green}{a_0}+\color{blue}{a_1})+(\color{green}{a_0}+\color{blue}{a_1}+\color{maroon}{a_2}),&...\\ S^{(3)}_0=\color{green}{a_0}, &S^{(3)}_1=\color{green}{a_0}+(\color{green}{a_0}+(\color{green}{a_0}+\color{blue}{a_1})),&... \end{array}\tag2$$ Now we can prove by induction that the following formula holds: $$S^{(k+1)}_n=\sum_{m=0}^n\binom{m+k}k\,a_{n-m}.\tag3$$

• Vladimir, I've just given an approach which generalizes your solution even more. Please see my new answer. – Gottfried Helms Aug 29 '19 at 6:55

A more generalized solution, where even fractional iteration-heights $$h$$ for $$S_n^{(h)}$$ become possible, can be found using a matrix-ansatz. Consider the matrix-equation $$D \cdot A = S^{(1)}(A) \tag 1$$ where $$D$$ is the lower triangular unit-matrix $$D= \Tiny \begin{bmatrix} 1&.&.&.&\cdots\\1&1&.&.&\cdots\\1&1&1&.&\cdots\\ 1&1&1&1&\cdots\\ \vdots&\vdots&\vdots&\vdots&\ddots\\ \end{bmatrix} \tag 2$$ then of course \small \begin{align} D^2 \cdot A &= S^{(2)}(A) \\ D^3 \cdot A &= S^{(3)}(A) \\ \vdots \\ D^h \cdot A &= S^{(h)}(A) \\ \end{align} \tag 3 The $$h$$'th power of $$D$$ can be computed using $$L = \log(I + (D-I))$$ and $$\exp(L)$$ using the series-representation of this functions (which reduce to finite sums in the case of using $$D$$). We get formally

$$\displaystyle \qquad \qquad \Large{D^h =}$$ $$\tag 4$$

and where we need only document the entries of the first column because of the schematic form of $$D^h$$:

$$\displaystyle \qquad \qquad S_n^{(h)} (A) = \sum_{c=0}^n D_{n,c} \cdot A[c] = \sum_{r=0}^n D_{n-r,0} \cdot A[r] \tag 5$$

The coefficients $$D_{r,0}$$ might look abscure, but can easily be described when factorials are extracted:

$$\displaystyle \qquad \qquad \large {S_5^{(h)}(A)=}$$ $$\tag 6$$

and even simpler

$$\displaystyle \qquad \qquad \large {S_5^{(h)}(A)=}$$ $$\tag 7$$

The coefficients in the previous representation are the unsigned Stirlingnumbers $$1$$'st kind and for integral $$h$$ this gives of course the appropriate binomial-expressions which are noted in the other answers and comments.
But we can easily insert fractional $$h$$ as well!

Concerning your last question, the quotient.

Example, let $$k=3$$ then the quotient can be found by multiple cancellations: $$P_3(n) = {n^3+3n^2+2n\over 6} = {(n+2)(n+1)n\over 6} \\\ P_3(n+1) = {(n+1)^3+3(n+1)^2+2(n+1)\over 6} = {(n+3)(n+2)(n+1)\over 6} \\\ {P_3(n+1)\over P_3(n)} ={{(n+3)(n+2)(n+1)\over 6}\over {(n+2)(n+1)n\over 6} } = {n+3\over n}$$ Thus in general: $${P_k(n+1)\over P_k(n)} ={{(n+k)\cdots(n+2)(n+1)\over k!}\over {(n+k-1)\cdots(n+1)n\over k!} } = {n+k\over n}$$