Proof by contradiction
Suppose that $\{X_n\}$ does not converge to $\ell$. Then, there is $\varepsilon_0>0$ such that $$\forall N\in\mathbb N,\exists n=n(N) : n>N~~~and ~~~ |X_n -\ell|>\varepsilon_0 $$
For $N_1=1$ there exists $n_1$ such that
$$n_1>N_1 ~~~and ~~~ |X_{n_1} -\ell|>\varepsilon_0 $$
Taking successively $N_{k+1}> \max\{N_k, n_k,k+1\}$ there exists $n_{k+1}>N_{k+1}$ such that,
$$ |X_{ n_{k+1}} -\ell|>\varepsilon_0 $$
It is easy to see that, $\{X_{ n_k}\}_k$ is a subsequence of $\{X_{ n}\}_n$
since
$$ n_k< n_{k+1} \quad i.e ~~\text{the map }~~k\mapsto n_k~~~\text{Is one-to-one}$$
However, $$\forall k,~~ |X_{ n_{k}} -\ell|>\varepsilon_0 \qquad \text{and}~~~\{X_{ n_{k}} \}~~~\text{is bounded} $$
Therefore By Bolzano-Weierstrass Theorem's there exists $\{X_{ n_{k_p} }\}_p$ subsequence of $\{X_{ n_{k} }\}_k$ which converges to some limit $\ell_1 $
but $\{X_{ n_{k_p} }\}_p\to \ell_1$ is also a converging subsequence of $\{X_n\}_n$
By assumption, $\ell=\ell_1$ that is together with the fact $\{X_{ n_{k_p} }\}_p$ is a subsequence of $\{X_{ n_{k} }\}_k$ we have
$$0=\lim_{p\to\infty } |X_{ n_{k_p} }-\ell|>\varepsilon_0>0~~~\text{which is a CONTRADICTION}$$
Note that
$$\forall p,~~|X_{ n_{k_p} }-\ell|>\varepsilon_0$$
Since
$$\forall k,~~|X_{ n_{k}} -\ell|>\varepsilon_0$$
Here's a more formal (and shorter) proof:
Let $(x_{n_k})$ be a convergent subsequence of $(x_n)$, which we know exists, and let $L$ be its limit. Then, given any $\varepsilon > 0$, there is some $K \in \mathbb{N}$ such that for all $k \geq K$, $|x_{n_k} - L| < \varepsilon$ (this is the definition of the limit).
Now, for any $n \geq n_K$, we will show than $|x_n - L| < \varepsilon$, which will complete the proof. For this purpose, suppose that this is not true. Then there is some $n \geq n_K$ such that $|x_n - L| \geq \varepsilon > |x_{n_K} - L|$.
First, note that if $x_1 \leq L$ then we must have $x_i \leq L$ for all $i$: if not, then we have some $i$, such that $x_1 \leq L < x_i$, but then for all $m > i$, $x_m \geq x_i > L$, so $|x_m - L| \geq |x_i - L| > 0$, so in particular, $(x_{n_k})\not\to L$, a contradiction. Symmetrically, if $x_1 \geq L$, then $x_i \geq L$ for all $i$.
Now, we have a problem: we have either $x_n \geq L + \varepsilon > x_{n_K} \geq L$ or $x_n\leq L - \varepsilon < x_{n_K} \leq L$, but then monotonicity gives us either $x_m \geq L + \varepsilon$ or $x_m \leq L - \varepsilon$ for all $m \geq n$, in particular for all but finitely many $n_k$, so $|x_{n_k} - L| \geq \varepsilon$ for all but finitely many $n_k$, so $(x_{n_k})\not\to L$, a contradiction.
Thus, we must have $|x_n - L| <\varepsilon$ for all $n \geq n_K$, hence $(x_n)\to L$.
Best Answer
Let $L$ be the positive solution to $L = 1+\frac{1}{1+L}$. It's really easy to solve for $L$, but even without explicitly solving for $L$ we can still show that the sequence converges to $L$ if we know that $a_n\ge 0$ for all $n$.
To do so, notice that $$a_{n+1}-L = \left(1+\frac{1}{1+a_n}\right) - \left(1 + \frac{1}{1+L}\right) = \frac{1}{1+a_n} - \frac{1}{1+L} = \frac{L-a_n}{(1+a_n)(1+L)}$$ and hence $$|a_{n+1}-L|\le\frac{1}{1+L}\frac{1}{1+a_n}|a_n-L|\le\frac{1}{1+L}|a_n-L|$$ since $a_n\ge 0\implies 1+a_n\ge 1$. Since $L$ is positive, $\frac{1}{1+L}<1$, so $$|a_n-L|\le\left(\frac{1}{1+L}\right)^{n-1}|a_1-L|\xrightarrow{n\rightarrow\infty}0.$$