Remove first element of sequence, compute cumulative sum, iterate

420 Views Asked by At

(This is related to my previous question General formula for iterated cumulative sum.)

Consider the sequence $S_0$ consisting of ones:

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

Now remove the first element and compute the cumulative sum of this sequence. Call the resulting sequence $S_1$:

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

Again, generate $S_2$ by removing first element from $S_1$ and computing the cumulative sum:

$$ 2,5,9,14,20,27\ldots $$

Then $S_3$:

$$ 5,14,28,48,75,110\ldots $$

And so on.

My question: Is there a general formula for $S_k(n)$?

(In the linked question, the problem is solved for the cummulative sum without removing first element, in terms of binomial coefficients.)

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

1

There are 1 best solutions below

1
On BEST ANSWER

For $0\le k\le n$ let $C_{n,0}=1$ for all $n$, $C_{n,k}=C_{n-1,k}+C_{n,k-1}$ for $0<k<n$, and $C_{n,n}=C_{n,n-1}$; the resulting triangular array is often called Catalan’s triangle. Here are rows $0$ through $5$:

$$\begin{array}{ccc} 1\\ 1&1\\ 1&2&2\\ 1&3&5&5\\ 1&4&9&14&14\\ 1&5&14&28&42&42 \end{array}$$

An easy induction proves that your sequences are the columns of this array, i.e., that your $k$-th sequence is $\langle C_{n,k}:n\ge k\rangle$.

Catalan’s triangle is OEIS A009766, with lots of references and the closed form

$$C_{n,k}=\frac{n+1-k}{n+1}\binom{n+k}k\;.$$