Algorithm for A127782

Question

• Let $a(n)$ be A127782 (i.e., an integer sequence with generating function $A(x)$ such that $A(x)=1+xA(x+x^2)$). Here $$ a(n) = \sum\limits_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \binom{n-k-1}{k}a(n-k-1), \\ a(0) = 1. $$
• Start with vector $\nu$ of fixed length $m$ with elements $\nu_i=1$ (that is, $\nu = \{1,1,\dotsc,1\}$) and for $i$ from $1$ to $m-3$, for $j$ from $1$ to $i$, for $k$ from $1$ to $j$ apply $\nu_k := \nu_k + \nu_{k+1}$. After ending these operations we need to reverse vector $\nu$.

I conjecture that after the whole transform we have $$\nu_n=a(n-1).$$

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

upto1(n) = my(v1); v1 = vector(n+1, i, 0); v1[1] = 1; for(i=1, n, v1[i+1] = sum(k=0, (i-1)\2, binomial(i-k-1, k)*v1[i-k])); v1
upto2(n) = my(v1); v1 = vector(n+2, i, 1); for(i=1, n-1, for(j=1, i, for(k=1, j, v1[k] += v1[k+1]))); Vecrev(v1)
test1(n) = upto1(n+1) == upto2(n)

Is there a way to prove it?

Answer 1

Let $v_{i,j}$ be the value of $\nu_j$ after round $i$, with initial values $v_{0,j} = 1$ for all $j\geq 1$. The rounds of updating values of $\nu_j$ translate into the recurrence: $$v_{i,j} = \sum_{k=0}^{\lfloor (i-j)/2\rfloor} \binom{i-j-k}{k} v_{i-1,j+k}.$$ Then by induction on $i$ it follows that for all $j\leq i+1$, $v_{i,j} = a(i+1-j)$. QED