How can I turn $(a_n-a_{n-1})^2-4a_na_{n-1}-8=0$ into $a_n=\frac12\left((1+\sqrt2)^{2n+1}+(1-\sqrt2)^{2n+1}\right)$? I was solving a complex problem and ended up with a recurrence equation:
$$(a_n-a_{n-1})^2-4a_na_{n-1}-8=0\quad(a_0=1)$$
The only thing I could do was to solve it as a quadratic equation and I got:
$$a_n=3a_{n-1}+2\sqrt{2a_{n-1}^2+2}$$
and I was stuck. But after calculations I found that all the numbers in the sequence are integer ($1$ $7$ $41$ $239$ $1393$ $8119$ $47321$ $275807$ $1607521$ $\dots$) and figured out it's a sequence called A002315. And this link https://oeis.org/A002315 had a general formula that is:
$$a_n=\frac12\left((1+\sqrt2)^{2n+1}+(1-\sqrt2)^{2n+1}\right)$$
I have no idea how one can reach this formula from the above recurrence equation. Can somebody help?
 A: since
$$a^2_{n-1}-6a_{n}a_{n-1}+a^2_{n}-8=0$$
and
$$a^2_{n+1}-6a_{n}a_{n+1}+a^2_{n}-8=0$$
so $a_{n-1},a_{n+1}$ is $t^2-6a_{n}t+a^2_{n}-8=0$ roots
then
$$a_{n-1}+a_{n+1}=6a_{n}$$
so $r^2+1=6r$,then
$r=3+2\sqrt{2},3-2\sqrt{2}$
then 
$$a_{n}=A(3+\sqrt{2})^{n-1}+B(3-2\sqrt{2})^{n-1}$$
since
$a_{1},a_{2}$ you can find $A,B$
A: A lot of this answer comes from the benefit of hindsight from seeing the solution you found, but anyway here are some ideas.

Note that the recurrence relation has the form
$$
  f(a_n,a_{n-1})=0
$$
where $f$ is a symmetric polynomial of degree $2$. It follows that
$$
  f(x,y)-f(y,z)
$$
is a degree $2$ polynomial which vanishes when $x=z$. Thus
$$
  f(x,y)-f(y,z)=(x-z)g(x,y,z)
$$
where $g$ is linear. Now you have
$$
  0=f(a_n,a_{n-1})-f(a_{n-1},a_{n-2})=(a_n-a_{n-2})g(a_n,a_{n-1},a_{n-2}).
$$
If we assume $a_n\neq a_{n-2}$ for all $n$, then
$$
  g(a_n,a_{n-1},a_{n-2})=0.
$$
Thus we have a linear recurrence which we can solve in the usual way.
Note that we actually can have $a_n=a_{n-2}$. In fact your equation has two solutions for $a_n$ for most values of $a_{n-1}$, so your recurrence doesn't have a unique solution. Here is another solution:
$$
  1,7,1,7,1,\ldots
$$
If we assume the $a_n$ are strictly increasing then we have $a_n>a_{n-2}$.
