Una desigualdad de secuencia para $x_{2^n}$ la función de partición binaria.

Question

Definir la secuencia $\{x_{n}\}$ recursivamente por $x_{1}=1$ y $$\begin{cases} x_{2k+1}=x_{2k}\\ x_{2k}=x_{2k-1}+x_{k} \end{cases}$$ Demostrar que $$x_{2^n}>2^{\frac{n^2}{4}}$$

He calculado algún término $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$

No sé qué hacer a partir de aquí, sé que de alguna manera tengo que comparar una forma de esta expresión con $x_{2^n}?$ pero, ¿cómo? ¿Estoy en la línea correcta? pero no tengo ni idea de cómo empezar a probarlo

Answer 1

En esta respuesta demostraré que $$\log_2 \left(x_{2^k}\right) \sim \frac{k^2}{2}$$ proporcionando las desigualdades explícitas $$2^{k^{2}/2-k/2-k\log_{2}k}\leq x_{2^k} \leq2^{k^{2}/2+k/2+1}.$$ Esto no sólo demuestra que podemos hacerlo mejor y lograr $k^2/2$ en el exponente, pero también que éste sea óptimo.

Como martin menciona en los comentarios, esta secuencia $x_{n}$ es el función de partición binaria que denotaré por $p_{B}(n).$ Esta función cuenta el número de formas de escribir $$n=\sum_{i=0}^{\lfloor\log_{2}n\rfloor}a_{i}2^{i}$$ donde el $a_{i}$ son enteros no negativos. En lo que sigue proporcionaremos algunos límites superiores e inferiores bastante precisos para $p_{B}\left(2^{k}\right)$ .

Límites superiores: Cuando $n=2^{k}$ , $a_{i}$ puede ser como máximo $2^{k-i}$ . Esto da como resultado $k+1$ particiones triviales donde $a_{i}=2^{k-i}$ para algunos $i$ y como máximo $2^{k-i}$ opciones restantes para cada $a_i$ . Por lo tanto, el número de opciones posibles es como máximo $$\prod_{i=0}^{k-1}2^{k-i}=2^{\sum_{i=1}^{k}i}=2^{k(k+1)/2},$$ y así $$p_{B}\left(2^{k}\right)\leq2^{k^{2}/2+k/2}+(k+1)\leq2^{k^{2}/2+k/2+1}.$$ Límites inferiores: Para atar $p_{B}(2^{k})$ desde abajo, nos dividimos $2^{k}$ en $k$ partes y asignar cada una de estas partes a los coeficientes $a_{1},a_{2},\dots,a_{k}.$ Hay al menos $2^{k-i}/k$ opciones disponibles para cada uno de los $a_{i}$ dada anteriormente, y para cualquier elección podemos completarla en una partición completa eligiendo $a_{0}=2^{k}-\sum_{i=1}^{k}a_{i}2^{i}.$ (Tenga en cuenta que si $2^{k-i}/k<1$ siempre hay una opción que es a_{i}=0 ) Por lo tanto, hemos dado el límite inferior $$p_{B}(2^{k})\geq\prod_{i=1}^{k}\frac{2^{k-i}}{k}=k^{-k}2^{k(k-1)/2},$$ y así $$p_{B}(2^{k})\geq2^{k^{2}/2-k/2-k\log_{2}k}.$$

Observación: La desigualdad $x_{2^k}>2^{k^2/4}$ se desprende de una comprobación numérica junto con el hecho de que $$\frac{k^{2}}{2}-\frac{k}{2}-k\log_{2}k>\frac{k^2}{4}$$ para todos $k\geq 19$ .

Answer 2

Desde $$a_{2k}=2a_{1}+a_{2}+a_{3}+\cdots+a_{k}$$ y está claro $$a_{p+1}-a_{p}\ge a_{q+1}-a_{q},p>q,p-q=\rm{even}$$ por lo que tenemos $$a_{r+k}-a_{r}\ge a_{r+1}-a_{r-k+1}$$ $$\Longrightarrow a_{r+k}+a_{r-k+1}\ge 2a_{r}$$ por lo que tenemos $$a_{1}+a_{2}+\cdots+a_{2r}\ge 2ra_{r}$$ entonces tenemos $$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}}$$