I have the following problem:
Let $a$, $b$ be positive integers and $(x_{n})_{n\geq 0}$ be a sequence of integers defined by the following formulas:
$x_{0}=0$,
$x_{1}=a$,
$x_{n}=x_{n-2}+bx_{n-1}$ for $n \geq 2$.
Compute $\gcd(x_{n}, x_{n+1})$ for all $n$.
After writing out a few terms, I have noticed that the $\gcd$ appears to be $a$:
$\gcd(x_{0},x_{1}) = \gcd(0,a) = a$
$\gcd(x_{1},x_{2}) = \gcd(a,ab) = a$
$\gcd(x_{2},x_{3}) = \gcd(ab, a+ab^{2}) = \gcd(ab,a(1+b^{2})) = a$
$\gcd(x_{3},x_{4}) = \gcd(a+ab^{2}, 2ab+ab^{3}) = \gcd(a(1+b^{2}), a(2b+b^{3})) = a$
etc.
Now, in order to prove this rigorously, I assume that I would have to show it by induction on n.
The problem with this is that I am having difficulty getting $x_{n}$ into a form where I could easily factor out $a$. I noticed that $x_{5} = a+3ab^{2}+ab^{4}$, and attempted to use this information in order to help me correctly predict the form that $x_{6}$ would take without actually writing it out; however, I was unsuccessful.
I'm not even sure if this is the correct approach for proving recursive statements like this by induction, but if anyone could please help, I would appreciate it very much.
Note that $\gcd(\color{Blue}{X},\color{Green}{Y})=\gcd(X,Y-X)$. By induction, it also $=\gcd(\color{Blue}{X},\color{Purple}{Y-bX})$ for any $b$.
Then $\gcd(x_n,x_{n+1})=\gcd(\color{Blue}{x_n},\color{Green}{x_{n-1}+bx_n})=\gcd(x_n,\color{Purple}{x_{n-1}})=\gcd(x_{n-1},x_n)$. So induct.