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

The hint is to use F_{a+b} = F_{a}F_{b+1} + F_{a-1}F_{b}.

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.

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

Quote:

Originally Posted by

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

Use induction on q.

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 F_{b }= 0, so b = 1 and if b = 1, a must equal 1

and if q = 1, then a = b and of course F_{a} = F_{b}

assume, as an inductive hypothesis, that since there is a q such that aq = b there is an r such that F_{a}r = F_{b}

now i just need to show that there is such an r for a(q+1) = b?

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

Quote:

Originally Posted by

**jtoem** assume a divides b

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

now if q = 0, then F_{b }= 0, so b = 1 and if b = 1, a must equal 1

and if q = 1, then a = b and of course F_{a} = F_{b}

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 F_{0} = 0, and so every number divides F_{0} as well.

Quote:

Originally Posted by

**jtoem** assume, as an inductive hypothesis, that since there is a q such that aq = b there is an r such that F_{a}r = F_{b}

now i just need to show that there is such an r for a(q+1) = b?

Yes.

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

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 F_{a(q+1)} = F_{b}

i expand then right side, F_{a(q+1)} = F_{a}F_{b+1} + F_{a-1}F_{b}

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.

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

F_{1} = 0; F_{2} = 1; F_{n+2} = F_{n} + F_{n+1} for n ≥ 1.

Is this correct?

Quote:

Originally Posted by

**jtoem** 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** 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** 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 F_{a(q+1)} = F_{b}

i expand then right side, F_{a(q+1)} = F_{a}F_{b+1} + F_{a-1}F_{b}

then i play aroudn and look for a way to apply the inductive hypothesis.

Yes. The inductive hypothesis is that F_{a} divides F_{b}, so the conclusion is now obvious. The only technical remark is that F_{a-1} does not exist if a = 1 according to the definition above, so the case a = 1 has to be treated separately.

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 F_{a} divides F_{b}

i assume that it does, to show that that implication holds larger q.

aq = b implies there is an r such that F_{a}r = F_{b}

comment: a previous result is that if a > 1, F_{a+b} = F_{a}F_{b+1} + F_{a-1}F_{b} and we assume the first Fibonnaci number, F_{1}, 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 F_{0}=0, so that r = 0.

but if q is 1, then a = b and F_{a}r = F_{b} where r = 1 and a,b are >= 1

*** now we take a,b > 1 such that a(q+1) = b ***

then F_{a(q+1)} = F_{b}

or F_{aq + a}, which is F_{b + a}

so, by the equality mentioned in the comment, F_{b}F_{a+1} + F_{b-1}F_{a} = F_{b}

but I am assuming that F_{a}r = F_{b}, so F_{a}rF_{a+1} + F_{b-1}F_{a} = F_{b}

or F_{a}(rF_{a+1} + F_{b-1}) = F_{b}

and there we have it because that is an expression of F_{b} as a product of F_{a} 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.

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

Quote:

Originally Posted by

**jtoem** but if q is 1, then a = b and F_{a}r = F_{b} where r = 1 and a,b are >= 1

This is a good base case.

Quote:

Originally Posted by

**jtoem** *** 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** then F_{a(q+1)} = F_{b}

or F_{aq + a}, which is F_{b + a}

Here and below, you are using b in two senses: as aq and as a(q+1).

Quote:

Originally Posted by

**jtoem** what about the base case, is it OK to take the base case as one?

Yes.

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 F_{a}(r) = F_{b}

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

F_{a(q+1)} = F_{c}

F_{aq + a} = F_{c}

F_{aq}F_{a+1} + F_{aq-1}F_{a} = F_{c}

since b = aq, F_{b} = F_{aq} and F_{b} = F_{a}(r)

F_{a}(r)F_{a+1} + F_{aq-1}F_{a} = F_{c}

F_{a}(rF_{a+1} + F_{aq-1}) = F_{c}

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.

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** assume: aq = b implies there is an r such that F_{a}(r) = F_{b}

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** then, a(q+1) = c for c>1 and a>=1

F_{a(q+1)} = F_{c}

F_{aq + a} = F_{c}

F_{aq}F_{a+1} + F_{aq-1}F_{a} = F_{c}

since b = aq, F_{b} = F_{aq} and F_{b} = F_{a}(r)

F_{a}(r)F_{a+1} + F_{aq-1}F_{a} = F_{c}

It is still not clear why F_{aq-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, F_{a} = 1 and so F_{a} | F_{b} for any b.

Here is how I would write it.

Prove: If a | b, then F_{a} | F_{b}.

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

Let P(q) be the following statement: F_{a} | F_{aq}. 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., F_{a} | F_{aq}. Need to prove: P(q+1), i.e., F_{a} | F_{a(q+1)}. But F_{a(q+1)} = F_{aq+a} = F_{aq}F_{a+1} + F_{aq-1}F_{a}. Here aq - 1 >= 1 because a > 1 and q >= 1, so F_{aq-1} is defined. Since F_{a} | F_{aq} by the induction hypothesis, we have F_{a} | F_{aq}F_{a+1} + F_{aq-1}F_{a}, 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.

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.