# Sequence that sums up to A224071

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

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.