Convergence of $a_{n+2}^3+a_{n+2}=a_{n+1}+a_n$
There might be an easier and more elegant solution, but this should work.
First observe that: $$ a_{n+1}+a_{n}=a_{n+2}^3+a_{n+2}\geq2\sqrt{a_{n+2}^4}=2a_{n+2}^2\geq4a_{n+2}-2 $$ Here I used the AM-GM inequality and the simply fact that $(a_{n+2}-1)^2\geq0$. Hence, $a_n\leq b_n$ with $$ b_{n+2}=\frac{b_{n+1}+b_{n}+2}{4}\\ b_{0,1}=a_{0,1} $$
Now, the recurrence equation for this reads: $$ b_{n}=1 + (\tfrac{1 - \sqrt{17}}{8})^n C_1 + (\tfrac{1 + \sqrt{17}}{8})^n C_2 $$ Since $|\tfrac{1 \pm \sqrt{17}}{8}|<1$ we can deduct that $b_n\to1$ for $n\to\infty$. So together with $1\leq a_n\leq b_n$ we can conclude that $a_n\to1$.
Initial remarks :
a) In case of convergence to a limit $L$, we would have $L^3+L=L+L$, with solutions $L=-1,0,1$.
b) We assume that, up to a switching operation, $a_1 \leq a_0.$
We are going to show that $a_n$ is convergent with limit $L=1.$
First step : the recurrence "definition"
$$a_{n+2}^3+a_{n+2}=a_{n+1}+a_n$$
of sequence $a_n$, rewritten under the form
$$ f(a_{n+2})=a_{n+1}+a_n \ \ \text{where} \ \ f(x):=x^3+x, \tag{0}$$
cannot be considered as a "definition" unless it has been proved that $a_{n+2}$ is determined in a unique way by (1). This will be the consequence of
Lemma $0$ : $f$ is a bijection.
Proof : $f'(x)=3x^2+1\geq 1>0$. Thus function $f$ is strictly increasing, therefore is bijective. $\square$.
Let us write (0) under the form :
$$a_{n+2}=f^{-1}(a_{n+1}+a_n)\tag{1}$$
Lemma $1$ : $a_n \geq 1$ whatever $n$.
Proof : by recurrence, using the fact that $f^{-1}(2,+\infty)=(1,\infty). \ \square$
Lemma $2$ : for any $x \geq 0, f(x) \geq 2x^2$
Proof by observing that $x^3+x-2x^2=x(x-1)^2 \geq 0. \ \square$
As a consequence of lemma $2$,
$$f^{-1}(u) \leq \sqrt{\tfrac{u}{2}}.\tag{2}$$
Thus, for any $n$,
$$a_{n+2} \leq \sqrt{\tfrac{a_{n+1}+a_n}{2}}\tag{3}.$$
Let us define an auxiliary sequence $b_n$ by
$$b_n=a_n-1\tag{4}$$
Our objective is thus to prove that $b_n \to 0$. (3) becomes :
$$b_{n+2} \leq \sqrt{1+\tfrac{b_{n+1}+b_n}{2}}-1\tag{5}.$$
Lemma $3$ : $b_n$ is a positive decreasing sequence bounded from below by $0$.
Proof : By recurrence. True (see initial remark b)) for the two first elements. For the general case, use in (5) the (classical) result :
$$\text{for all} \ x>0, \ \ \ 1 \leq \sqrt{1+x}\leq 1+\tfrac{x}{2}.\tag{5}$$
$\ \square$
Lemma $3$ allows to conclude that $a_n$ is a positive decreasing sequence bounded from below by $1$. Thus $a_n$ converges to a limit which is necessarily $L=1$ (see initial remark a)).
Remark about the rate of convergence : I have observed that sequence $b_n$ behaves asymptotically as a geometrical sequence with ratio $r=0.640388...$ whatever the initial values $a_0$ and $a_1$. This value is in fact equal to the value $(1+\sqrt{17})/8$ found for one of the roots of characteristic equation found by @maxmilgram. I have no true proof of this fact.
This is the first time I see this type of recusrion relation where the next term in the sequence is not given directly but instead a function of it is given. This makes the problem particularly interesting (for me, at least).
Hence an uncommon approach seems to be justified. I am going to relate convergence to the stability of simple (constant) solutions.
1. Layout of the solution
Let us start with the observation that there are three constant solutions of the recursion
$$a_{n+2}^3+a_{n+2}=a_{n+1}+a_{n}\tag{1}$$
These are given by the roots of the equation
$$z^3+z = z + z\tag{2}$$
that is
$$s_1 = \{a_n = - 1\}$$ $$s_2 = \{a_n = 0\}\tag{3}$$ $$s_3=\{a_n = + 1\}$$
We show below that $s_1$ and $s_3$ are stable solutions, and $s_2$ is unstable.
A stable solution is definied as one where a sufficiently small deviation from the solution is damped out for $n\to\infty$. In an unstable solution, in contrast, small deviations increase so that the sequence departs from the solution for large $n$.
Depending on the initial values $a_1$ and $a_2$ (except the singular case $a_1 = a_2=0$) the solution approches one of the stable solutions. This statement is equivalent to saying the sequence is convergent.
2. Stability analysis
Applying the common procedure we let
$$a_k= s + \delta_k\tag{4}$$
where $s$ is the constant solution to be studied and $\delta_k$ is a small deviation. Small is defined as $|\delta_k|<<1$
Inserting $(4)$ into $(1)$ gives
$$(s + \delta_{n+2})^3 +(s + \delta_{n+2})= (s + \delta_{n+1})+(s + \delta_{n}) $$
Expanding the 3rd power and keeping only the linear term in $\delta$ gives
$$s^3 + 3 s^2 \delta_{n+2} +(s + \delta_{n+2})= (s + \delta_{n+1})+(s + \delta_{n}) $$
Observing that $s$ solves $(2)$ this can be simplified to
$$(1+3 s^2)\delta_{n+2} =\delta_{n+1}+\delta_{n}\tag{5} $$
This is a linear recursion equation which can be solved by standard methods.
In the case $s=0$ $(5)$ reduces to the Fibonacci recursion which is known to diverge, in agreement with our identifying this solution as unstable.
For the cases $s=\pm 1$ I leave as an exercise to the reader to show that the solutions $\delta_n \to 0$ for $n\to\infty$ and arbitrary but suffciently small initial conditions.
3. Numerical study (in Mathematica)
As an example of how to treat the recursion $(1)$ numerically I used these commands in Mathematica
a[1] := 1; a[2] := 0;
Table[a[n] =
z /. FindRoot[z^3 + z == a[n - 1] + a[n - 2], {z, 0}], {n, 3, 20}]
{0.682328, 0.53187, 0.765544, 0.794984, 0.879716, 0.913186, 0.946085, \
0.963849, 0.977093, 0.985069, 0.990473, 0.993857, 0.996071, 0.997477, \
0.998385, 0.998965, 0.999337, 0.999575}
Explanation: in the first line the initial values are defined. The FindRoot command solves for $z$ and thus finds the value of $a_{n+2}$ for the given right Hand side, i.e. as a function of $a_{n+1}$ and $a_{n}$. The Table command provides a list of the first few terms of the sequence.
We can see that with these initial conditions the values approach the stable solution $a_n=+1$
In this case
a[1] := -0.1; a[2] := 0;
Table[a[n] =
z /. FindRoot[z^3 + z == a[n - 1] + a[n - 2], {z, 0}], {n, 3, 20}]
{-0.0990289, -0.0980852, -0.19023, -0.268877, -0.396685, -0.522729, \
-0.647697, -0.749461, -0.828489, -0.884939, -0.924151, -0.950462, \
-0.967888, -0.979268, -0.986656, -0.991426, -0.994498, -0.996472}
the stable solution $a_n=-1$ is approached.