Playing around with sequences, I observed the following:
Take $a_1=b_1=1$ and $a_2=b_2=k$ for fixed $k$ with $1<k<2$.
Prove that if $a_{n+2}=\frac{a_{n+1}^2-1}{a_n}$ and $b_{n+2}=kb_{n+1}-b_n$,
then $a_n=b_n, \forall n \in \mathbb{N}.$
This can be shown by guessing $a_n=\frac{2}{4-k^2}\sin[\cos^{-1}(\frac{k}{2})n]$ and using the formula $\sin(\alpha+x)\sin(\alpha-x)=\sin^2(\alpha)-\sin^2(x)$ to derive the recurrence, and guessing $b_n=r^n$ and solving for the coefficients of the linearly independent solutions, then comparing the closed forms of $a_n$ and $b_n$.
Can anyone however come up with a non-"Deus Ex Machina" proof, say by induction?
Rewriting the relation about $a_n$, we get for $n\geq 2$ $$1=a^2_{n+1}-a_na_{n+2}=a^2_{n}-a_{n-1}a_{n+1} $$ Hence $$a_{n+1}\left(a_{n+1}+a_{n-1}\right)=a_n\left(a_{n}+a_{n+2}\right)\Leftrightarrow \\ \frac{a_n+a_{n+2}}{a_{n+1}}=\frac{a_{n+1}+a_{n-1}}{a_{n}} $$ Since this is true for all $n\geq 2$, we can substitute $n=2$ in the RHS. We calculate $a_3=k^2-1$. So $$\frac{a_n+a_{n+2}}{a_{n+1}}=\frac{a_3+a_1}{a_2}=\frac{k^2-1+1}{k}=k \Leftrightarrow \\ a_{n+2}=ka_{n+1}-a_n $$ It can be manually checked the last relation holds for $n=1$ as well. So $a_n=b_n$ for all $n\in\mathbb{N}$. For a complete proof, we need to justify the division by $a_n$, that is, we need to show $a_n\ne 0$.