2
$\begingroup$
  • 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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.