A sequence inequality for $x_{2^n}$, the binary partition function. 
Define the sequence $\{x_{n}\}$ recursively by  $x_{1}=1$ and 
  $$\begin{cases}
x_{2k+1}=x_{2k}\\
x_{2k}=x_{2k-1}+x_{k}
\end{cases}$$
  Prove that
  $$x_{2^n}>2^{\frac{n^2}{4}}$$

I have compute some term $x_{2}=2,x_{3}=2,x_{4}=4,x_{5}=4,x_{6}=6,x_{7}=6,x_{8}=10,\cdots,x_{16}=36,x_{32}=202$
I am unsure what to do from here, I know I somehow need to compare a form of this expression to $x_{2^n}?$, but how? Am I on the right lines?but I don't have any idea how to start proving it

since
$$a_{2k}=2a_{1}+a_{2}+a_{3}+\cdots+a_{k}$$
and it is clear $$a_{p+1}-a_{p}\ge a_{q+1}-a_{q},p>q,p-q=\rm{even}$$
so we have
$$a_{r+k}-a_{r}\ge a_{r+1}-a_{r-k+1}$$
$$\Longrightarrow a_{r+k}+a_{r-k+1}\ge 2a_{r}$$
so we have
$$a_{1}+a_{2}+\cdots+a_{2r}\ge 2ra_{r}$$
then we have
$$a_{2^{n+1}}=a_{2^n}+a_{2^n-1}+\cdots+a_{1}
\ge 2^na_{2^{n-1}}>2^{\frac{n^2+2n+1}{4}}$$
