# How to prove $3a=2b+c$ if $u_{n}\big|v_{n}$

The sequence $\{u_{n}\}$, $\{v_{n}\}$ is defined by $$u_{0} =u_{1} =1,u_{n}=2u_{n-1}-3u_{n-2}(n\geq2)$$ $$v_{0} =a, v_{1} =b , v_{2}=c,v_{n}=v_{n-1}-3v_{n-2}+27v_{n-3} (n\geq3)$$ .There exists the positive integer $N$ such that when $n> N$ ,have $u_{n}\big|v_{n}$ . Prove that $$3a=2b+c$$

I have do following $$u_n=\dfrac{\left (1+i\sqrt{2}\right )^n+\left (1-i\sqrt{2}\right )^n}{2}$$ $$v_n=\alpha\cdot 3^n+\beta \cdot \left (-1-2i\sqrt{2} \right )^n+\gamma \cdot \left (-1+2i\sqrt{2} \right )^n$$

I think basics method does not works here.

Any ideas ?

## 1 Answer

Notice that if you write $p,q = 1 \pm \sqrt {-2}$ the characteristic roots of the first linear recurrence, the characteristic roots of the second are their products, $p^2,pq=3$, and $q^2$.
So an easy way to make a sequence satisfying the second one that also satisfies the divisibility condition is to multiply $u_n$ with another integer sequence satisfying the first one. In essence, this exercise shows that this is the only way to make them.

Some linear algebra with a sprinkle of Galois theory shows that the $\Bbb Q$-vector spaces of rational sequences that are solutions to those recurrence have dimension $2$ and $3$, generated over $\Bbb Q$ by $\{(p^n+q^n) ; \sqrt{-2}(p^n - q^n)\}$ for the first one and by $\{(p^{2n}+q^{2n}) ; (pq)^n = 3^n; \sqrt{-2}(p^{2n} - q^{2n})\}$ for the second one, and all those sequences are integer sequences.

From this we get that $u_n = \frac 12 (p^n + q^n)$ and there are rational numbers $x,y,z$ such that $v_n = x(p^{2n} + q^{2n}) + y(pq)^n + z\sqrt{-2}(p^{2n}-q^{2n})$.
We can scale $v_n$ by an nonzero integer without strengthening the hypothesis nor weakening the goal we need to prove, so we can assume that $x,y,z$ are integers to make things easier.

Then, if $u_n$ divides $v_n$ then it also divides $v_n - (p^n+q^n)(x(p^n+q^n)+z\sqrt{-2}(p^n-q^n)) = (y-2x)(pq)^n = (y-2x)3^n$.
Moreover, a quick induction shows that $3$ never divides $u_n$, and so $u_n$ divides $y-2x$ for all $n$.

Since $u_n$ is unbounded, we must have $y = 2x$. Then, $v_n = 2u_n (x(p^n+q^n)+z\sqrt{-2}(p^n-q^n))$, which implies that the sequence $v_n/u_n$ satisfies the same linear recurrence as $u_n$.

In particular, since the first three values of $u_n$ are $1,1,-1$ and the first three values of $v_n$ are $a,b,c$, the first three values of $v_n/u_n$ are $a,b,-c$, and thus $-c = 2b-3a$.