$T_1=1,T_2=3,T_n=2T_{n-1}+T_{n-2}$, where $n\ge3$ GCD$(T_n,T_{n-1})=1$

Question

We have sequence

$T_1=1,T_2=3,T_n=2T_{n-1}+T_{n-2}$, where $n\ge3$

I need to prove that for every natural number $n\ge2$, GCD$(T_n,T_{n-1})=1$

Any ideas how to prove it? I noticed that first five member of this sequence is a prime number, except $T_6=99$, and then there goes primes again. How to prove it in general?

Answer 1

Hint for induction: $\gcd(x,y)=\gcd(x+y,y)$.

(This is true because $x,y$ and $x+y,y$ have the same sets of common divisors!)

Answer 2

We have $$ \begin{pmatrix}T_{n+2} \\ T_{n+1} \end{pmatrix} =\begin{pmatrix}2&1\\1&0\end{pmatrix} \begin{pmatrix}T_{n+1} \\ T_{n} \end{pmatrix} $$ The matrix has determinant $-1$ and so is invertible over the integers.

Therefore, the common divisors of $T_{n+2}, T_{n+1}$ are exactly the same as the common divisors of $T_{n+1}, T_{n}$. The result follows by induction since $\gcd(T_1,T_0)=1$.