Explicit form of a recursive relation My question is to find an explicit formula for $N_{k,n}$, if the following recursive one is known:
$$
\left\{
\begin{align}
\begin{split}
 N_{1,n} &= 1 \text{,}
\\
 N_{k+1,n} &= \sum_{i = k+1}^{n-1} N_{k,i}
\end{split}
\end{align}
\right.
$$
$$
\text{for } n \in \{\,2, 3, \dots\,\}, k \in \{\,n+1, n+2, \dots\,\} \text{.}
$$
I can calculate a few first terms ($N_{1,n} = 1$, $N_{2,n} = n-2$, $N_{3,n} = \frac{(n-2)(n-3)}{2}$), but unfortunately I cannot find the general solution.
 A: As mentioned in comments, one way is to notice the Hockey stick identity in the definition and then prove it matches for rest of your definition, giving the closed form $N_{k,n}=\binom{n-2}{k-1}$.
If you don't notice that at first, you can simplify the recurrence $$N_{k+1,n+1} - N_{k+1,n} = \sum_{i=k+1}^{n}N_{k,i}-\sum_{i=k+1}^{n-1}N_{k,i} = N_{k,n},$$ hence
$$
N_{k+1,n+1} = N_{k+1,n} + N_{k,n}.
$$
Now add base cases such as $N_{1,n}=1$ and $N_{k,2}=0$ for $k\geq 2$, which follow trivially from definitions. Again you can notice that the recurrence definition resembles Pascal's formula and you can go from there. 
Eventually if all that fails, you can use a generic method for solving the last recurrence. For example, using generating functions as in the answer  Solving two-dimensional recurrence relation $a_{i,\ j}\ =\ a_{i,\ j-1}\ +\ a_{i-1,\ j-1}$, you should get $f(x,y)=\sum_{k\geq 1, n \geq 2}N_{k,n}x^k y^n=\frac{xy^2}{1-y-xy}$. This in turn simplifies using geometric series into $$f(x,y)=xy^2\sum_{n=0}^{\infty}y^n(1+x)^n=xy^2\sum_{n=0}^{\infty}y^n\sum_{k=0}^{n}\binom{n}{k}x^k = \sum_{n\geq 0, k \geq 0}^{\infty}\binom{n}{k}x^{k+1}y^{n+2},$$ and so finally
$$
f(x,y)=\sum_{n\geq 2, k \geq 1}^{\infty}\binom{n-2}{k-1}x^{k}y^{n}.
$$
Now just read off the coefficient of $x^k y^n$.
