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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ have you tried induction? $\endgroup$– Gabriel RomonSep 16, 2016 at 5:00
-
1$\begingroup$ @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? $\endgroup$– Kay K.Sep 16, 2016 at 5:03
-
1$\begingroup$ 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. $\endgroup$– Gabriel RomonSep 16, 2016 at 5:14
-
$\begingroup$ Note that $(1+\sqrt{2})(1-\sqrt{2}) = 1-2 = -1$. $\endgroup$– marty cohenSep 16, 2016 at 5:19
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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$
-
1$\begingroup$ 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. $\endgroup$– dxivSep 16, 2016 at 5:38
$\begingroup$
$\endgroup$
0
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}$.
