Sequence A059117 in the OEIS is $\lambda(k, n)$, the number of ways to place $n$ distinct intervals with exactly $k$ starting and stopping points. (See the entry for clarification on what that means.) The $\lambda$-numbers are defined by
\begin{align*} \lambda(k, n) &= {k \choose 2} (\lambda(k, n - 1) + 2 \lambda(k - 1, n - 1) + \lambda(k - 2, n - 1)) \\ \lambda(k, 0) &= [k = 0], \end{align*} where $[k = 0]$ is an Iverson bracket. The comments at the OEIS note that $\lambda$ can be expressed as $$\lambda(k, n) = \sum_j {k \choose j} {j \choose 2}^n (-1)^{k - j} .$$ How can you derive this sum from the recurrence relation?
I can check that the given sum satisfies the recurrence, but I can't derive it. I've tried ordinary and exponential generating functions, but they get really messy. For example, the ordinary generating function $A_k(x) = \sum_{n \geq 0} \lambda(k, n) x^n$ satisfies the three-term recurrence $$(1 - {k \choose 2} x) A_k = x {k \choose 2} (2 A_{k - 1} + A_{k - 2}).$$
Define with initial values $\, a_0(n) = \delta_{0n}\,$ the recursion $$ a_k(n) = {n \choose 2} (a_{k-1}(n) + 2 a_{k-1}(n - 1) + a_{k-1}(n - 2)). \tag1$$
Define the exponential generating function $$ f_k(x) := \sum_{n=0}^\infty a_k(n)x^n/n! \tag2 $$ and the related e.g.f. $$ g_k(x) = \sum_{n=0}^\infty b_k(n)x^n/n! := f_k(x) \exp(x) \tag3$$ where $\,b_k\,$ is the Binomial transform of $\,a_k\,$ in OEIS terminology.
Notice that $$ g_k'(x) = (f_k(x) + f_k'(x))\exp(x) \tag4 $$ and $$ g_k''(x) = (f_k(x) + 2f_k'(x) + f_k''(x))\exp(x). \tag5 $$ Notice that equation $(1)$ implies that $$ g_k(x) = x^2/2\; g_{k-1}''(x). \tag6 $$ Referring back to equation $(3)$ this implies that $$ b_k(n) = {n \choose 2}b_{k-1}(n) \tag7$$ and given the initial value of $\, b_0(n)=1\,$ this implies $$ b_k(n) = {n \choose 2}^k. \tag8$$ Applying the inverse binomial transform gives us the result $$ a_k(n) = \sum_{j=0}^n (-1)^{n - j}{n \choose j} {j \choose 2}^k .\tag9$$