# How to find tight asymptotics of a function defined in terms of a strange recurrence?

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!