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


In this answer I will prove that $$\log_2 \left(x_{2^k}\right) \sim \frac{k^2}{2}$$ by providing the explicit inequalities $$2^{k^{2}/2-k/2-k\log_{2}k}\leq x_{2^k} \leq2^{k^{2}/2+k/2+1}.$$ This not only shows that we can do better and achieve $k^2/2$ in the exponent, but also that this is optimal.

As martin mentions in the comments, this sequence $x_{n}$
  is the binary partition function, which I will denote by $p_{B}(n).$ This functions counts the number of ways to write $$n=\sum_{i=0}^{\lfloor\log_{2}n\rfloor}a_{i}2^{i}$$
 where the $a_{i}$ are nonnegative integers. In what follows we'll provide some fairly sharp upper and lower bounds for $p_{B}\left(2^{k}\right)$. 
Upper Bounds: When $n=2^{k}$, $a_{i}$ can be at most $2^{k-i}$. This yields $k+1$ trivial partitions where $a_{i}=2^{k-i}$ for some $i$, and at most $2^{k-i}$ remaining choices for each $a_i$. Thus the number of possible choices is at most $$\prod_{i=0}^{k-1}2^{k-i}=2^{\sum_{i=1}^{k}i}=2^{k(k+1)/2},$$
 and so $$p_{B}\left(2^{k}\right)\leq2^{k^{2}/2+k/2}+(k+1)\leq2^{k^{2}/2+k/2+1}.$$
Lower Bounds: To bound $p_{B}(2^{k})$ from below, we split up $2^{k}$ into $k$ parts and assign each of these parts to the coefficients $a_{1},a_{2},\dots,a_{k}.$ There are at least $2^{k-i}/k$ choices available for each of the $a_{i}$ given above, and for any such choice we can complete it into a full partition by choosing $a_{0}=2^{k}-\sum_{i=1}^{k}a_{i}2^{i}.$
  (Note that if $2^{k-i}/k<1$, there still is always one choice which is a_{i}=0
 ) Thus we have given the lower bound $$p_{B}(2^{k})\geq\prod_{i=1}^{k}\frac{2^{k-i}}{k}=k^{-k}2^{k(k-1)/2},$$ and so $$p_{B}(2^{k})\geq2^{k^{2}/2-k/2-k\log_{2}k}.$$
Remark: The inequality $x_{2^k}>2^{k^2/4}$ follows from a numerical check along with the fact that $$\frac{k^{2}}{2}-\frac{k}{2}-k\log_{2}k>\frac{k^2}{4}$$ for all $k\geq 19$. 
