# Given $a_n= 6a_{n-1} -4a_{n-2}$ and initial values, find a closed form for $a_n$

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

## 2 Answers

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

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

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

Here is a hint:

$${3-\sqrt5}<1$$

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