2
$\begingroup$

Consider the following interesting recurrence $$ \begin{aligned} Q_0(k) &= k + 1 \\ Q_i(k) &= k^{2^i} + \prod_{j = 0}^{i - 1} Q_j(k), \end{aligned} $$ and use it to define $$A(k) = \frac{1}{k} \sum_{i = 0}^{k - 1} \frac{k^{2^i}}{Q_i(k)}$$ for $k \in \mathbb{Z}_{> 0}$. It's not too hard to see that $0 \le A(k) \le 1$, but I know more specifically that $A(k) = 1 - O(\ln k / k)$ and $A(k) = 1 - \Omega(1 / k)$. I would like to be able to say that $A(k) = 1 - \Theta(1 / k)$, but I'm not sure that it's even true. In fact, heuristically, it appears more likely that $A(k) = 1 - \Theta(\ln k / k)$.

I'm looking for help resolving this question either way (or perhaps somewhere in between). For those curious about where this strange recurrence came from, I can only say that $A(k)$ represents a lower bound on the ratio of two expectations that came from a very natural problem in my research.

I tried finding non-trivial upper and lower bounds on $Q_i(k)$, to no avail. I computed the first few $Q_i$ as polynomials in $k$. $$ \begin{aligned} Q_1 &= k^2 + k + 1 \\ Q_2 &= k^4 + k^3 + 2k^2 + 2k + 1 \\ Q_3 &= k^8 + k^7 + 3k^6 + 6k^5 + 9k^4 + 10k^3 + 8k^2 + 4k + 1 \end{aligned} $$ Searching their coefficients on the OEIS gives A122888 and A225200. The first five coefficients appear to always be: $1,\ 1,\ i,\ i(i - 1),\ i(i - 1)(i - 1.5)$. I'm not really sure where to go from here. Any suggestions are appreciated!

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .