# Two recurrence relations gcd proof

Let $q_1, q_2,\ldots$ be a sequence of integers with $q_i\gt0$ for all $i\gt 1$. Define $(a_n)_{n\ge-1}$ and $(b_n)_{n\ge-1}$ by the following recurrence relations: $a_{-1}=0,\ a_0=1,\ b_{-1}=1,\ b_0=0$. And $\forall n\ge1$ $$a_n=q_n\cdot a_{n-1}+a_{n-2}\qquad\text{and}\qquad b_n=q_n\cdot b_{n-1}+b_{n-2}.$$

Prove that:

1. $a_n\cdot b_{n-1}-b_n\cdot a_{n-1}=(-1)^n$, $\forall n\ge-1$
2. $\gcd(a_n, b_n)=1, \forall n\ge-1$

I did 1. fine by induction, but can't seem to show 2. the same way...maybe I need to use 1)? Any help is appreciated!

• use mathjax to edit mathematical symbols. – Praveen Jan 22 '15 at 14:08

Use the fact that $\gcd(a_n,b_n)$ must divide any $\mathbb Z$-linear combination of $a_n$ and $b_n.$ With that, we see from 1. that we must indeed have $\gcd(a_n,b_n) = 1.$