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



How to get a closed form for a possibly simple combinatorial sequence
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](https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition) $(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}}.$$


