Results 1 to 12 of 12
Like Tree1Thanks
  • 1 Post By jtoem

Math Help - If a divides b, then a's Fib number divides b's Fib number

  1. #1
    Newbie
    Joined
    Nov 2013
    From
    Madagascar
    Posts
    7
    Thanks
    1

    If a divides b, then a's Fib number divides b's Fib number

    The hint is to use Fa+b = FaFb+1 + Fa-1Fb.

    What i keep trying:

    a divides b => there is a q in Z such that aq = b.

    so aq + a = b + a, and then i use the hint.

    But i never get anywhere.

    I want to use that if a divides b and a divides c then a divides mb + nc for m,n in Z, but i can't figure out how/ I tried to let c = a, but I got nowhere.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: If a divides b, then a's Fib number divides b's Fib number

    Quote Originally Posted by jtoem View Post
    a divides b => there is a q in Z such that aq = b.
    Use induction on q.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2013
    From
    Madagascar
    Posts
    7
    Thanks
    1

    Re: If a divides b, then a's Fib number divides b's Fib number

    ok so, to use induction on q:

    assume a divides b
    by def of division, there is a q in Z such that aq = b

    now if q = 0, then Fb = 0, so b = 1 and if b = 1, a must equal 1

    and if q = 1, then a = b and of course Fa = Fb

    assume, as an inductive hypothesis, that since there is a q such that aq = b there is an r such that Far = Fb

    now i just need to show that there is such an r for a(q+1) = b?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: If a divides b, then a's Fib number divides b's Fib number

    Quote Originally Posted by jtoem View Post
    assume a divides b
    by def of division, there is a q in Z such that aq = b

    now if q = 0, then Fb = 0, so b = 1 and if b = 1, a must equal 1

    and if q = 1, then a = b and of course Fa = Fb
    Hmm, don't you think it is strange that aq = b and q = 0 imply that b = 1?

    If q = 0, then b = 0 and every number a divides 0. But hopefully F0 = 0, and so every number divides F0 as well.

    Quote Originally Posted by jtoem View Post
    assume, as an inductive hypothesis, that since there is a q such that aq = b there is an r such that Far = Fb

    now i just need to show that there is such an r for a(q+1) = b?
    Yes.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,880
    Thanks
    742

    Re: If a divides b, then a's Fib number divides b's Fib number

    Edit: Post deleted
    Last edited by SlipEternal; November 15th 2013 at 08:46 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2013
    From
    Madagascar
    Posts
    7
    Thanks
    1

    Re: If a divides b, then a's Fib number divides b's Fib number

    i think i have made a bit of an error in saying 'now if q = 0, then Fb = 0, so b = 1 and if b = 1, a must equal 1'

    its more like if r = 0, then Fb = 0, so b =1, since the first fib number is 0. and of course Fa can be whatever, since anything times 0 is 0. this case is a bit werid because if b = 1, then a = q = 1. generally, q and r are not the same; i guess that is for q > 1. a pattern is that as q increases by one, b increases by a factor of a.

    but if q is 0, then b is 0, like you said, and a can be anything. actually, tho, this case shouldn't arise right? since there is no zeroth fib number.

    i want to know about this hint. when i try to do the inductive step:

    aq = b
    aq + a = b + a
    a(q+1) = a + b
    then Fa(q+1) = Fb
    i expand then right side, Fa(q+1) = FaFb+1 + Fa-1Fb
    then i play aroudn and look for a way to apply the inductive hypothesis.

    is that the right way, or are you clueing me in on a way without the hint?

    i noticed that if q is 2, then r is the sum of the two previous r's, like 2*2=4, 3*2=6, 4*2=8 and on the fib side of things 1*3=3, 2*4=8, 3*7=21 where seven is r. that struck me but i quickly lost interest in looking for a pattern for higher q's in the sort of incremental increase of a and b approach.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: If a divides b, then a's Fib number divides b's Fib number

    Let's agree on the definition of Fibonacci numbers. The indices (e.g., a, b) may start from 0 or from 1, and the first Fibonacci number may be 0 or 1, so there are at least four variants. From what you wrote, the definition seems to be

    F1 = 0; F2 = 1; Fn+2 = Fn + Fn+1 for n ≥ 1.

    Is this correct?

    Quote Originally Posted by jtoem View Post
    its more like if r = 0, then Fb = 0
    There is no reason to consider the case r = 0 because induction is on q.

    Quote Originally Posted by jtoem View Post
    this case is a bit werid because if b = 1, then a = q = 1. generally, q and r are not the same; i guess that is for q > 1.
    There is nothing strange about a = b and q = 1. Induction has to start somewhere. If the first index is 1, then induction on q starts from q = 1, and the base case is trivial.

    Quote Originally Posted by jtoem View Post
    i want to know about this hint. when i try to do the inductive step:

    aq = b
    aq + a = b + a
    a(q+1) = a + b
    then Fa(q+1) = Fb
    i expand then right side, Fa(q+1) = FaFb+1 + Fa-1Fb
    then i play aroudn and look for a way to apply the inductive hypothesis.
    Yes. The inductive hypothesis is that Fa divides Fb, so the conclusion is now obvious. The only technical remark is that Fa-1 does not exist if a = 1 according to the definition above, so the case a = 1 has to be treated separately.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2013
    From
    Madagascar
    Posts
    7
    Thanks
    1

    Re: If a divides b, then a's Fib number divides b's Fib number

    After a brief search, i conclude that it isn't against the forum rules to post proofs. still, since much of the work has already been posted, i will not go into every detail.


    So i am trying to prove that a divides b implies Fa divides Fb
    i assume that it does, to show that that implication holds larger q.
    aq = b implies there is an r such that Far = Fb
    comment: a previous result is that if a > 1, Fa+b = FaFb+1 + Fa-1Fb and we assume the first Fibonnaci number, F1, is 1, contrary to other of my posts. (i checked and this is the definition of the book i am using). if q is 0, then a*0=b implies b is zero, but there is no zeroth fib number according to my book, so this might be a problem. if so, i want to say that the F0=0, so that r = 0.
    but if q is 1, then a = b and Far = Fb where r = 1 and a,b are >= 1
    *** now we take a,b > 1 such that a(q+1) = b ***
    then Fa(q+1) = Fb
    or Faq + a, which is Fb + a
    so, by the equality mentioned in the comment, FbFa+1 + Fb-1Fa = Fb
    but I am assuming that Far = Fb, so FarFa+1 + Fb-1Fa = Fb
    or Fa(rFa+1 + Fb-1) = Fb
    and there we have it because that is an expression of Fb as a product of Fa and an integer.


    two issues:

    what about the base case, is it OK to take the base case as one? there are are no negative Fib numbers, and no Fib numbers of negative numbers, so i think q must b in Z+ or we must state the theorem with the Fibonacci numbers of the absolute values of a and b.

    i dont really understand is the starred step; is it OK?


    thanks for your patience on this.
    Last edited by jtoem; November 18th 2013 at 10:50 AM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: If a divides b, then a's Fib number divides b's Fib number

    Quote Originally Posted by jtoem View Post
    but if q is 1, then a = b and Far = Fb where r = 1 and a,b are >= 1
    This is a good base case.

    Quote Originally Posted by jtoem View Post
    *** now we take a,b > 1 such that a(q+1) = b ***
    No need to require a > 1; we may allow a = 1.

    Quote Originally Posted by jtoem View Post
    then Fa(q+1) = Fb
    or Faq + a, which is Fb + a
    Here and below, you are using b in two senses: as aq and as a(q+1).

    Quote Originally Posted by jtoem View Post
    what about the base case, is it OK to take the base case as one?
    Yes.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Nov 2013
    From
    Madagascar
    Posts
    7
    Thanks
    1

    Re: If a divides b, then a's Fib number divides b's Fib number

    You are right, I used b = aq and b = a(q+1). That is not OK.

    To fix it, can't I just introduce a new number, c?

    assume: aq = b implies there is an r such that Fa(r) = Fb

    base case: if q is 1, then a = b and Far = Fb where r = 1 and a,b are >= 1

    then, a(q+1) = c for c>1 and a>=1

    Fa(q+1) = Fc
    Faq + a = Fc
    FaqFa+1 + Faq-1Fa = Fc
    since b = aq, Fb = Faq and Fb = Fa(r)
    Fa(r)Fa+1 + Faq-1Fa = Fc
    Fa(rFa+1 + Faq-1) = Fc

    The proposition is true because if you assume it is true for some q, it is true for the next q, even if b changes.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: If a divides b, then a's Fib number divides b's Fib number

    The proof is OK now, but there are a couple of smaller remarks.

    Quote Originally Posted by jtoem View Post
    assume: aq = b implies there is an r such that Fa(r) = Fb

    base case: if q is 1, then a = b and Far = Fb where r = 1 and a,b are >= 1
    The first line in the quote you need to prove, not assume. You do assume it as the induction hypothesis, but this happens during the proof of the induction step, after the base case.

    Quote Originally Posted by jtoem View Post
    then, a(q+1) = c for c>1 and a>=1

    Fa(q+1) = Fc
    Faq + a = Fc
    FaqFa+1 + Faq-1Fa = Fc
    since b = aq, Fb = Faq and Fb = Fa(r)
    Fa(r)Fa+1 + Faq-1Fa = Fc
    It is still not clear why Faq-1 makes sense, i.e., why aq > 1. You assumed that a(q+1) > 1, but if a = 1 and you are making the induction step from q = 1 to q = 2, then aq = 1. Fortunately, Fa = 1 and so Fa | Fb for any b.

    Here is how I would write it.

    Prove: If a | b, then Fa | Fb.

    If a = 1, then Fa = 1 and the statement is obvious. For the rest of the proof, assume that a > 1.

    Let P(q) be the following statement: Fa | Faq. We prove P(q) by induction on q.

    Base case: q = 1. Then P(q) is "Fa | Fa", which is obviously true.

    Induction step. Assume the induction hypothesis P(q), i.e., Fa | Faq. Need to prove: P(q+1), i.e., Fa | Fa(q+1). But Fa(q+1) = Faq+a = FaqFa+1 + Faq-1Fa. Here aq - 1 >= 1 because a > 1 and q >= 1, so Faq-1 is defined. Since Fa | Faq by the induction hypothesis, we have Fa | FaqFa+1 + Faq-1Fa, which concludes the induction step and the proof.

    Note that I used only variables a and q instead of a, b, c, q and r, which makes it easier to grasp the proof.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Nov 2013
    From
    Madagascar
    Posts
    7
    Thanks
    1

    Re: If a divides b, then a's Fib number divides b's Fib number

    I think you are right that it is better to make clear the statement to be proved and the inductive hypothesis. Also, my proof does not make clear that the fib number of aq-1 exists. It is remedied by saying that a is strictly greater than one after the base case, you did.

    In your proof, mentioning these points helps. I noticed that I used the definition of division while you used the fact that if a divides b and a divides c then a divides mb + nc for m,n in Z, which in my book, is called something like the linear combination lemma. It is much nicer with just the two variables. Thanks for your guidance.
    Thanks from emakarov
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: October 25th 2012, 05:19 AM
  2. Replies: 3
    Last Post: October 8th 2011, 04:16 PM
  3. Replies: 2
    Last Post: May 1st 2011, 02:11 PM
  4. Replies: 7
    Last Post: December 25th 2010, 10:50 PM
  5. any number can divides infinity???
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: August 19th 2009, 11:58 PM

Search Tags


/mathhelpforum @mathhelpforum