A problem with sequences

Question

I have a problem I don't seem to be able to solve other than by brute force.

Consider the increasing sequences of $n$ positive integer numbers such that all the $n−1$ differences between any two consecutive numbers of the sequence are different from one other and from any number in the sequence.

For example, if we have a sequence of 3 numbers $\{a_1,a_2,a_3\}$, the numbers $a_1, a_2, a_3, (a_2−a_1)$ and $(a_3−a_2)$ must be all different, as in $\{2,3,7\}$, because $2 \neq 3 \neq 7 \neq 3−2 \neq 7−3$.

For each $n$, find the minimum possible value of the sum of all numbers of a sequence.

In the example above, $2+3+7=12$ but $\{1,4,6\}$ has sum $11$, so for $n=3$ the minimum sum is $11$.

Can you find the value for $n=15$? can you find a general formula?

Update 1:

The values I've found are $1,4,11,22,39,63$ for $n=1$ to 6 respectively.

In some cases the sequences with minimum sum are unique. For example, $n=4$ only $\{1,4,6,11\}$ adds up to 22; for $n=5$ only $\{1,5,7,10,16\}$ has sum 39.

For others values of $n$, there are multiple minimal sequences. For $n=3$, besides the sequence in the example above, $\{1,3,7\}$ adds up to 11 as well. For $n=6$ there are 4 sequences whose sum is 63.

For $n=7$ the best I could do is 94 (6 distinct sequences, 2 starting with 3), but I'm not sure it is minimal.

Update 2:

OESIS A005228 (thanks @JwJJJJ) provides sequences that respect the rules, but are not minimal, hence their sum is an upper bound.

For the term $a_n$ of A005228 (as shown by @C Squared in the answer below, thanks):

$0 ≤ a_{n+2} − 2 a_{n+1} + a_n − 1 ≤ 1$

It looks like that for the sum of the first $n$ terms $S_n$:

$0 ≤ S_{n+3} − 3 S_{n+2} + 3 S_{n+1} − S_n − 1 ≤ 1$

Solving the difference equation, we find that the upper bound is:

$\frac {1} {6} (6 − 7 n + 6 n^2 + n^3) ≤ S_n ≤ \frac{1}{3} (2 n + n^3)$

I'm confident one can find a better estimate than $n^3$, but not sure that the exponent could reach as low as 2.

Answer 1

This is not an answer, just a long comment

Edit: I undeleted this just in case. If its not of any substantial use, just let me know.

From playing around with this for a bit, it seems like the first few terms of a minimal sequence would be given by the following (I add a zero term for convenience):$$0,1,3,7,12,18,26,35,45,56,69,83,98,114,131,150$$

Organizing this and looking for some more patterns, we see that

$$ \begin{array}{|c|c|c|c|} \hline n & 0&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\\ \hline a_n & 0 & 1 & 3 & 7 & 12 & 18 & 26 & 35 & 45 & 56 & 69 & 83 & 98 & 114 & 131 & 150\\ \hline a_{n+1}-a_n &1 & \color{blue}{2} & \color{red}4 & \color{red}5 & \color{red}6 & \color{green}8 & \color{green}9 & \color{green}{10} & \color{green}{11} & \color{orange}{13} & \color{orange}{14} & \color{orange}{15} & \color{orange}{16} & \color{orange}{17} & 19 & 20\\ \hline &\color{red}1& \color{blue}2 & \color{red}1 & \color{red}1 & \color{blue}2 & \color{red}1& \color{red}1&\color{red}1&\color{blue}2&\color{red}1&\color{red}1&\color{red}1&\color{red}1&\color{blue}2&\color{red}1&\color{red}1\\ \hline \end{array} $$

The idea is that you want to be able to list every natural number exactly once using the differences of consecutive terms along with the terms in the sequence, so the terms only increase when they are forced to. Interestingly, if we define $b_n=a_{n+1}-a_n$ and investigate $b_{n+1}-b_n$ (the last row of the array) we see that a binary sequence appears, where after $n$ consecutive $\color{red}1$'s, we flip to a $\color{blue}2$.

If we set $c_n=b_{n+1}-b_n$, then we see that, through a crafty oeis search, $$c_n=\begin{cases}2 &\text{ if }n\equiv \frac{m(m+3)}{2}\\ 1&\text{ if else}\end{cases}$$

Working backwards and expanding, we find that $$a_{n+2}=2a_{n+1}-a_n+c_n$$ which gives a solid start at a recursive definition for $a_1=1$ and $a_2=3$. If there is a closed form for $c_n$, then we would be fairly close to being done, but I highly doubt it. Some ideas I was trying for $c_n$ was to either get some function of the type $(-1)^{g(n)}$ in order to flip back and forth between $-1$ and $1$, try and come up with an expression for it in terms of the $\sin$ or $\cos$ functions, or encode $c_n$ in a polynomial.

As a closing observation, if we look at the sum over the first several terms of $a_n$, we get the partial sums given by \begin{array}{|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\\ \hline \sum_{k=1}^{n} a_k & 0 & 1 & 4 & 11 & 23 & 41 & 67 & 102 & 147 & 203 & 272 & 355 & 453 & 567 & 698 & 848\\ \hline \end{array}