# Sequence

• Jul 9th 2010, 11:19 AM
novice
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.
• Jul 9th 2010, 02:05 PM
novice
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}$
• Jul 9th 2010, 02:56 PM
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?
• Jul 9th 2010, 04:10 PM
chiph588@
Quote:

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.

Quote:

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.
• Jul 9th 2010, 05:35 PM
novice
I apologize. It's $\displaystyle a_{2n+2}=a_n+a_{n+1}$
• Jul 9th 2010, 05:40 PM
novice
You are quite amazing. You made it look so simple.
• Jul 9th 2010, 05:55 PM
chiph588@
Quote:

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.
• Jul 9th 2010, 06:00 PM
chiph588@
Quote:

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$.
• Jul 9th 2010, 07:43 PM
novice
Quote:

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.