$g(x):=\cos x-x\Rightarrow g(-{\pi\over 3})>0 ,g({\pi\over 3})<0$. As $g$ is continuous over $\mathbb{R}$, $g$ vanishes somewhere between $(-{\pi\over 3},{\pi\over 3})$. Note that as $\pi\gt 3$, $g$ can't vanish outside $(-{\pi\over 3},{\pi\over 3})$ otherwise it would mean $|\cos (x)|\gt 1$ for some $x$. Also notice $|{d\over dx}\cos x|=|\sin x|< {1\over \sqrt 2}\;\forall\; x\in (-{\pi\over 3},{\pi\over 3})$. As $\cos x$ is positive in $({-\pi\over 3},{\pi\over 3})$, the sole solution of $\cos x=x$, let's call it $\alpha$, must lie in the interval $(0,{\pi\over 3})$ (we can rule out $x=0$ by direct checking).
As cosine is differentiable over $(0,{\pi\over 3})$, using $\mathtt{MVT}$ for $x,y \in (0,{\pi\over 3}) \text{ with } x\neq y$ we see that $\exists c: x< c< y$ and $\cos x-\cos y=(x-y)\sin c\Rightarrow |\cos x-\cos y|\le \left({1\over\sqrt{2}}\right)|x-y|$. As $|\cos x|\le1$, for $n>1,x_n\in(0,{\pi\over 3})$. Therefore for $n>1$ we have
$$|\alpha-x_{n}|=|\cos\alpha-\cos x_{n-1}|\le\left({1\over\sqrt{2}}\right)|\alpha-x_{n-1}|\le\left({1\over\sqrt{2}}\right)^2|\alpha-x_{n-2}|\\
\le...\le\left({1\over\sqrt{2}}\right)^{n}|\alpha-x_0|:=\left({1\over\sqrt{2}}\right)^n\delta
\cdots(1)
$$
So, for $m>n>1$
$$|x_m-x_n|\le|\alpha-x_m|+|\alpha-x_n|\le\left[\left({1\over\sqrt{2}}\right)^m+\left({1\over\sqrt{2}}\right)^n\right]\delta<2\delta\left({1\over\sqrt{2}}\right)^n\cdots(2)
$$
As $2\delta$ is a constant and $\left({1\over\sqrt{2}}\right)< 1$, $(2)$ proves that $\{x_n\}$ is Cauchy and $(1)$ proves that it converges to $\alpha$.
As mentioned in the comments, there is no way to find a defining formula for a infinite sequence from a finite initial segment because given any finite list there are infinitely many ways to extend it.
That said, if you know ahead of time that the mystery sequence is defined by some recurrence and you know something about the structure of that recurrence, you can discover its formula.
For example: Given $a_0=1, a_1=4, a_2=9, a_3=16, \dots$ and the knowledge that our recurrence is a of the form $a_{n}=ba_{n-1}+cn+d$, we get that:
$$4=b(1)+c(0)+d, 9=b(4)+c(1)+d, \mbox{ and } 16=b(9)+c(2)+d$$
Thus $b+d=4$, $4b+c+d=9$, $9b+2c+d=16$.
Solving this (linear) system yields $b=1$, $c=2$, and $d=-1$. So that $a_n = a_{n-1}+2n-1$.
This is essentially the same process as polynomial curve fitting.
The main problem with all of this is knowing what your formula should look like to begin with. Without making some assumption about the shape of your formula, solving such a problem is hopeless (because the problem is ill defined).
Best Answer
Here’s a completely different approach. Divide the recurrence by $a_n$ to get
$$\frac{a_{n+1}}{a_n}=1+\frac{2a_{n-1}}{a_n}=1+\frac2{a_n/a_{n-1}}\;.\tag{1}$$
If we set $b_n=\dfrac{a_{n+1}}{a_n}$, we can rewrite $(1)$ as $$b_n=1+\frac2{b_{n-1}}\;.\tag{2}$$
Since $a_0=0$ and $a_1=1$, we can’t define $b_0$, but $a_2=a_1+2a_0=1$, so $b_1=\dfrac11=1$. Then $b_2=3$, $b_3=\frac53$, $b_4=\frac{11}5$, $b_5=\frac{21}{11}$, $b_6=\frac{43}{21}$, and $b_7=\frac{85}{43}$. This is enough to show a clear pattern: if $b_n=\frac{c_n}{d_n}$ in lowest terms, it appears that
$$c_{n+1}=2c_n+(-1)^{n+1}\tag{3}$$
and
$$d_{n+1}=c_n\;,\tag{4}$$
so that $$b_{n+1}=\frac{c_{n+1}}{d_{n+1}}=\frac{2c_n+(-1)^{n+1}}{c_n}=2-\frac{(-1)^n}{c_n}\;.\tag{5}$$
It’s not too hard to use $(2)$ to prove $(3)$ and $(4)$ by induction on $n$. $(3)$ and the fact that $c_1=1$ imply that $\langle c_n:n\in\Bbb Z^+\rangle$ is a strictly increasing sequence of positive integers, and $(5)$ then allows us to calculate $\lim\limits_{n\to\infty}b_n$ very easily.