Why $a_{n+3}=a_{n+2}+2a_{n+1}-a_n$ for $n\geq8$, where $a_{n+1}$ is the second smallest number that is not the sum of any earlier terms?
In the first part, it is shown that the recursion $a_{n+1}=a_{n}+2a_{n-1}-a_{n-2}$ follows under a certain condition. In the second part, it is shown that the condition is satisfied for $n\geq9$ if $a_0=0$. The other initial conditions will be treated later.
Consider besides the sequence $a_n$, $n\geq0$, the increasing sequences $b_n$ of those numbers that cannot be written as sums of distinct $a_n$ and the sequence $c_n=a_0+...+a_n$. It is also essential to introduce the sets $B^{(n)}\subset\{0,...,c_n-1\}$ of those numbers that cannot be written as sums of distinct $a_i$ with $0\leq i\leq n$.
Clearly, a number $x$ can be written as a sum of certain distinct $a_i$ with $0\leq i\leq n$ if and only if $c_n-x$ can: The summation for $c_n-x$ is taken over the indices that do not appear in the summation for $x$. This means that $t\in B^{(n)}$ if and only if $c_n-t\in B^{(n)}$. $B^{(n)}$ is updated recursively with $a_n$ if we want to determine $a_n$ for large $n$.
I. Assume that for a certain $n$ the elements of $B^{(n)}$ between $b_{n-3}$ and $2a_n$ are exactly
$$b_{n-3},b_{n-2},b_{n-1},c_n-b_{n-1},c_n-b_{n-2},2a_n$$
and that $2a_n=c_n-b_{n-3}$. Furthermore assume that $b_{n-3} < b_{n-2} < b_{n-1}< a_n<c_n-b_{n-1}$. This might seem to be a lot of assumptions, but they are, for example, satisfied for $a_0=0$ and $n=9,10,11,12$.
Then $c_n-b_{n-2}$ is the second smallest number larger than $a_n$ that cannot be written as a sum of distinct integers in ${a_0,...,a_n}$ and we obtain $a_{n+1}=c_n-b_{n-2}$. As now $c_n-b_{n-1}<a_{n+1}$ cannot be written as a sum of any distinct elements of the whole sequence $a_k$, we also have $b_n=c_{n}-b_{n-1}$. Observe that $b_{n-1}<a_n<b_n$. Finally, by definition, $c_{n+1}=c_n+a_{n+1}$ and we also obtain $a_{n+1}<c_{n+1}-b_n$ because this is equivalent to $c_n>b_n$ which is true by $b_n=c_n-b_{n-1}$. Observe that $a_{n+1}=c_n-b_{n-2}$ implies that $2a_{n+1}=c_{n+1}-b_{n-2}$.
To complete the recursion, we must show that the elements of $B^{(n+1)}$ between $b_{n-2}$ and $2a_{n+1}$ are exactly
$$b_{n-2},b_{n-1},b_{n},c_{n+1}-b_{n},c_{n+1}-b_{n-1},2a_{n+1}=c_{n+1}-b_{n-2}.$$
How is $B^{(n+1)}$ obtained from $B^{(n)}$?
a) The elements of the form $x+a_{n+1}$ with $x\in B^{(n)}$ for which $x+a_{n+1}>c_n$ are added to $B^{(n)}$ because they cannot be sums of distinct elements of $\{a_0,...,a_{n+1}\}$.
b) $a_{n+1}$ and the elements $y$ of $B^{(n)}$ such that $y-a_{n+1}$ is not in $B^{(n)}$ are removed from the resulting set because $y-a_{n+1}$ is a sum of distinct elements of
$\{a_0,...,a_{n}\}$ if it is not in $B^{(n)}$.
From these relations we now want to deduce that the elements of $B^{(n+1)}$ between $b_{n-2}$ and $2a_{n+1}$ are exactly
$$b_{n-2},b_{n-1},b_{n},c_{n+1}-b_{n},c_{n+1}-b_{n-1},2a_{n+1}=c_{n+1}-b_{n-2}.$$
At this point, we introduce the additional condition that $b_{n-4}<b_{n-2}-b_{n-3}<b_{n-3}$.
First, this implies that $b_0+a_{n+1},...,b_{n-4}+a_{n+1}$ are between $a_{n+1}$ and $2a_n$ because $b_{n-4}+a_{n+1}<2a_n$ is equivalent to $b_{n-4}+c_n-b_{n-2}<c_n-b_{n-3}$ and therefore to $b_{n-4}<b_{n-2}-b_{n-3}$. As by assumption, there are no elements of $B^{(n)}$ between $a_{n+1}$ and $2a_n$, all these elements are sums of distinct elements of $\{a_0,...a_n\}$. (If $b_0=0$ then $b_0+a_{n+1}=a_{n+1}$ has not to be considered here.) Hence they are not in $B^{(n+1)}$ either. Hence also their "complements" $c_n-b_0-a_{n+1},...,c_n-b_{n-4}-a_{n+1}$ are not in $B^{(n)}$, so
$c_n-b_0,...,c_n-b_{n-4}$, i.e. the elements of $B^{(n)}$ above $2a_n=c_n-b_{n-3}$ are not in $B^{(n+1)}$. By construction, $b_n=c_n-b_{n-1}$ remains in $B^{(n+1)}$, but $a_{n+1}=c_n-b_{n-2}$ is not in that set. What about $2a_n$?
We have $2a_n-a_{n+1}=c_n-b_{n-3}-(c_n-b_{n-2})=b_{n-2}-b_{n-3}$ and therefore, by the above additional condition, it is not in $B^{(n)}$ and hence $2a_n$ is not in $B^{(n+1)}$. Finally, we must treat $b_j+a_{n+1}$, $j=n-3,...,n$ and $2a_{n+1}$.
The latter is in $B^{(n+1)}$, because by construction $a_{n+1}$ is in $B^{(n)}$.
We have $b_{n-3}+a_{n+1}$ (which is smaller than $c_n$) not in $B^{(n)}$, because $c_n-b_{n-3}-a_{n+1}=b_{n-2}-b_{n-3}$ is not. Hence it is also not in $B^{(n+1)}$.
$b_{n-2}+a_{n+1}=c_n$ is not in $B^{(n)}$. $b_{n-1}+a_{n+1}=c_{n+1}-b_n$ is in $B^{(n+1)}$ and so is $b_{n}+a_{n+1}=c_{n+1}-b_{n-1}$. This proves that the elements of $B^{(n+1)}$ between $b_{n-2}$ and $2a_{n+1}$ are the ones listed above and completes the recursive step.
This shows that if the assumptions from the beginning for a certain $n=n_0$ are satisfied and if the additional condition holds for all $n\geq n_0$ then we have for all $n\geq n_0$
$$b_n=c_n-b_{n-1},\ a_{n+1}=c_n-b_{n-2},\ c_{n+1}=c_n+a_{n+1}.$$
Eliminating $a_{n+1}$ from these relations, we find $c_n=b_n+b_{n-1}$ and $c_{n+1}=2c_n-b_{n-2}$. Eliminating now $c_n$, we find $b_{n+1}=b_n+2b_{n-1}-b_{n-2}$.
So the sequence $b_n$ satisfies the recursion we want. This carries over to the sequence $c_n$ because $c_n=b_n+b_{n-1}$ and to the sequence $a_n$ because
$a_n=c_n-c_{n-1}$. This completes the first part.
II. The last example shows that there can be no general proof (i.e. for all initial conditions) that after a while, the sequence $a_n$ will satisfy the recursion $a_n=a_{n-1}+2a_{n-2}-a_{n-3}$. For the initial condition of the original sequence ($a_0=0$) it is shown here using finitely many computations that $a_n$ does satisfy the recursion for $n\geq9$.
We calculate the sequences $a_n$, $b_n$, $c_n$ ( see part I for their definitions) up to $n=13$. I used pari/gp, but in pricinple, it could be done by hand if one uses the updating procedure for $B^{(n)}$ from part I. It turns out that $2a_n-a_{n+1}$ is always a sum of distinct integers in $\{a_0,...,a_n\}$ except for $n=5$. The results for $n=6,...,13$ are
$$\begin{array}{|r|r|r|r|r|r|r|r|r|}\hline
n& 6& 7& 8& 9& 10& 11& 12& 13\\\hline
a_n& 33& 38& 86& 162& 284& 522& 928& 1688\\\hline
b_n& 36& 76& 122& 238& 406& 760& 1334& 2448\\\hline
c_n& 74&112& 198& 360& 644& 1166& 2094& 3782\\\hline
b_n-b_{n-1}-b_{n-2}& -5& 14& 10& 40& 46& 116& 168& 354\\\hline
2b_{n-1}-b_n& 16& -4& 30& 6& 70& 52& 186& 220\\\hline
\delta_n& -12& 3& 0& 0& 0& 0& 0& 0\\\hline
\varepsilon_n& 2&-21& 0&33& -12& 0&0& 0\\\hline
\end{array}$$
Here $\delta_n=b_n-b_{n-1}-2b_{n-2}+b_{n-3}$, $\varepsilon_n=a_n-a_{n-1}-2a_{n-2}+a_{n-3}$. We list $b_n-b_{n-1}-b_{n-2}$ and $2b_{n-1}-b_n$, because the additional condition necessary for the first part is $b_{n-4}<b_{n-2}-b_{n-3}<b_{n-3}$.
For $n_0=13$, we also list the elements of $B^{(n_0)}$ between $b_{n_0-3}$ and
$2a_{n_0}$:
$$406, 760, 1334, 2448, 3022, 3376.$$
They are $b_{n_0-3},b_{n_0-2},b_{n_0-1},c_{n_0}-b_{n_0-1},c_{n_0}-b_{n_0-2},2a_{n_0}$ as needed in the beginning of part I.
We have $2a_{n_0}=c_{n_0}-b_{n_0-3}$ and the elements are ordered as needed.
Finally, we have $b_{n_0-4}<b_{n_0-2}-b_{n_0-3}<b_{n_0-3}$, i.e. the additional condition necessary for part I to work because $b_{n_0-2}-b_{n_0-3}-b_{n_0-4}>0$ and $2b_{n_0-3}-b_{n_0-2}>0$. All this can be checked in the above table.
Part I shows that then all the conditions (except maybe the last inequalities) are also satisfied for $n=n_0+1=14$ instead of $n_0$ and that
$$(1)\ \ \ b_{n}=c_{n}-b_{n-1},\ a_{n+1}=c_{n}-b_{n-2},\ c_{n+1}=c_{n}+a_{n+1}$$
for $n=n_0$.
The table shows that we also have $b_{n_0-3}<b_{n_0-1}-b_{n_0-2}<b_{n_0-2}$. Therefore, we can also proceed to $n=n_0+2$ and to $n=n_0+3$ and all the conditions hold, except maybe the inequalities. We have seen at the end of part I, that the relations (1) for $n_0$ and $n_0+1$ imply that the sequence $b_n$ satisfies the recursion
$$(2)\ \ \ \ x_{n+1}=x_n+2x_{n-1}-x_{n-2}$$
for $n=n_0$.
Hence this is already the case for $b_n$, $n=n_0$ and $n_0+1$. We had checked it beforehand for $n=7,...,n=n_0-1$ in the table. As a consequence, the sequences $d_n=b_n-b_{n-1}-b_{n-2}$ and $e_n=2b_{n-1}-b_n$ sastisfy the recursion (2) already for $n=9,...,n=n_0+1$.
Now observe that any sequence solution of (2) such that $0<x_{k-2}<x_{k-1}<x_{k}$ for a certain $k$ also satisfies $x_k<x_{k+1}$ because $x_{k+1}-x_k=2x_{k-1}-x_{k-2}>0$. Hence $0<x_{k-1}<x_{k}<x_{k+1}$. Now as seen above, $d_n$ and $e_n$ satisfy the recursion for $n=n_0$ and $n=n_0+1$ and in the table, we see that $0<d_{n_0-2}<d_{n_0-1}<d_{n_0}$ and $0<e_{n_0-2}<e_{n_0-1}<e_{n_0}$. The choice of $n_0$ is motivated by this fact. Hence first, $0<d_{n_0-1}<d_{n_0}<d_{n_0+1}$ and then $0<d_{n_0}<d_{n_0+1}<d_{n_0+2}$ and similarly, $0<e_{n_0}<e_{n_0+1}<e_{n_0+2}$. In particular, $d_{n_0+1},d_{n_0+2},e_{n_0+1},e_{n_0+2}$ are positive.
This allows to proceed to higher and higher $n$: All conditions necessary for
part I to work are always satisfied. Therefore, the recursion (2) for $b_n$
is satisfied for all $n\geq 7$! Since $c_n=b_n+b_{n-1}$ and $a_n=c_n-c_{n-1}$ at least for $n\geq n_0$, the recursion (2) holds for $a_n$ and all $n\geq n_0+2$, at least. The table and the calculations for $n=13,14$ mentioned above, which yield $a_{14},a_{15}$, show that it is actually true for $n\geq10$.
III. The same method works for all the examples, except of course, the last one. The third and
fifth example are actually the same as the first and second, respectively, except for the first
term.
In the second example($a_0=1$), we proceed as for the first one (see I. and II.). I just put the results of the calculations for $n=6,...,13$ $$\begin{array}{|r|r|r|r|r|r|r|r|r|}\hline n&6& 7& 8& 9& 10& 11& 12& 13\\\hline a_n& 53& 61& 138& 260& 456& 838& 1490& 2710\\\hline b_n& 58& 122& 196& 382& 652& 1220& 2142& 3930\\\hline c_n& 119& 180& 318& 578& 1034& 1872& 3362& 6072\\\hline b_n-b_{n-1}-b_{n-2}& -8& 22& 16& 64& 74& 186& 270& 568\\\hline 2b_{n-1}-b_n& 26& -6& 48& 10& 112& 84& 298& 354\\\hline \delta_n& -19& 4& 0& 0& 0& 0& 0& 0\\\hline \varepsilon_n& 3& -34& 0& 53& -19& 0& 0& 0\\\hline \end{array}$$ Here again $\delta_n=b_n-b_{n-1}-2b_{n-2}+b_{n-3}$, $\varepsilon_n=a_n-a_{n-1}-2a_{n-2}+a_{n-3}$ and we list $b_n-b_{n-1}-b_{n-2}$ and $2b_{n-1}-b_n$, because the additional condition necessary is $b_{n-4}<b_{n-2}-b_{n-3}<b_{n-3}$. For $n_0=13$, we also list the elements of $B^{(n_0)}$ between $b_{n_0-3}$ and $2a_{n_0}$: $$652, 1220, 2142, 3930, 4852, 5420.$$ They are $b_{n_0-3},b_{n_0-2},b_{n_0-1},c_{n_0}-b_{n_0-1},c_{n_0}-b_{n_0-2},2a_{n_0}$ as in part I. The remaining considerations are as for the first example.
Also in the fourth example ($a_0=3$), we proceed as for the first one. Here, we have to calculate until $n=15$ in order to have three subsequent increasing values for $b_n-b_{n-1}-b_{n-2}$ and $2b_{n-1}-b_n$. The resulte for $n=8,...,15$ are $$\begin{array}{|r|r|r|r|r|r|r|r|r|}\hline n& 8& 9& 10& 11& 12& 13& 14& 15\\\hline a_n& 167& 313& 548& 1007& 1790& 3256& 5829& 10551\\\hline b_n& 235& 459& 783& 1466& 2573& 4722& 8402& 15273\\\hline c_n& 381& 694& 1242& 2249& 4039& 7295& 13124& 23675\\\hline b_n-b_{n-1}-b_{n-2}& -9& 31& 21& 78& 89& 224& 324& 683\\\hline 2b_{n-1}-b_n& 26& -10& 57& 11& 135& 100& 359& 424\\\hline \delta_n& -26& 14& 0& 0& 0& 0& 0& 0\\\hline \varepsilon_n& 0& 64& -26& 0& 0& 0& 0& 0\\\hline \end{array}$$ Again for $n_0=15$, we list the elements of $B^{(n_0)}$ between $b_{n_0-3}$ and $2a_{n_0}$: $$2573, 4722, 8402, 15273, 18953, 21102.$$ The rest is as for the above example and the first example. Observe that here, the indices of the sequence $b_n$ have been shifted to have $b_{n-1}<a_n<b_n$.
IV. The last example is quite different. Every sixth value of $n$, we have that $2a_n-a_{n+1}$
is in $B^{(n)}$, i.e. not a sum of distinct elements of $\{a_0,...,a_n\}$.
Unfortunately the condition necessary for part I to work is also not satisfied for certain of the remaining
$5/6$-th of the steps as we will see. This requires modifications of the considerations
of part I.
First, we calculate up to $n=7$:
$$\begin{array}{|r|r|r|r|r|r|r|r|r|}\hline
n&0& 1& 2& 3& 4& 5& 6& 7\\\hline
a_n&2& 3& 6& 10& 17& 31& 55& 79\\\hline
b_n&1& 4& 7& 14& 24& 45& 62& 141\\\hline
c_n& 2& 5& 11& 21& 38& 69& 124& 203\\\hline
b_n-b_{n-1}-b_{n-2}&*& *& 2& 3& 3& 7& -7& 34\\\hline
2b_{n-1}-b_n&*& -2& 1& 0& 4& 3& 28& -17\\\hline
\end{array}$$
Here we have for convenience omitted 0 from the sets $B^{(n)}$ and start with $b_0=1$.
Now we proceed by induction, but a complicated one.
We summarize the situation at $n=7$ with $x=b_6=62$ and $y=b_5=45$ as parameters.
We perform six steps (five of them almost as in part I) and show that we arrive at the same situation
except for other values of $x,y$.
Then by induction, we obtain that the complete sequences $a_n,b_n,c_n$ are obtained by repeting
these six steps. The recursion
$a_{n+12}=31a_{n+6}-4a_n$ follows.
We suppose that for some $n$ the numbers in $B^{(n)}$ between $b_{n-3}$ and $2a_n$ are
$$b_{n-3},b_{n-2}=y,b_{n-1}=x, 3x-y,2a_n.$$
We also suppose that $a_n=2x-y$ and $c_n=4x-y$. If we assume $b_{n-3}<y$ then
the list is in ascending order because of $y<x$. In the sequel, the expressions of all quantities
in terms of $x,y$ allow to compare them just using $y<x$. These details are omitted. Finally, we assume that
$b_{n-4}<b_{n-2}-b_{n-3}<b_{n-3}$ and that $b_{n-4}<b_{n-1}-b_{n-2}<b_{n-3}$.
We conclude that $2a_n=c_n-b_{n-2}$. So the situation is different from that in the beginning
of part I. We also conclude that $c_{n-1}=c_n-a_n=2x$.
Observe that this situation is given for $n=7$ as can be verified in the above table.
- As in part I, we find $b_n=3x-y$ and $a_{n+1}=2a_n=4x-2y,$ hence $c_{n+1}=8x-3y.$
As in part I, we update $B^{(n)}$. The numbers $b_j+a_{n+1}$, $j=0,...,n-4$, are not in $B^{(n)}$,
because their complements are $c_{n}-b_j-a_{n+1}=b_{n-2}-b_j$ and hence between
$b_{n-2}-b_{n-4}>b_{n-3}$ and $b_{n-2}$. $b_{n-3}+a_{n+1}$ is not in $B^{(n)}$ because its
complement $c_{n}-b_{n-3}-a_{n+1}=b_{n-2}-b_{n-3}$ is not. This implies that
$b_j+a_{n+1}$, $j=0,...,n-3$, are not in $B^{(n+1)}$. The above fact that $c_{n}-b_j-a_{n+1}$
$j=0,...,n-3$, is not in $B^{(n)}$ also implies that the corresponding $c_n-b_j$
are not in $B^{(n+1)}$. Again, $b_n=b_{n-1}+a_{n+1}$ is in $B^{(n+1)}$, but $a_{n+1}$ is removed.
$b_{n-2}+a_{n+1}=4x-y=c_n$ is not in $B^{(n+1)}$, but
$b_{n-1}+a_{n+1}=5x-2y=c_{n+1}-b_n$ and $b_{n}+a_{n+1}=7x-3y=c_{n+1}-b_{n-1}$ are in $B^{(n)}$ and
so is $2a_{n+1}=8x-4y$.
The elements of $B^{(n+1)}$ between $b_{n-2}$ and $2a_{n+1}$ are now $$\begin{array}{|r|r|r|r|r|r|r|} b_{n-2}&b_{n-1}&b_{n}&c_{n+1}-b_n&c_{n+1}-b_{n-1}&2a_{n+1}\\\hline y&x&3x-y&5x-2y&7x-3y&8x-4y \end{array}.$$ We have $c_{n+1}=8x-3y$ and hence $2a_{n+1}=c_{n+1}-b_{n-2}$. We had assumed that $b_{n-4}<b_{n-1}-b_{n-2}<b_{n-3}$. - Before the beginning of the second step, the situation is therefore as before the
step in part I, except that $b_{n-4}<b_{n-1}-b_{n-2}<b_{n-3}$ here.
We proceed (almost) as in part I or in the above first step, except that
$b_{n-3}+a_{n+2}$ has to be treated apart. We omit the details. We arrive at
the following situation before step 3.
The elements of $B^{(n+2)}$ between $b_{n-1}$ and $2a_{n+2}$, $a_{n+2}=7x-3y$ are now $$\begin{array}{|r|r|r|r|r|r|r|} b_{n-1}&b_{n}&b_{n+1}&c_{n+2}-b_{n+1}&c_{n+2}-b_{n}&2a_{n+2}\\\hline x&3x-y&5x-2y&10x-4y&12x-5y&14x-6y \end{array}.$$ We have $c_{n+2}=15x-6y$ and hence $2a_{n+2}=c_{n+2}-b_{n-1}$. Observe that $c_{n+2}=3b_{n+1}$ and hence $c_{n+2}-b_{n+1}=2b_{n+1}$! This will be crucial later. Here we have that $b_n-b_{n-1}=2x-y>x=b_{n-1}$. - Before the beginning of the third step, the situation is therefore as before the
step in part I, except that $b_{n}-b_{n-1}>b_{n-1}$ here.
We proceed (almost) as in part I or in the above steps. The treatment of $b_j+a_{n+3}$ is
even simpler than before. We omit the details. We arrive at
the following situation before step 4 which is as before the step in part I.
The elements of $B^{(n+3)}$ between $b_{n}$ and $2a_{n+3}$, $a_{n+3}=c_{n+2}-b_{n}=12x-5y$, are now with $c_{n+3}=27x-11y=2a_{n+3}+b_{n}$: $$\begin{array}{|r|r|r|r|r|r|r|} b_{n}&b_{n+1}&b_{n+2}&c_{n+3}-b_{n+2}&c_{n+3}-b_{n+1}&2a_{n+3}\\\hline 3x-y&5x-2y&10x-4y&17x-7y&22x-9y&24x-10y \end{array}.$$ We have $b_{n+1}-b_{n}=2x-y$ again and this has been seen to be between $b_{n-1}$ and $b_n$. - So we can proceed as in part I (details omitted). We arrive at the following situation before
step 5:
The elements of $B^{(n+4)}$ between $b_{n+1}$ and $2a_{n+4}$, $a_{n+4}=c_{n+3}-b_{n+1}=22x-9y$, are now with $c_{n+4}=49x-20y=2a_{n+4}+b_{n+1}$: $$\begin{array}{|r|r|r|r|r|r|r|} b_{n+1}&b_{n+2}&b_{n+3}&c_{n+4}-b_{n+3}&c_{n+4}-b_{n+2}&2a_{n+4}\\\hline 5x-2y&10x-4y&17x-7y&32x-13y&39x-16y&44x-18y \end{array}.$$ Observe that now $b_{n+2}=2b_{n+1}$ and the situation is different from all the other steps. - We find as before $b_{n+4}=c_{n+4}-b_{n+3}=32x-13y$ and
$a_{n+5}=c_{n+4}-b_{n+2}=39x-16y$, so that
$c_{n+5}=88x-36y$. By chance, $c_{n+5}=4a_{n+4}$.
The numbers $b_j+a_{n+5}$, $j=1,...,n$, are not in
$B^{(n+4)}$, because their complements $c_{n+4}-b_j-a_{n+5}=b_{n+2}-b_j$ are
between $b_{n+2}-b_{n+1}=b_{n+1}$ and $b_{n+2}$ and hence not in $B^{(n+4)}$.
Therefore $b_j+a_{n+5}$, $j=1,...,n$ are also not in $B^{(n+5)}$.
Contrary to all other steps, $b_{n+1}+a_{n+5}$ is in $B^{(n+4)}$ and thus also in
$B^{(n+5)}$, because it complement $b_{n+2}-b_{n+1}=b_{n+1}$ is in $B^{(n+4)}$.
Observe that $b_{n+1}+a_{n+5}=2a_{n+4}$. As before, $c_{n+4}-b_j$, $j=1,...,n$,
are not in $B^{(n+5)}$. We just saw that $c_{n+4}-b_{n+1}=2a_{n+4}$ is in
$B^{(n+5)}$. $b_{n+2}+a_{n+5}=c_{n+4}$ is not in $B^{(n+5)}$.
$b_{n+3}+a_{n+5}=c_{n+5}-b_{n+4}$ and $b_{n+4}+a_{n+5}=c_{n+5}-b_{n+3}$ are
in $B^{(n+5)}$ as is $2a_{n+5}$.
The elements of $B^{(n+5)}$ between $b_{n+2}$ and $2a_{n+5}$, $a_{n+5}=c_{n+4}-b_{n+2}=39x-16y$, are now with $c_{n+5}=88x-36y=2a_{n+5}+b_{n+2}$: $$\begin{array}{|r|r|r|r|r|r|r|r|} b_{n+2}&b_{n+3}&b_{n+4}&2a_{n+4}&c_{n+5}-b_{n+4}&c_{n+5}-b_{n+3}&2a_{n+5}\\\hline 10x-4y&17x-7y&32x-13y&44x-18y&56x-23y&71x-29y&78x-32y \end{array}.$$ We will use that $b_{n+4}-b_{n+3}=15x-6y$ between $b_{n+2}$ and $b_{n+3}$. - This final step is different because of the additional element $2a_{n+4}$ in $B^{(n+5)}$ between $b_{n+2}$ and $2 a_{n+5}$. We find $b_{n+5}=2a_{n+4}=44x-18y$ and $a_{n+6}=c_{n+5}-b_{n+4}=56x-23y$ so that $c_{n+6}=144y-59y$. Updating $B^{(n+5)}$, the elements $b_j+a_{n+6}$, $j=1,...,n+2$, are not in $B^{(n+5)}$ because their complements $c_{n+5}-b_j-a_{n+6}=b_{n+4}-b_j$ are between $b_{n+4}-b_{n+2}>b_{n+3}$ and $b_{n+4}$. Hence they are also not in $B^{(n+6)}$. For $j=n+3$, we find the complement $b_{n+4}-b_{n+3}\in]b_{n+2},b_{n+3}[$. Therefore $b_{n+3}+a_{n+6}$ is also not in $B^{(n+6)}$. $b_{n+4}+a_{n+6}=c_{n+5}$ is not in $B^{(n+6)}$. $2a_{n+4}+a_{n+6}=100x-41y=c_{n+6}-b_{n+5}$ is in $B^{(n+6)}$ and so is $2a_{n+6}$. $c_{n+5}-b_{n+3}$ is removed, because $c_{n+5}-b_{n+3}-a_{n+6}=15x-6y$ is between $b_{n+2}$ and $b_{n+3}$ and hence not in $B^{(n+5)}$. $2a_{n+5}$ is removed, because $2a_{n+5}-a_{n+6}=c_{n+5}-b_{n+2}-(c_{n+5}-b_{n+4})=b_{n+4}-b_{n+2}$ is between $b_{n+3}$ and $b_{n+4}$ and hence not in $B^{(n+5)}$.
As a result after six steps, the elements of $B^{(n+6)}$ between $b_{n+3}$ and $2a_{n+6}$, $a_{n+6}=c_{n+5}-b_{n+4}=56x-23y$, are now with $c_{n+6}=144x-59y=2a_{n+6}+b_{n+4}$: $$\begin{array}{|r|r|r|r|r|r|r|r|} b_{n+3}&b_{n+4}&b_{n+5}&c_{n+6}-b_{n+5}&c_{n+6}-b_{n+4}=2a_{n+6}\\\hline 17x-7y&32x-13y&44x-18y&100x-41y&112x-46y \end{array}.$$ We verify that $a_{n+6}=2b_{n+5}-b_{n+4}$, $c_{n+6}-b_{n+5}=3b_{n+5}-b_{n+4}$, $4b_{n+5}-b_{n+4}=144x-59y=c_{n+6}$, that $b_{n+5}>b_{n+4}>b_{n+3}$, $b_{n+5}<2b_{n+4}$, that $b_{n+4}-b_{n+3}=15x-6y$ is between $b_{n+2}=10x-4y$ and $b_{n+3}$ and that $b_{n+5}-b_{n+4}=12x-5y$ also is between $b_{n+2}$ and $b_{n+3}$. Therefore with $n'=n+6$ at the place of $n$ and $x'=b_{n+5}$, $y'=b_{n+4}$ at the place of $x=b_{n-1},y=b_{n-2}$, respectively, we have the same situation as before the first step. This finally completes the recursion.
By induction, these 6 steps are repeated infinitely often and determine the whole sequences $a_k,b_k,c_k$. In order to deduce the recursive relations $x_{k+12}=31x_{k+6}-4x_k$ for these sequences, we first introduce the vectors $v_k=(b_{6k},b_{6k-1})^T$, $k=1,2,3,...$. Then $v_1=(b_6,b_5)^T$ and if $v_k=(x,y)^T$ then $v_{k+1}=(x',y')^T=(44x-18y,32x-13y)^T=A(x,y)^T=Av_k$ with the matrix $$A=\begin{pmatrix}44&-18\\32&-13\end{pmatrix}.$$ Its characteristic polynomial is $\lambda^2-31\lambda+4$. By the Cayley-Hamilton Theorem, we conclude that $A^2-31A+4I=0$. Applying this to $v_k$ yields $v_{k+2}=31v_{k+1}-4v_k$, which means that $b_{6k+12}=31b_{6k+6}-4b_{6k}$ and $b_{6k+11}=31b_{6k+5}-4b_{6k-1}$ for all $k=1,2,...$.
If we put $x=b_{6k}$, $x'=b_{6k+6}$, $x''=b_{6k+12}$ we have $x''=31x'-4x$ and similarly for $y=b_{6k-1}$, $y'=b_{6k+5}$, $y''=b_{6k+11}$, we have $y''=31y'-4y$. Now, as shown in the six steps, for every $j\in\{1,2,3,4\}$, the quantity $b_{6k+j}$, $b_{6k+6+j}$, $b_{6k+12+j}$ is a linear combination of $(x,y)$, $(x',y')$, $(x'',y'')$, respectively, and the coefficients are the same in the three cases. This implies that we also have $b_{6k+12+j}=31b_{6k+6+j}-4b_{6k+j}$ for $j=1,2,3,4$ In the same way, the six steps show that for each $j\in\{0,\ldots,5\}$, $a_{6k+j}$ is a linear combination of $b_{6k}$ and $b_{6k-1}$ for every $k$ with coefficients independent of $k$. This implies that also $a_{m+12}=31a_{m+6}-4a_{m}$ for all $m\geq6$. For the remaining $m=1,...,5$, the relation is shown by a calculating up to $n=17$. For the sequence $c_m$, we proceed in the same way. This completes the treatment of the last example.
V. An open question for me is whether for all initial conditions, $a_n$ satisfies a certain recursion for sufficiently large $n$ and whether it is always one of the two in the examples of the question. In numerous examples I tried, always one of the two known recursions occurred. Any reports of initial conditions not leading to one of the two recursions is welcome!
Observe that the largest root of $\lambda^{12}-31\lambda^6+4=0$ is $\lambda_b=1.77...$ and therefore slightly smaller than the largest root $\lambda_a=1.80...$ of $\lambda^3-\lambda^2-2\lambda+1=0$. The growth of $a_n$ is therefore not as fast in the last example as in the other ones.
The steps in all the examples also show that the set $B^{(n)}$ of numbers below $a_0+\cdots+a_n$ that cannot be written as sums of distinct elements of $\{a_0,...a_n\}$ has a number of elements of the order $2n$. This is much less than the number of numbers that can be written as such sums which is of the order $\lambda_a^n$ or $\lambda_b^n$ in examples 1-5 or example 6, respectively.