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

  • $\begingroup$ Just a test to see if I have understood: in $S_1$ should the last term be $21$? $\endgroup$ – User3773 Feb 26 '15 at 17:39
  • $\begingroup$ @Cla Oops. Yes, sorry. Corrected! $\endgroup$ – 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.

  • $\begingroup$ Wow. It was really simple! Could you provide any reference? $\endgroup$ – Luis Mendo Feb 26 '15 at 17:43
  • $\begingroup$ Thanks a lot for your help. I've posted a related question here $\endgroup$ – 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$$

  • $\begingroup$ Vladimir, I've just given an approach which generalizes your solution even more. Please see my new answer. $\endgroup$ – 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 =} $ picture1 $ \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)=}$ image2 $\tag 6$

and even simpler

$ \displaystyle \qquad \qquad \large {S_5^{(h)}(A)=}$ image3 $\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} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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