Meeting a Challenge raised by Ekhad and Zeilberger related to Stern's Triangle

Abstract

This paper resolves an open problem raised by Ekhad and Zeilberger for computing $\omega (10000)$, which is related to Stern's triangle. While $\nu (n)$, defined as the sum of squared coefficients in ${\prod }_{i=0}^{n-1}(1+x^{2^i}+x^{2^{i+1}})$, admits a rational generating function, the analogous function $\omega (n)$ for ${\prod }_{i=0}^{n-1}(1+x^{2^i+1}+x^{2^{i+1}+1})$ presents substantial computational difficulties due to its complex structure. We develop a method integrating constant term techniques, conditional transfer matrices, algebraic generating functions, and $P$-recursions. Using the conditional transfer matrix method, we represent $\omega (n)$ as the constant term of a bivariate rational function. This framework enables the calculation of $\omega (10000)$, a $6591$-digit number, and illustrates the method's broad applicability to combinatorial generating functions.