1
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ have you tried induction? $\endgroup$ Sep 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$ Sep 16, 2016 at 5:14
  • $\begingroup$ Note that $(1+\sqrt{2})(1-\sqrt{2}) = 1-2 = -1$. $\endgroup$ Sep 16, 2016 at 5:19

2 Answers 2

6
$\begingroup$

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$

$\endgroup$
1
  • 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$
    – dxiv
    Sep 16, 2016 at 5:38
4
$\begingroup$

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}$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .