# $R$-recursion for the A143017

• Let $$a(n)$$ be A143017 i.e. number of $$\{2-1-3, 2'^e-31\}$$-avoiding permutations of size $$n$$ (see definition in the Elizalde paper). Here $$a(n) = \frac{1}{n}\sum\limits_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} 2\binom{n}{2k}\binom{n-k}{k-1} + \frac{n}{n-k}\binom{n}{2k+1}\binom{n-k}{k}.$$
• Let $$R(n, q) = R(n-1, q+2) + \sum\limits_{j=0}^{q}(-1)^jR(n-1,j), \\ R(0, q) = 1.$$

I conjecture that $$R(n-1, 0) = a(n).$$

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

a(n) = (1 / n) * sum(k = 0, n \ 2, 2 * binomial(n, 2*k) * binomial(n-k, k-1) + n * binomial(n, 2*k+1) * binomial(n-k, k) / (n-k))
R_upto(n) = my(v1, v2, v3); v1 = vector(2*n + 1, i, 1); v2 = v1; v3 = vector(n + 1, i, 0); v3[1] = 1; for(i = 1, n, for(q = 0, 2*(n - i), v2[q + 1] = v1[q + 3] + sum(j = 0, q, (-1) ^ j * v1[j + 1])); v1 = v2; v3[i + 1] = v1[1]); v3
test(n) = R_upto(n) == vector(n+1, i, a(i))


Is there a way to prove it?

We proceed by "guessing" a generating function for $$R(n,q)$$ and verifying that it has the right properties.

According to https://oeis.org/A143017, the generating function $$G= \sum_{n=1}^\infty a(n) x^n$$ satisfies $$$$xG^3 + (4x-2)G^2 + (4x-1)G + x = 0 \tag{1}$$$$ and it is easy to see that $$G$$ is uniquely determined as a formal power series by this equation and the condition that $$G$$ has no constant term.

Let $$F$$ be the compositional inverse of $$x(1-x^2)/(1+x-x^2)$$ so $$\frac{F(1-F^2)}{1+F-F^2} =x.$$

We note that we may rewrite the functional equation for $$F$$ as $$F = x\left(1+\frac{F}{1-F^2}\right),$$ and $$F/x$$ is the generating function for sequence A101785.

First we show that $$G = F/(1-F)$$. By (1) it is sufficient to show that $$\begin{equation*} x\left(\frac{F}{1-F}\right)^3 + (4x-2)\left(\frac{F}{1-F}\right)^2 + (4x-1)\frac{F}{1-F}+ x = 0. \end{equation*}$$ We have \begin{align*} x\left(\frac{F}{1-F}\right)^3 + (4x-2)&\left(\frac{F}{1-F}\right)^2 + (4x-1)\frac{F}{1-F}+ x\\ &=x\frac{1+F-F^2}{(1-F)^3} - \frac{F(1+F)}{(1-F)^2} \\ &=\frac{F(1-F^2)}{1+F-F^2}\frac{1+F-F^2}{(1-F)^3} - \frac{F(1+F)}{(1-F)^2}=0. \end{align*}

Now let $$\begin{equation*} S_q(x) =\sum_{n=0}^\infty R(n,q) x^{n+1}. \end{equation*}$$ The recurrence for $$R(n,q)$$ is equivalent to the identity $$$$S_q(x) =x+ xS_{q+2}(x) + x\sum_{j=0}^q (-1)^j S_j(x). \tag{2}$$$$ and the $$S_q(x)$$ are determined by (2) and the condition that each $$S_q(x)$$ is a power series in $$x$$ starting with $$x$$. Now let $$U(z) = \sum_{q=0}^\infty S_q(x) z^q.$$ Multiplying (2) by $$z^{q+2}$$ and summing on $$q\ge0$$ gives $$$$z^2 U(z) = \frac{xz^2}{1-z} +x \bigl(U(z) -S_0(x) -S_1(x)z\bigr) + \frac{xz^2}{1-z}U(-z)\tag{3}$$$$ and $$U(z)$$ is the unique solution of (3).

I claim that $$$$S_q(x) = \frac{F}{(1-F)^{\lfloor q/2\rfloor+1}(1+F)^{\lceil q/2\rceil}},\tag{4}$$$$ which is equivalent to $$$$U(z) = \frac{F(1+F+z)}{1-F^2-z^2}.\tag{5}$$$$ To verify this, we use (4) and (5) to express (3) in terms of $$x$$, $$z$$, and $$F$$, and then replace $$x$$ with $$F(1-F^2)/(1+F-F^2)$$. We obtain an easily verified identity of rational function in $$z$$ and $$F$$. In particular, $$\sum_{n=1}^\infty R(n-1,0) x^{n}=S_0(x) = \frac{F}{1-F} = G = \sum_{n=1}^\infty a(n) x^n.$$