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

Solution 1:

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$.

Solution 2:

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}}$$