Sequence that sums up to A224071

Question

• Let $a(n)$ be A224071 (i.e., number of Schroeder paths of semilength $n$ in which there are no $(2,0)$-steps at level $1$). Here

$$ a(n) = \frac{1}{2(n+1)}\sum\limits_{k=0}^{n}(k+1)((-1)^{\left\lfloor\frac{k+1}{3}\right\rfloor}+(-1)^{\left\lfloor\frac{k+2}{3}\right\rfloor})\sum\limits_{i=0}^{n-k}\binom{n+1}{n-k-i}\binom{n+i}{n} $$

• Also ordinary generating function $A(x)$ satisfies

$$ A(x)=\frac{4}{3-5x+\sqrt{1-6x+x^2}} $$

• Let $\nu_2(n)$ be A007814 (i.e., number of trailing zeros in the binary expansion of $n$). Here

$$ \nu_2(2n+1) = 0, \\ \nu_2(2n) = \nu_2(n) + 1 $$

• Let $b(n)$ be an integer sequence such that

$$ b(2n+1) = b(n), \\ b(2n) = b(n) + b(2n-2^{\nu_2(n)+1}), \\ b(0) = 1 $$

• Let

$$ s(n) = \sum\limits_{i=0}^{2^n - 1} b(i) $$

I conjecture that $$s(n) = a(n).$$

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

a(n) = 1/(2*(n+1))*sum(k = 0, n, (k+1)*((-1)^((k+1)\3) + (-1)^((k+2)\3))*sum(i=0, n-k, binomial(n+1, n-k-i)*binomial(n+i,n)))
b(n) = if(n == 0, 1, b(n\2) + if(!(n%2), b(n-2^valuation(n, 2))))
s(n) = sum(i=0, 2^n - 1, b(i))
test(n) = s(n) == a(n)

Is there a way to prove it?

Answer 1

For $n=2^tk$ with odd $k$, we have $$b(n) = b(\frac{k-1}2)+\sum_{i=1}^t b(2^i(k-1))$$

Similarly to this answer, we partition $s(n)$ into smaller sums depending on the 2-adic valuation of the summands: $$s(n) = \sum_{k\geq 0} s^{(k)}(n),$$ where $$s^{(k)}(n) := \sum_{j=0\atop \nu_2(2^n+j)=k}^{2^n-1} b(j).$$ Clearly, $s^{(k)}(n)=0$ for $k>n$.

From the recurrence above, it follows that for $n>1$, $$s^{(0)}(n) = s(n-1) = \sum_{k=0}^{n-1} s^{(k)}(n-1)$$ and for $k\geq1$ $$s^{(k)}(n) = s^{(k-1)}(n-1) + \sum_{m\geq k+1} s^{(m)}(n),$$ further implying that $$2s^{(k)}(n) = s^{(k-1)}(n-1) + s^{(0)}(n+1) - \sum_{m=0}^{k-1} s^{(m)}(n).$$

Define the generating function $${\cal S}(x,y) := \sum_{n,k\geq 0} s^{(k)}(n) x^n y^k.$$ The above recurrence for $s^{(k)}(n)$ translates to $$2({\cal S}(x,y) - {\cal S}(x,0)) = xy{\cal S}(x,y) + \frac{{\cal S}(x,0)-1}x\frac{y}{1-y} - {\cal S}(x,y)\frac{y}{1-y},$$ from where it follows that $${\cal S}(x,y) = \frac{(y+2x-2xy) {\cal S}(x,0) - y}{x(2-y-xy+xy^2)}.$$

Since the coefficient of $x^n$ in ${\cal S}(x,y)$ is a polynomial in $y$, we have that $2-y-xy+xy^2$ as a polynomial in $y$ must divide the polynomial $(y+2x-2xy) {\cal S}(x,0) - y$. Plugging its zero $y=\frac{1+x-\sqrt{1-6x+x^2}}{2x}$, we obtain $${\cal S}(x,0) = \frac{x + 1 - \sqrt{x^{2} - 6 \, x + 1}}{2 \, x^{2} - x + 1 + (2 \, x - 1)\sqrt{x^{2} - 6 \, x + 1}}.$$ It remains to verify that $${\cal S}(x,1) = \frac{{\cal S}(x,0) - 1}{x} = \frac{4}{3-5x+\sqrt{1-6x+x^2}}$$ as required.