Sequence $\{a_k\}$ is built according to next rule: $$ a_0=0;\\ a_1=1;\\ \forall n\in \mathbb{N} ~ \exists i,j ~ (0\leqslant i<j\leqslant n),\mbox{ so that } a_{n+1}-a_{n} = a_j-a_i. $$
Conjecture:
for any $v\in\left[2^n+1,~ 2^{n+1}\right]$ there exists (described above) sequence, that $a_{n+2} = v$.
Examples:
$v=10 (n=3)$: appropriate sequence $0,1,2,4,8,10,...$;
$v=12 (n=3)$: appropriate sequence $0,1,2,4,8,12,...$;
$v=13 (n=3)$: appropriate sequence $0,1,2,4,7,13,...$ (any sequence $0,1,2,4,8,x,...$ is wrong);
$v=25 (n=4)$: appropriate sequence $0,1,2,4,7,13,25,...$;
$v=49 (n=5)$: appropriate sequence $0,1,2,4,7,14,28,49,...$;
$v=105 (n=6)$: appropriate sequence $0,1,2,4,8,15,30,60,105,...$;
$v=233 (n=7)$: appropriate sequence $0,1,2,4,8,16,30,59,117,233,...$;
Question: How to prove this conjecture?
(or show counterexample: unreachable $v$ for $n+2$ steps).
Our approach is inductive, that is we assume we have already made sequences of appropriate lengths for all the intervals up to $[2^{n-1}+1,2^n]$ and want to extend these by appending one term to get the sequences for $[2^n+1,2^{n+1}].$
Let $2^n+1 \le v \le 2^{n+1}$ and consider the cases where $v$ is even or odd. First if $v=2k$ is even then we have $2^{n-1}+1 \le k \le 2^n$ so that we can select a sequence making $k$ in the right number of steps, and append $v=2k$ to it, since $2k-k=k$ and any sequence making $k$ has the difference $k=k-0$ in it.
On the other hand suppose $v=2k+1$ so that $2^{n-1} \le k \le 2^n-1$ (where the subtraction of $1$ here is valid since $v$ is odd and hence $v<2^{n+1}.$) Adding $1$ to these terms gives $$2^{n-1}+1 \le k+1 \le 2^n.$$ We can now make a sequence for $k+1$ of appropriate length, and we may append $v$ to it, since $v-(k+1)=k$ and any sequence for $k+1$ contains $1$ and hence also the difference $(k+1)-1=k.$