# Deriving a sum from a two-variable recurrence stated in the OEIS

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

• All the entry says is, "Number of ways of placing n identifiable positive intervals with a total of exactly k starting and/or finishing points." I don't see how that clarifies what you have said at all. What is a starting or finishing point? Can you give an example? Jul 9 '19 at 23:32
• @saulspatz I don't actually care about the combinatorial interpretation. I'm only interested in how to derive the sum from the recurrence. Both are stated in the "FORMULA" section of the OEIS entry, but without proof. Jul 9 '19 at 23:36
• The exponent in the formula should be $n$ instead of $m$. Jul 9 '19 at 23:45
• @saulspatz Thanks for the catch! Fixed now. Jul 9 '19 at 23:47

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