Results 1 to 9 of 9

Math Help - Sequence

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    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.
    Last edited by novice; July 9th 2010 at 05:34 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Sep 2009
    Posts
    502

    Perhaps solved

    I think I have found the general expression for a_k.

    a_k=a_{k-1}+(-1)^k a_{k-2}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    I'm a tad confused by the OP: isn't a_{2n+2}=a_{2n+2} a tautology? What is the original problem, here?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by novice View Post
    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.

    Quote Originally Posted by Ackbeet View Post
    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<k .

    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.
    Last edited by chiph588@; July 9th 2010 at 04:49 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Sep 2009
    Posts
    502
    I apologize. It's a_{2n+2}=a_n+a_{n+1}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Sep 2009
    Posts
    502
    You are quite amazing. You made it look so simple.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by novice View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by novice View Post
    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 .
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by chiph588@ View Post
    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.
    Last edited by novice; July 9th 2010 at 07:59 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: August 24th 2010, 02:10 AM
  2. Replies: 0
    Last Post: July 4th 2010, 12:05 PM
  3. Replies: 2
    Last Post: March 1st 2010, 11:57 AM
  4. sequence membership and sequence builder operators
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 4th 2009, 03:16 AM
  5. Replies: 12
    Last Post: November 15th 2006, 12:51 PM

Search Tags


/mathhelpforum @mathhelpforum