CN-SMO 2015 Problem 1

Suppose that the sequence $\{a_n\}$ satisfy $a_1=1$ and $a_{2k}=a_{2k-1}+a_k, a_{2k+1}=a_{2k}$ for $k=1,2, \ldots$ Prove that $a_{2^n}< 2^{\frac{n^2}{2}}$ for any integer $n \geq 3$ .