I will use induction.For $\rm k=0$ we have $\rm y_{0+1}=y_1=1=x_1=x_{2^0}$ Let $\rm y_{r+1}=x_{2^r}$.We must show that $\rm y_{r+2}=x_{2^{r+1}}$ $\rm y_{r+2}=\dfrac{y_{r+1}^2+2}{2y_{r+1}}=\dfrac{x^2_{2^r}+2}{2x_{2^r}}$.So we must show that $\rm \dfrac{x^2_{2^r}+2}{2x_{2^r}}=x_{2^{r+1}}$. For this it suffice to show that $\rm \dfrac{x^2_t+1}{2x_t}=x_{2t},\forall t\in \mathbb{N^*}$. To prove this i will use induction.We have $\rm x_2=\dfrac{x_1+2}{x_1+1}=\dfrac{3}{2}$,so for $\rm t=1$ we have $\rm \dfrac{x_1^2+1}{2x_1}=\dfrac{3}{2}=x_{2\cdot1}$ Let $\rm \dfrac{x_r^2+1}{2x_r}=x_{2r}$.We must show that $\rm \dfrac{x^2_{r+1}+1}{2x_{r+1}}=x_{2(r+1)}$ $\rm x_{2r+2}=\dfrac{x_{2r+1}+2}{x_{2r+1}+1}=..=\dfrac{3x_{2r}+4}{2x_{2r}+3}=..=\dfrac{3x^2_r+8r+6}{2x^2_r+6x_r+4}$ Since $\rm x_{r+1}=\dfrac{x_r+2}{x_r+1}$ we have $\rm \dfrac{x^2_{r+1}+1}{2x_{r+1}}=..=\dfrac{3x^2_r+8r+6}{2x^2_r+6x_r+4}=x_{2r+2}$ qed.

Define $(a_n)_{n\geq 1}$ and $(b_n)_{n\geq 1}$ by $a_1=b_1=1$ and $a_{n+1}=a_n+2b_n$, $b_{n+1}=a_n+b_n$. This way $x_n=\frac{a_n}{b_n}$ (by induction, say). Lemma: The following are true: $$a_{2n}=2b_n^2+a_n^2 \text{ , } b_{2n}=2a_nb_n$$Proof: Write the recurrence relation in matrix notation $$\left(\begin{array}{cc} a_{n+1}&a_n\\ b_{n+1}&b_n\end{array}\right)=\left(\begin{array}{cc} 1&2\\ 1&1\end{array}\right)\left(\begin{array}{cc} a_n&a_{n-1}\\ b_n&b_{n-1}\end{array}\right)\implies \left(\begin{array}{cc} a_{n+1}&a_n\\ b_{n+1}&b_n\end{array}\right)=\left(\begin{array}{cc} 1&2\\ 1&1\end{array}\right)^{n-1}\left(\begin{array}{cc} 3&1\\ 2&1\end{array}\right)=\left(\begin{array}{cc} 1&2\\ 1&1\end{array}\right)^n\left(\begin{array}{cc} 1&1\\ 1&0\end{array}\right)$$ Now $$\left(\begin{array}{cc} a_{2n+1}&a_{2n}\\ b_{2n+1}&b_{2n}\end{array}\right)=\left(\begin{array}{cc} 1&2\\ 1&1\end{array}\right)^{2n}\left(\begin{array}{cc} 1&1\\ 1&0\end{array}\right)=\left(\begin{array}{cc} 1&2\\ 1&1\end{array}\right)^n\left(\begin{array}{cc} 1&1\\ 1&0\end{array}\right)\left(\begin{array}{cc} 0&1\\ 1&-1\end{array}\right)\left(\begin{array}{cc} 1&2\\ 1&1\end{array}\right)^n\left(\begin{array}{cc} 1&1\\ 1&0\end{array}\right)=\left(\begin{array}{cc} a_{n+1}&a_n\\ b_{n+1}&b_n\end{array}\right)\left(\begin{array}{cc} 0&1\\ 1&-1\end{array}\right)\left(\begin{array}{cc} a_{n+1}&a_n\\ b_{n+1}&b_n\end{array}\right)$$ And hence we get the desired relations. $\blacksquare$ We show that $y_{n+1}=x_{2^n}$ by induction. For $n=1$ both sides are $\frac{3}{2}$, so the base case is verified. We will now make use of the following Identity: $$x_{2n}=\frac{x_n^2+2}{2x_n}$$Proof: Substitute $x_n=\frac{a_n}{b_n}$ and rewrite it as $$2x_{2n}x_n=2\frac{a_{2n}a_n}{b_{2n}b_n}=\frac{2a_na_{2n}}{2a_nb_n^2}=\frac{a_n^2+2b_n^2}{b_n^2}=\frac{a_n^2}{b_n^2}+2=x_n^2+2$$Which is equivalent to the proposition $\blacksquare$ This serves as the inductive step, so $x_{2^n}=y_{n+1}$. $\blacksquare$