IMC 2014 · Day 1 · P2

Let $N_n = \binom{n+1}{2}$ (then $a_{N_n}$ is the first appearance of number $n$ in the sequence) and consider limit of the subsequence $$b_{N_n} := \frac{\sum_{k=1}^{N_n} a_k}{N_n^\alpha} = \frac{\sum_{k=1}^{n} (1 + \dots + k)}{\binom{n+1}{2}^\alpha} = \frac{\sum_{k=1}^{n} \binom{k+1}{2}}{\binom{n+1}{2}^\alpha} = \frac{\binom{n+2}{3}}{\binom{n+1}{2}^\alpha} = \frac{\frac{1}{6} n^3 (1 + 2/n)(1 + 1/n)} {(1/2)^\alpha n^{2\alpha} (1 + 1/n)^\alpha}.$$ We can see that $\lim_{n \to \infty} b_{N_n}$ is positive and finite if and only if $\alpha = 3/2$. In this case the limit is equal to $\beta = \frac{\sqrt{2}}{3}$. So, this pair $(\alpha, \beta) = (\frac{3}{2}, \frac{\sqrt{2}}{3})$ is the only candidate for solution.

We will show convergence of the original sequence for these values of $\alpha$ and $\beta$. Let $N$ be a positive integer in $[N_n + 1, N_{n+1}]$, i.e., $N = N_n + m$ for some $1 \le m \le n + 1$. Then we have $$b_N = \frac{\binom{n+2}{3} + \binom{m+1}{2}} {\left( \binom{n+1}{2} + m \right)^{3/2}}$$ which can be estimated by $$\frac{\binom{n+2}{3}}{\left( \binom{n+1}{2} + n \right)^{3/2}} \le b_N \le \frac{\binom{n+2}{3} + \binom{n+1}{2}}{\binom{n+1}{2}^{3/2}}.$$ Since both bounds converge to $\frac{\sqrt{2}}{3}$, the sequence $b_N$ has the same limit and we are done.