$R$-recursion for the A143017

Question

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

Answer 1

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 \begin{equation} xG^3 + (4x-2)G^2 + (4x-1)G + x = 0 \tag{1} \end{equation} 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 \begin{equation} S_q(x) =x+ xS_{q+2}(x) + x\sum_{j=0}^q (-1)^j S_j(x). \tag{2} \end{equation} 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 \begin{equation} 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} \end{equation} and $U(z)$ is the unique solution of (3).

I claim that \begin{equation} S_q(x) = \frac{F}{(1-F)^{\lfloor q/2\rfloor+1}(1+F)^{\lceil q/2\rceil}},\tag{4} \end{equation} which is equivalent to \begin{equation} U(z) = \frac{F(1+F+z)}{1-F^2-z^2}.\tag{5} \end{equation} 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.$$