Open Contests

As $a_n=n\cdot a_{\lfloor \frac{n}{2}\rfloor }$, it suffices to show that for each $n\ge 12$ we have $a_{\lfloor \frac{n}{2}\rfloor }\ge n$. By the inequalities $n\le 2\lfloor \frac{n}{2}\rfloor +1<3\lfloor \frac{n}{2}\rfloor$ this reduces to proving that $a_m\ge 3m$ for each $m\ge 6$. By $a_m=m\cdot a_{\lfloor \frac{m}{2}\rfloor }$ the latter reduces to proving $a_l\ge 3$ for $l\ge 3$. This is true, since $a_l=l\cdot a_{\lfloor \frac{l}{2}\rfloor }\ge l$.

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
a_n	1	2	3	8	10	18	21	64	72	100	110	216	234	294	315
n^2	1	4	9	16	25	36	49	64	81	100	121	144	169	196	225

Hence for $12\le n<16$ the claim is true. For bigger numbers note that for each $k\ge 4$ we have $$a_{2k}=2^k\cdot 2^{k-1}\cdots 2\cdot 1=2^{k+(k-1)+\cdots +1}=2^{\frac{k(k+1)}{2}}\ge 2^{2(k+1)}.$$ By simple induction we conclude that $a_n$ increases as $n$ increases. For arbitrary $n\ge 16$ pick $k\ge 4$ such that $2^k\le n<2^{k+1}$, giving $$a_n\ge a_{2k}\ge 2^{2(k+1)}=(2^{k+1}{)}^2>n^2.$$