How to get a closed form for a possibly simple combinatorial sequence

Question

I hope this question isn't too simple for MO. Combinatorics is not my forte.

I have two positive integers $n,k$ that define a resultant integer. I am running an experiment and I have a collection of sequences of integers as follows. For each $n$ I list the results for $k = 1,\dots 20$ although there are more integers that follow the same pattern.

• $n = 2$ gives 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11.

This is a simple sequence with an obvious pattern.

• $n = 3$ gives 1, 3, 5, 8, 11, 15, 19, 24, 29, 35, 41, 48, 55, 63, 71, 80, 89, 99, 109, 120

The differences between consecutive numbers is exactly the sequence for $n = 2$ (excluding the first number $1$ in the preceding sequence.

• $n = 4$ gives $1, 4, 9, 17, 28, 43, 62, 86, 115, 150, 191, 239, 294, 357, 428, 508, 597, 696, 805, 925$.

Again the differences between consecutive numbers is exactly the sequence for $n = 3$ (excluding the first number $1$ in the preceding sequence).

And it continues this way for larger values of $n$.

Assuming this is indeed the general rule, how could one find a closed form formula for arbitrary positive $n ,k$ (with $n \geq 2$).

Answer 1

It's worth to consider the sequence for $n=1$: $$1,1,0,1,0,1,0,\dots$$ Let $s_k^n$ denote the $k$-th term of the $n$-th sequence. In particular, $s_1^1=1$ and for $k>1$, $s_k^1$ equals 1 if $k$ is even and $0$ if $k$ is odd.

Then for $n>1$, we have $$s_k^{n} = \sum_{i_{n-1}=1}^k s_{i_{n-1}}^{n-1} = \cdots = \sum_{i_{n-1}=1}^k \sum_{i_{n-2}=1}^{i_{n-1}} \cdots \sum_{i_1=1}^{i_2} s_{i_1}^1=\sum_{i_1,i_2,\dots,i_{n-1}\atop 1\leq i_1\leq i_2\leq \dots \leq i_{n-1}\leq k} s_{i_1}^1$$ $$ = \sum_{i_1=1}^{k} s_{i_1}^1 \sum_{i_2,i_3,\dots,i_{n-1}\atop i_1\leq i_2\leq \dots \leq i_{n-1}\leq k} 1 = \sum_{i_1=1}^{k} s_{i_1}^1 \left(\!\!\binom{k-i_1+1}{n-2}\!\!\right) = \sum_{i_1=1}^{k} s_{i_1}^1 \binom{k-i_1+n-2}{n-2},$$ where $\left(\!\!\binom{k-i_1+1}{n-2}\!\!\right) = \binom{k-i_1+n-2}{n-2}$ gives the number of combinations with repetitions $(i_2,i_3,\dots,i_{n-1})$ from the set $\{t_1,i_1+1,\dots,k\}$ of size $k-i_1+1$.

Recalling the formula for $s_{i_1}^1$, we have $$s_k^n = \binom{k+n-3}{n-2} + \sum_{\ell=1}^{\lfloor k/2\rfloor} \binom{k+n-2-2\ell}{n-2},$$ which holds for all $n>1$ and $k\geq 1$.

UPDATE. Noticing that $\binom{k+n-2-2\ell}{n-2}$ is the coefficient of $x^{n-2}$ in $(1-x)^{-(k+1-2\ell)}$, the formula above can be further reduced to the sum of $O(n)$ terms (which may be preferable when $k$ is large as compared to $n$): $$s_k^n = \binom{k+n-3}{n-2} + \frac{(k+1)\bmod 2}{2^{n-1}} + \sum_{i=1}^{n-1} \binom{k-2+i}{i}\frac{1}{2^{n-i}}.$$