# On a A089039 and pair of sequences with simple recursion

• 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?

• If your formula is only tested numerically but not proved, you should prepend it with the word Conjecture when adding it to the OEIS. Commented Apr 20 at 14:00
• Unfortunately, "enough for me" is not a valid mathematical argument. Commented Apr 20 at 14:46
• "I want to share such findings, marking them as true" - please don't do that unless you have proof. You violate the mathematical standards for what is "true", and mislead other people that way. It's fine to add your formulas to the OEIS, but please clearly mark those that are not yet proved as such. Commented Apr 20 at 15:18
• I'd like to back up what Max is saying here. Please do not do this! There are many things in mathematics that are true for very large initial intervals and then fail. You might think that $2^𝑛−3$ is never divisible by $𝑛$ for $n>1$, but then you get to $𝑛=4700063497$ and find this is the first time it happens. Commented Apr 20 at 19:26
• If you can, please undo any damage you've done to OEIS this way. We all depend on it. Commented Apr 20 at 19:47

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.