Sequence is defined by $a_0 = 3$, $a_1 = 7$ and $a_n = 2^na_{n-1}+(-1)^na_{n-2}$. Prove that gcd($a_n,a_{n-1}$) = 1 for all natural numbers n.

Question

I have started using my base case where n=1, which is simple gcd(7,3)=1 is obviously true.

So I can assume that P(k) holds (gcd($a_n,a_{n-1})=1$), now I have to prove P(k+1). I believe using strong induction is needed here, but not positive, if so I would assume P(1)...P(k) holds.

I know $a_{n+1} = 2^{n+1}a_n+(-1)^{n+1}a_{n-1}$, and $a_n$ is equal to what is given in the sequence. After this point I've tried using Bezout's Lemma and the fact that the gcd will divide both of these, but keep getting stuck. I have no clue where I could apply my induction hypothesis or how to get it into a form where I can even apply this.

Any help is appreciated.

Answer 1

By definition, $GCD(a_{n+1} \ , a_{n})$ divide both $a_{n+1}$ and $a_{n}$.

Since $a_{n+1}=2^{n+1}\ a_{n+1}\ + (-1)^{n+1}\ a_{n-1}$, $GCD(a_{n+1}\ a_{n})$ also divide $a_{n-1}$. Consequently, if $GCD(a_{n} \ , a_{n-1})=1$, then $GCD(a_{n+1} \ , a_{n})=1$

Because $GCD(3 , 7)=1$, then $GCD(a_{n+1} \ , a_{n})=1$ for all $n$ by induction.

Answer 2

It's special case $\,b_n = 2^{n+1},\ c_n = (-1)^{n+1}\,$ below, where $(x,y)$ denotes $\gcd(x,y),\,$ where we essentially employ the Euclidean algorithm to compute the gcd.

Lemma $ $ If $\,a_{n+1} = b_n a_n + c_n a_{n-1}$ and $(a_n,c_n)=1\,$ both hold true for for all $\,n\ge 1$ then it follows that $\,(a_{n+1},a_n) = (a_1,a_0)\,$ for all $\,n\ge 0$.

Proof $ $ Induct on $n$. Clear if $n = 0.\ $ Else it follows by induction via Euclidean modular reduction

$$\begin{align} (a_{n+1},a_n) &= (b_n a_n + c_n a_{n-1},\, a_n)\\[.2em] &= (c_n a_{n-1},\, a_n)\ \ {\rm by\ Euclidean\ modular\ reduction}\\[.2em] &= (a_{n-1},\,a_n)\ \ \ \ \ \ {\rm by}\ \ (c_n,a_n) = 1\ \ {\rm and\ Euclid's\ Lemma}\\[.2em] &= (a_1,a_0)\ \ \ \ \ \ \ \ \ \ \ {\rm by\ induction} \end{align}$$