5
$\begingroup$

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

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

4 Answers 4

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Wow. It was really simple! Could you provide any reference? $\endgroup$
    – Luis Mendo
    Commented Feb 26, 2015 at 17:43
  • $\begingroup$ Thanks a lot for your help. I've posted a related question here $\endgroup$
    – Luis Mendo
    Commented Feb 26, 2015 at 18:47
3
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

We can generalize this problem to an arbitrary initial sequence.

Let $a_n\,(n=0,1,2,3,...)$ be a sequence of numbers. Let's define its iterated partial sums by the recurrence: $$S^{(0)}_n=a_n,\quad S^{(p)}_n=\sum_{k=0}^n S^{(p-1)}_k\quad \color{gray}{\text{for}\,\,p>0,}$$ so that we have $$\small\begin{array} &\!\!\!\!\!\!S^{(0)}_0=\color{green}{a_0}, &\!\!S^{(0)}_1=\color{blue}{a_1}, &\!\!\!S^{(0)}_2=\color{maroon}{a_2},&\!\!\tiny...\\ \!\!\!\!\!\!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},&\!\!\tiny...\\ \!\!\!\!\!\!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}),&\!\!\tiny...\\ \!\!\!\!\!\!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})),&\!\!\tiny... \end{array}$$ Now we can prove by induction that the following formula holds: $$S^{(p)}_n=\sum_{k=0}^n \binom{n-k+p-1}{p-1} a_k.$$

$\endgroup$
1
  • $\begingroup$ Vladimir, I've just given an approach which generalizes your solution even more. Please see my new answer. $\endgroup$ Commented Aug 29, 2019 at 6:55
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .