Results 1 to 12 of 12
Like Tree3Thanks
  • 1 Post By Plato
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Nuber Theory and Sequences

  1. #1
    Newbie
    Joined
    May 2013
    From
    morroco
    Posts
    14
    Thanks
    1

    Nuber Theory and Sequences

    Hello MHF, Here's a problem that I couldn't solve, could anyone help me.

    - Here's the things i already figured out :
    U(1) = U(2) = 1
    U(n+1) = U(n) + U(n-1) \ n is greater than 2
    U(n+p) = U(n) * U(P-1) + U(n+1) * U(p)

    Show that GCD(U(n+p),U(n)) = GCD(U(n), U(p))
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,403
    Thanks
    1486
    Awards
    1

    Re: Nuber Theory and Sequences

    Quote Originally Posted by Orpheus View Post
    Hello MHF, Here's a problem that I couldn't solve, could anyone help me.
    - Here's the things i already figured out :
    U(1) = U(2) = 1
    U(n+1) = U(n) + U(n-1) \ n is greater than 2
    U(n+p) = U(n) * U(P-1) + U(n+1) * U(p)
    Show that GCD(U(n+p),U(n)) = GCD(U(n), U(p))
    That is a nice question. Do you plan to show any effort or discussion on it?
    Thanks from Orpheus
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2013
    From
    morroco
    Posts
    14
    Thanks
    1

    Re: Nuber Theory and Sequences

    of course, in fact I'm now still trying to solve it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2013
    From
    morroco
    Posts
    14
    Thanks
    1

    Re: Nuber Theory and Sequences

    Quote Originally Posted by Plato View Post
    That is a nice question. Do you plan to show any effort or discussion on it?
    I think i should show that U(n+p) = U(n) * K + U(p) but i couldn't do it.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,418
    Thanks
    718

    Re: Nuber Theory and Sequences

    Quote Originally Posted by Orpheus View Post
    U(1) = U(2) = 1
    U(n+1) = U(n) + U(n-1) \ n is greater than 2
    U(n+p) = U(n) * U(P-1) + U(n+1) * U(p)
    Is the third line a part of the definition of U, just like the first two lines? If not, then it should be indicated.

    Quote Originally Posted by Orpheus View Post
    I think i should show that U(n+p) = U(n) * K + U(p) but i couldn't do it.
    There is no constant K that works for all n and p. For example, for p = 2, K has to be 1 for n = 1, and K has to be 2 for n = 2.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2013
    From
    morroco
    Posts
    14
    Thanks
    1

    Re: Nuber Theory and Sequences

    Quote Originally Posted by emakarov View Post
    Is the third line a part of the definition of U, just like the first two lines? If not, then it should be indicated.

    There is no constant K that works for all n and p. For example, for p = 2, K has to be 1 for n = 1, and K has to be 2 for n = 2.
    - Yes the third part is a part of the definition, and is true for all n and p that are greater than 2
    - K is not a constant, i mean i could show that U(p) is the remainder of the division of U(n+p) on U(n).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,418
    Thanks
    718

    Re: Nuber Theory and Sequences

    Quote Originally Posted by Orpheus View Post
    U(1) = U(2) = 1
    U(n+1) = U(n) + U(n-1) \ n is greater than 2
    U(n+p) = U(n) * U(P-1) + U(n+1) * U(p)
    Quote Originally Posted by Orpheus View Post
    - Yes the third part is a part of the definition, and is true for all n and p that are greater than 2
    That's not the response I was hoping for. Look at the first two lines. The first line defines U at 1 and 2. The second line defines U at 3 when n = 2. Indeed, the right-hand side refers to U(2) and U(1), which are already defined. Similarly, it defined U at 4 when n = 3, and in general it defines U at every n ≥ 2. So, what can the third line add? At best it agrees with what the first two lines say; at worst it contradicts them. But it is not a part of the definition; it is a separate claim. It turns out that this claim is true and is given as a lemma without a proof to be used in this problem.

    Not knowing the definitions involved in a statement is worse than not being able to prove that statement, but here are further hints anyway. Replace U(n+p) with U(n) * U(p-1) + U(n+1) * U(p) in GCD(U(n+p), U(n)) and use the following facts.

    Proposition 1. GCD(kn + m , n) = GCD(m, n) for k ∈ ℤ.
    Proposition 2. GCD(U(n+1), U(n)) = 1. Proof: By induction on n.
    Proposition 3. If GCD(m, n) = 1, then GCD(km, n) = GCD(k, n).
    Thanks from Orpheus
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    May 2013
    From
    morroco
    Posts
    14
    Thanks
    1

    Re: Nuber Theory and Sequences

    Quote Originally Posted by emakarov View Post
    That's not the response I was hoping for. Look at the first two lines. The first line defines U at 1 and 2. The second line defines U at 3 when n = 2. Indeed, the right-hand side refers to U(2) and U(1), which are already defined. Similarly, it defined U at 4 when n = 3, and in general it defines U at every n ≥ 2. So, what can the third line add? At best it agrees with what the first two lines say; at worst it contradicts them. But it is not a part of the definition; it is a separate claim. It turns out that this claim is true and is given as a lemma without a proof to be used in this problem.

    Not knowing the definitions involved in a statement is worse than not being able to prove that statement, but here are further hints anyway. Replace U(n+p) with U(n) * U(p-1) + U(n+1) * U(p) in GCD(U(n+p), U(n)) and use the following facts.

    Proposition 1. GCD(kn + m , n) = GCD(m, n) for k ∈ ℤ.
    Proposition 2. GCD(U(n+1), U(n)) = 1. Proof: By induction on n.
    Proposition 3. If GCD(m, n) = 1, then GCD(km, n) = GCD(k, n).
    the 3rd line is the previous question in this exercice and I already solved it, I tought it may be used in this question that's why i put there.
    as for GCD(U(n+1), U(n)) = 1 I proved it with induction.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,418
    Thanks
    718

    Re: Nuber Theory and Sequences

    Quote Originally Posted by Orpheus View Post
    the 3rd line is the previous question in this exercice and I already solved it, I tought it may be used in this question that's why i put there.
    as for GCD(U(n+1), U(n)) = 1 I proved it with induction.
    Good, then proving GCD(U(n+p), U(n)) = GCD(U(n), U(p)) should not be hard.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    May 2013
    From
    morroco
    Posts
    14
    Thanks
    1

    Re: Nuber Theory and Sequences

    Quote Originally Posted by emakarov View Post
    Good, then proving GCD(U(n+p), U(n)) = GCD(U(n), U(p)) should not be hard.
    I couldn't do it, because i tought the only way is by showing that U(p) is the remainder of U(n+p) divised by U(n)
    and I don't see how can i use those propositions.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,418
    Thanks
    718

    Re: Nuber Theory and Sequences

    GCD(U(n+p), U(n))
    = GCD(U(n) * U(p-1) + U(n+1) * U(p), U(n))
    = GCD(U(n+1) * U(p), U(n)) by Proposition 1
    = GCD(U(p), U(n)) by Propositions 2 and 3.

    The sequence U(n) is called Fibonacci numbers. A similar fact is discussed here.
    Thanks from Orpheus
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    May 2013
    From
    morroco
    Posts
    14
    Thanks
    1

    Re: Nuber Theory and Sequences

    Quote Originally Posted by emakarov View Post
    GCD(U(n+p), U(n))
    = GCD(U(n) * U(p-1) + U(n+1) * U(p), U(n))
    = GCD(U(n+1) * U(p), U(n)) by Proposition 1
    = GCD(U(p), U(n)) by Propositions 2 and 3.

    The sequence U(n) is called Fibonacci numbers. A similar fact is discussed here.
    OHH I see thank you, I tought that i couldn't use a product of two numbers for the first proposition that was dumb of me.
    anyway thank you.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 8
    Last Post: September 24th 2011, 07:33 AM
  2. theory of sequences and series
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 5th 2010, 03:28 AM
  3. Monotone sequences and Cauchy sequences
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: March 21st 2009, 08:59 PM
  4. graphical sequences - graph theory
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 3rd 2008, 09:31 PM
  5. Replies: 5
    Last Post: January 16th 2008, 04:51 PM

Search Tags


/mathhelpforum @mathhelpforum