1. ## Sequence

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

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

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

$\displaystyle a_0=1$
$\displaystyle n=0, \:a_1=1, \:\:a_2=2$
$\displaystyle n=1, \:a_3=1, \:\:a_4=3$
$\displaystyle n=2, \:a_5=2, \:\:a_6=3$
$\displaystyle n=3, \:a_7=1, \:\:a_8=4$
$\displaystyle n=4, \:a_9=3, \:a_{10}=5$
$\displaystyle n=5, \:a_{11}=2, \:a_{12}=5$
$\displaystyle n=6, \:a_{13}=3, \:a_{14}=4$
$\displaystyle n=7, \:a_{15}=1, \:a_{16}=5$
$\displaystyle 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. $\displaystyle gcd(a_0,a_1)=gcd(1,1)=1$ is obvious.

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

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

2. ## Perhaps solved

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

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

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

4. Originally Posted by novice
$\displaystyle a_0=1$
$\displaystyle n=0, \:a_1=1, \:\:a_2=2$
$\displaystyle n=1, \:a_3=1, \:\:a_4=3$
$\displaystyle n=2, \:a_5=2, \:\:a_6=3$
$\displaystyle n=3, \:a_7=1, \:\:a_8=4$
$\displaystyle n=4, \:a_9=3, \:a_{10}=5$
$\displaystyle n=5, \:a_{11}=2, \:a_{12}=5$
$\displaystyle n=6, \:a_{13}=3, \:a_{14}=4$
$\displaystyle n=7, \:a_{15}=1, \:a_{16}=5$
$\displaystyle 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 $\displaystyle a_{2n+2}=a_{2n+2}$ a tautology? What is the original problem, here?
Stern's Diatomic Series is defined as $\displaystyle 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: $\displaystyle (a_0,a_1)=(0,1)=1$.

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

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

By the IH, there exists $\displaystyle x,y\in\mathbb{Z}$ such that $\displaystyle 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 $\displaystyle (a_k,a_{k+1})=1$

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

By the IH, there exists $\displaystyle x,y\in\mathbb{Z}$ such that $\displaystyle 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 $\displaystyle (a_k,a_{k+1})=1$

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

5. I apologize. It's $\displaystyle 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 $\displaystyle a_k$.

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

9. Originally Posted by chiph588@
Fyi this is wrong as it says $\displaystyle a_6=5$ when actually $\displaystyle 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.