Tips/strategies for bounding this partial sum with binomial coefficients

95 Views Asked by At

Edit: I simplified slightly the notation and added one of my attempts.

So I am interested in lower bounding this sum:

\begin{equation} \left(\frac{3}{2}\right)^d \left(\frac{9}{4}\right)^{2L} \left| \sum_{\alpha_1 k_1 + ... + \alpha_d k_d = L} \left(-\frac{4}{27}\right)^{k_1+k_2+...+k_d} {1 \choose k_1}{1+2k_1 \choose k_2}{1+2k_1+2k_2 \choose k_3} \cdots {1+2k_1+...+2k_{d-1} \choose k_d} \right| \end{equation}

where $\alpha_j=d+1-j$, and the limits are $0 \leq k_1 \leq 1, 0 \leq k_2 \leq 1+2k_1, \cdots, 0\leq k_j \leq 1+2k_1+\cdots+k_{j-1}$.

Specifically, I am interested in lower bounding the absolute value when $L=O(d)$. If $L=0$ the result is trivially $(3/2)^d$, so I suspect that it also grows exponentially with $d$ when $L$ is small. However, I don't know how to prove it (numerically it seems to hold). Do you know of any techniques that could be applied to this problem?

Something that I tried is to express it in the form of a polynomial. Specifically, the value of the sum is equivalent to computing the value of the $(d+2L)$-th coefficient of the polynomial $Q(x) = (3/2)^d K_1(x) K_2(x)...K_d(x)$, where the $K_j(x)$ can be obtained recursively: \begin{equation} K_1(x)=1-x^2/3 \end{equation} \begin{equation} K_2(x)=1-\frac{1}{3}(3/2)^2K_1(x)^2x^4 \end{equation} \begin{equation} K_j(x)=1-\frac{1}{3}(3/2)^{2j-1} K_1(x)^2 K_2(x)^2 ... K_{j-1}^2(x) x^{2j} \end{equation}

However, I am not sure this leads anywhere, since computing the coefficient seems equally hard, and I could not think of a smart way to bound it. Any ideas would be very appreciated, thanks!