Intersecting algorithm for A065601

Question

• Let $a(n)$ be A065601 (i.e., number of Dyck paths of length $2n$ with exactly $1$ hill). Here $$ a(n) = \frac{1}{2(n+1)}((3n-2)a(n-1) + 2(9n-19)a(n-2) + 4(2n-3)a(n-3)), \\ a(0) = a(2) = 0, a(1) = 1. $$ Also ordinary generating function is $$ \frac{1}{x}\left(\frac{1-\sqrt{1-4x}}{3-\sqrt{1-4x}}\right)^2. $$ Finally, the closed form is $$ a(n) = \frac{1}{n+1}\sum\limits_{j=0}^{n-1}\binom{2n-j-1}{n}(j+1)(j+2)(-1)^j. $$
• Start with vectors $\nu_1, \nu_2$ of length $n$ with elements $\nu_{1,i} = 1, \nu_{2,i}=i$ (that is, $\nu_1 = \{1, 1, \dotsc, 1\}$, $\nu_2 = \{1, 2, \dotsc, n\}$) and for $i$ from $1$ to $n-1$ and for $j$ from $i+1$ to $n$ apply $[\nu_{1,j}, \nu_{2,j}] := [\nu_{1,j} + \nu_{2,j-1}, \nu_{2,j} + \nu_{1,j-1}]$.

I conjecture that after the whole transform we have $|\nu_{1,i}-\nu_{2,i}|=a(i-1)$.

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

upto1(n) = my(v1); v1 = vector(n, i, 1); v2 = vector(n, i, i); for(i=1, n-1, for(j=i+1, n, v1[j] += v2[j-1]; v2[j] += v1[j-1])); vector(n, i, abs(v1[i]-v2[i]))
upto2(n) = my(v1); v1 = vector(n+1, i, 0); v1[2] = 1; for(i=3, n, v1[i+1] = ((3*i - 2)*v1[i] + 2*(9*i - 19)*v1[i-1] + 4*(2*i-3)*v1[i-2])/(2*(i+1))); v1
test(n) = upto1(n+1) == upto2(n)

Is there a way to prove it?

Answer 1

Let $v_{i,j}$ be the value of $\nu_{2,j} - \nu_{1,j}$ after round $i$, with initial values $v_{0,j} = j-1$ for all $j\geq 1$. For $i\geq 1$, we have $v_{i,j} = v_{i-1,j}$ for $j\leq i$, while for $j\geq i+1$, $$v_{i,j} = v_{i-1,j} - v_{i,j-1}.$$ Correspondingly, the generating function $$F(x,y) := \sum_{i\geq 0} x^i \sum_{j\geq i+1} y^{j-i-1} v_{i,j}$$ satisfies $$(x-y-y^2)F(x,y) = x(1+y)F(x,0) - \frac{y^2(1+y)}{(1-y)^2}.$$ Plugging $y=\frac{-1+\sqrt{1+4x}}{2}$ (zero of $x-y-y^2$) in, we get $$F(x,0) = \frac1{x} \bigg(\frac{-1+\sqrt{1+4x}}{-3+\sqrt{1+4x}}\bigg)^2,$$ and correspondingly $$F(-x,0) = -\frac1{x} \bigg(\frac{1-\sqrt{1-4x}}{3-\sqrt{1-4x}}\bigg)^2,$$ matching the negated o.g.f. for A065601. Hence, $$v_{i,i} = v_{i-1,i} = (-1)^{i-1} [x^{i-1}]\ F(-x,0) = (-1)^i a(i-1).$$ QED

---

PS. The same result can also be obtained from this earlier question by taking $f(i)=-1$ for all $i$.