La construcción de las secuencias con las medidas ya "existente" en la secuencia

Question

Secuencia $\{a_k\}$ está construido de acuerdo a la siguiente regla: $$ a_0=0;\\ a_1=1;\\ \forall n\in \mathbb{N} ~ \existe i,j ~ (0\leqslant i<j\leqslant n),\mbox{ que } a_{n+1}-a_{n} = a_j-a_i. $$

Conjetura:

para cualquier $v\in\left[2^n+1,~ 2^{n+1}\right]$ existe (descrito anteriormente) de la secuencia, que $a_{n+2} = v$.

Ejemplos:

$v=10 (n=3)$: secuencia adecuada $0,1,2,4,8,10,...$;

$v=12 (n=3)$: secuencia adecuada $0,1,2,4,8,12,...$;

$v=13 (n=3)$: secuencia adecuada $0,1,2,4,7,13,...$ (cualquier secuencia $0,1,2,4,8,x,...$ es malo);

$v=25 (n=4)$: secuencia adecuada $0,1,2,4,7,13,25,...$;

$v=49 (n=5)$: secuencia adecuada $0,1,2,4,7,14,28,49,...$;

$v=105 (n=6)$: secuencia adecuada $0,1,2,4,8,15,30,60,105,...$;

$v=233 (n=7)$: secuencia adecuada $0,1,2,4,8,16,30,59,117,233,...$;

Pregunta: ¿Cómo demostrar esta conjetura?
(o mostrar contraejemplo: inalcanzable $v$ $n+2$ pasos).

Answer 1

Nuestro enfoque es inductivo, es decir que se supone que ya han hecho las secuencias apropiadas de las longitudes de todos los intervalos de hasta el $[2^{n-1}+1,2^n]$ y quieres ampliar estos anexando un plazo para que las secuencias de las $[2^n+1,2^{n+1}].$

Deje $2^n+1 \le v \le 2^{n+1}$ y considerar los casos en que $v$ es par o impar. En primer lugar si $v=2k$ es incluso entonces tenemos $2^{n-1}+1 \le k \le 2^n$, de modo que podemos seleccionar una secuencia de decisiones $k$ en el número de pasos, y anexar $v=2k$ a, ya que $2k-k=k$ y cualquier secuencia de decisiones $k$ tiene la diferencia de $k=k-0$.

Por otro lado supongamos $v=2k+1$, de modo que $2^{n-1} \le k \le 2^n-1$ (donde la resta de las $1$ aquí es válido desde $v$ es impar y, por tanto,$v<2^{n+1}.$) Añadiendo $1$ a estos términos da $$2^{n-1}+1 \le k+1 \le 2^n.$$ Ahora podemos hacer una secuencia de $k+1$ de la longitud apropiada, y podemos anexar $v$ a, ya que $v-(k+1)=k$ y cualquier secuencia de $k+1$ contiene $1$ y de ahí también la diferencia de $(k+1)-1=k.$