On a A089039 and pair of sequences with simple recursion

Question

• Let $a(n)$ be A089039 (i.e., number of circular permutations of $2n$ letters that are free of jealousy). Here

$$ a(n) = \sum\limits_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\frac{n!(n-k-1)!^2}{(k-1)!^2(n-2k)!k}, \\ a(1) = 1 $$

• Let $b(n)$ be A001040. Here

$$ b(n) = (n-1)b(n-1) + b(n-2), \\ b(0) = 0, b(1) = 1 $$

• Let $c(n)$ be A001053. Here

$$ c(n) = (n-1)c(n-1) + c(n-2), \\ c(0) = 1, c(1) = 0 $$

• Let $d(n)$ be an integer sequence such that

$$ d(n) = (n-1)!(b(n-1)+c(n)), \\ d(1) = 1 $$

I conjecture that $$d(n)=a(n).$$

Note that Feb 10 2019 formula in the OEIS entry of A089039 is mine. I just checked the result numerically and added it to the encyclopedia as correct.

Here is the PARI/GP program to check it numerically:

a(n) = if(n == 1, 1, sum(k = 1, n\2, n!*(n-k-1)!^2/((k-1)!^2*(n-2*k)!*k)))
d(n) = if(n == 1, 1, my(v1, v2); v1 = [0, 1]; v2 = [1, 0]; for(i=2, n, v1 = [v1[2], (i-1)*v1[2] + v1[1]]; v2 = [v2[2], (i-1)*v2[2] + v2[1]]); (n-1)!*(v1[1] + v2[2]))
test(n) = d(n) == a(n)

Is there a way to prove it?

Answer 1

Let $d'(n) := d(n)/(n-1)! = b(n-1)+c(n)$ and $a'(n):=a(n)/(n-1)!$.

From the given recurrences for $b(n)$ and $c(n)$, it follows that $d'(n)$ satisfies the following order-4 recurrence: $$d'(n) + (2n + 2)d'(n+1) + (n^2 + 3n)d'(n+2) - (2n+4)d'(n+3) + d'(n+4) = 0.$$ Since $a'(n)$ has the same initial values as $d'(n)$, it remains to verify that $a'(n)$ satisfy the same recurrence.

Let's rewrite $a'(n)$ in the form that allows somewhat flexible summation over $k$: $$(\star)\qquad a'(n) = \sum_{k=1}^{B} T(n,k)$$ where $T(n,k):=\binom{n-k-1}{k-1}\frac{n(n-k-1)!}{k!}$ and $B$ can be any integer in the interval $[\lfloor n/2\rfloor,n-1]$. We apply Zeilberger's algorithm for finding a recurrence for $T(n,k)$. Maple's command Zeilberger( n*binomial(n-k-1,k-1)*(n-k-1)!/k!, n, k, En ) computes the recurrence: $$T(n,k) + (2n + 2)T(n+1,k) + (n^2 + 3n)T(n+2,k) - (2n+4)T(n+3,k) + T(n+4,k) = G(n,k+1) - G(n,k)$$ for a certain explicit but ugly looking function $G(n,k)$. Noticing that $G(n,n)=G(n,1)=0$, we sum this recurrence for $T(n,k)$ over $k=1..n-1$ and use formula $(\star)$ to obtain the recurrence: $$a'(n) + (2n + 2)a'(n+1) + (n^2 + 3n)a'(n+2) - (2n+4)a'(n+3) + a'(n+4) = 0,$$ which matches the one for $d'(n)$. QED

PS. It should have been possible to obtain the last recurrence directly with Maple's command ZeilbergerRecurrence( n*binomial(n-k-1,k-1)*(n-k-1)!/k!, n, k, a, 1..n-1 ) but somehow it fails.