Show that $u_{n+1}=6u_n-4u_{n-1}$ if $u_n=(3+\sqrt{5})^n+(3-\sqrt{5})^n$ for $n=1,2,...$

Question

I have already shown that for each $n,u_n$ is an integer.

Now we can show that $u_n=\dfrac{1}{2^n}(\sqrt{5}+1)^{2n}+\dfrac{2^{3n}}{(\sqrt{5}+1)^{2n}}$

But the problem is while showing $u_{n+1}=6u_n-4u_{n-1}$ , I can see that the whole calculation is taking pages. Is there any shortcut, crisp way of proving it?

PS - I am not showing here the gory, intricate calculations here that cost me pages as this might make the users viewing it, uneasy.

Answer 1

Or that way $$u_{n+1}-6u_n+4u_{n-1} = 0$$ If $t$ is a solution of $t^2 -6t +4 = (t-3)^2 - 5 = 0$ then $u_n = t^n$ is a solution of the recursion:

$$t^{n+1} - 6t^n + 4 t^{n-1} = t^{n-1}(t^2 - 6t + 4) = 0$$ You can quickly see that if you have two solutions $t_1, t_2$ of above quadratic equation, then any linear combination $at_1^n + bt_2^n$ is also a solution of the recursion.

Answer 2

Write $a=3+\sqrt5$, $b=3-\sqrt5$. Then $u_n=a^n+b^n$. Also $$u_{n+1}-6u_n+4u_{n-1}=a^{n+1}-6a^n+4a^{n-1}+b^{n+1}-6b^n+4b^{n-1} =(a^2-6a+4)a^{n-1}+(b^2-6b+4)b^{n-1}$$ etc. You need this to equal zero.

Answer 3

Hint Let $a_n=(3+\sqrt{5})^n$, can you show that $a_{n+1}=6a_n-4a_{n-1}$ and the same for $b_n=(3-\sqrt{5})^n$ ?