0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ use mathjax to edit mathematical symbols. $\endgroup$ – Praveen Jan 22 '15 at 14:08
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.