Math Help - Sequence

1. Sequence

Let $a_0, a_1, a_2,$ ... be a seqence of positive integers for which

$a_0=1,$
$a_{2n+1}=a_n$
$a_{2n+2}=a_n+a_{n+1}$

Prove that $a_n$ and $a_{n+1}$ are relatively prime for every nonnegative integer $n$.

$a_0=1$
$n=0, \:a_1=1, \:\:a_2=2$
$n=1, \:a_3=1, \:\:a_4=3$
$n=2, \:a_5=2, \:\:a_6=3$
$n=3, \:a_7=1, \:\:a_8=4$
$n=4, \:a_9=3, \:a_{10}=5$
$n=5, \:a_{11}=2, \:a_{12}=5$
$n=6, \:a_{13}=3, \:a_{14}=4$
$n=7, \:a_{15}=1, \:a_{16}=5$
$n=8, \:a_{17}=4, \:a_{18}=7$
...
...
...
There doesn't seem to be a discernable pattern, but any how, I think these can be approached by Strong Induction.

The basis case is easy. $gcd(a_0,a_1)=gcd(1,1)=1$ is obvious.

The Inductive step: Assume $gcd(a_k,a_{k+1})=gcd(a_{2p+1}, a_{2p+2})=gcd(a_p,a_{p+1})=1$. We show that $gcd(a_{k+1},a_{k+2})=1$, $p \in \mathsb{z}^+ \cup {0}$

I can't see the recurrence relation for $a_k$. Need help.

2. Perhaps solved

I think I have found the general expression for $a_k$.

$a_k=a_{k-1}+(-1)^k a_{k-2}$

3. I'm a tad confused by the OP: isn't $a_{2n+2}=a_{2n+2}$ a tautology? What is the original problem, here?

4. Originally Posted by novice
$a_0=1$
$n=0, \:a_1=1, \:\:a_2=2$
$n=1, \:a_3=1, \:\:a_4=3$
$n=2, \:a_5=2, \:\:a_6=3$
$n=3, \:a_7=1, \:\:a_8=4$
$n=4, \:a_9=3, \:a_{10}=5$
$n=5, \:a_{11}=2, \:a_{12}=5$
$n=6, \:a_{13}=3, \:a_{14}=4$
$n=7, \:a_{15}=1, \:a_{16}=5$
$n=8, \:a_{17}=4, \:a_{18}=7$
This sequence is Stern's Diatomic Series.

Originally Posted by Ackbeet
I'm a tad confused by the OP: isn't $a_{2n+2}=a_{2n+2}$ a tautology? What is the original problem, here?
Stern's Diatomic Series is defined as $a_0=0,\;a_1=1,\;\begin{cases}a_{2n}=a_n,\; n\text{ is even}\\a_{2n+1}=a_n+a_{n+1},\; n\text{ is odd}\end{cases}$

Now for the proof, base case: $(a_0,a_1)=(0,1)=1$.

Assume $(a_m,a_{m+1})=1$ for all $m.

Case 1: $k=2n$ which gives $(a_{2n},a_{2n+1})=(a_n,a_n+a_{n+1})$.

By the IH, there exists $x,y\in\mathbb{Z}$ such that $xa_n+ya_{n+1}=1\implies (x-y)a_n+y(a_n+a_{n+1})=1\implies (a_n,a_n+a_{n+1})=1$

Therefore $(a_k,a_{k+1})=1$

Case 2: $k=2n+1$ which gives $(a_{2n+1},a_{2n+2})=(a_n+a_{n+1},a_{n+1})$.

By the IH, there exists $x,y\in\mathbb{Z}$ such that $xa_n+ya_{n+1}=1\implies x(a_n+a_{n+1})+(y-x)a_{n+1}=1\implies (a_n+a_{n+1},a_{n+1})=1$

Therefore $(a_k,a_{k+1})=1$

So by strong induction the claim $(a_n,a_{n+1})=1$ for all $n\in\mathbb{N}$ holds.

5. I apologize. It's $a_{2n+2}=a_n+a_{n+1}$

6. You are quite amazing. You made it look so simple.

7. Originally Posted by novice
You are quite amazing. You made it look so simple.
You'll have to modify the proof a bit, as our definitions of the sequence slightly differ.

8. Originally Posted by novice
I think I have found the general expression for $a_k$.

$a_k=a_{k-1}+(-1)^k a_{k-2}$
Fyi this is wrong as it says $a_6=5$ when actually $a_6=3$.

9. Originally Posted by chiph588@
Fyi this is wrong as it says $a_6=5$ when actually $a_6=3$.
Yes, thank you. I plotted the results, and saw that the curves didn't meet. I felt embarrassed.
You didn't do it to me, but I did to myself quite often.