# 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?

• have you tried induction? Sep 16, 2016 at 5:00
• @LeGrandDODOM If I knew the formula and I was supposed to only prove that the formula meets the equation then I would have done so, but my question is how can one find the formula out of the recurrence equation? Sep 16, 2016 at 5:03
• the solution you've found... it looks exactly like the solution to a homogeneous linear recurrence relations of order $2$, so I guess your recurrence equation can be rewritten as such. Sep 16, 2016 at 5:14
• Note that $(1+\sqrt{2})(1-\sqrt{2}) = 1-2 = -1$. Sep 16, 2016 at 5:19

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$
• Neat. But you use the untold assumption that $a_{n-1}, a_{n+1}$ are distinct roots of $r^2 - 6 r + 1$, which misses valid solutions such as $1,7,1,7,...$ per @stewbasic's answer.
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}$.