2
$\begingroup$

I have a recursive formula: $$ a_n= 6a_{n-1} -4a_{n-2}$$ with $a_0=1$ and $a_1=3$, and I need to find a closed-form expression of $(a_n)_{n\in \mathbb{N}}$.

I managed to calculate almost everything but at the end I get this expression: $$ a_n= \frac{(3+\sqrt{5})^n}{2} + \frac{(3-\sqrt{5})^n}{2} $$

Is there a way to prove the following statement? Because Everything I have tried up till now doesn't do the job, and are these two expressions equal at all?

$$ \frac{(3+\sqrt{5})^n}{2} + \frac{(3-\sqrt{5})^n}{2} = \left \lceil \frac{(3+\sqrt5)^n}{2} \right \rceil$$

$\endgroup$
1
$\begingroup$

Note that $3-\sqrt5$ is a little less than $0.764$, so $0<\frac{(3-\sqrt5)^n}2<\frac12$ for all $n\ge 1$. The lefthand side of your final expression must be an integer; call it $m$. Thus,

$$0<m-\frac{(3+\sqrt5)^n}2<\frac12\;,$$

and it follows immediately that

$$m=\left\lceil\frac{(3+\sqrt5)^n}2\right\rceil\;.$$

For this it’s actually enough that $\frac{(3-\sqrt5)^n}2<1$; the fact that it’s less than $\frac12$ allows the stronger conclusion that $a_n$ is actually the integer closest to $\frac{(3+\sqrt5)^n}2$ for $n\ge 1$.

$\endgroup$
4
  • 1
    $\begingroup$ Did you mean $0<\frac{(3\color{red}-\sqrt5)^n}2<\frac12$? $\endgroup$ May 10 '20 at 17:52
  • $\begingroup$ @J.W.Tanner: Ouch! Yes, I certainly did; thanks! $\endgroup$ May 10 '20 at 17:54
  • $\begingroup$ Do you have idea what combinatorial question might be behind OP recursive formula? $\endgroup$
    – Aqua
    May 10 '20 at 17:57
  • $\begingroup$ @Aqua: Nothing comes to mind immediately. It could simply be an exercise in finding the closed form of a recursively defined sequence. $\endgroup$ May 10 '20 at 18:05
1
$\begingroup$

Here is a hint:

${3-\sqrt5}<1$

$\endgroup$
2
  • $\begingroup$ Do you have idea what combinatorial question might be behind OP recursive formula? $\endgroup$
    – Aqua
    May 10 '20 at 17:58
  • 1
    $\begingroup$ Cf. OEIS $\endgroup$ May 10 '20 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.