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

• Nov 11th 2013, 11:59 PM
jtoem
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.
• Nov 12th 2013, 04:58 AM
emakarov
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.
• Nov 15th 2013, 01:23 AM
jtoem
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?
• Nov 15th 2013, 07:44 AM
emakarov
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 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
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.
• Nov 15th 2013, 08:15 AM
SlipEternal
Re: If a divides b, then a's Fib number divides b's Fib number
Edit: Post deleted
• Nov 17th 2013, 12:48 PM
jtoem
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.
• Nov 17th 2013, 01:15 PM
emakarov
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
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 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.
• Nov 18th 2013, 10:45 AM
jtoem
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.
• Nov 18th 2013, 12:33 PM
emakarov
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 Far = Fb 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 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
what about the base case, is it OK to take the base case as one?

Yes.
• Nov 19th 2013, 11:49 PM
jtoem
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.
• Nov 20th 2013, 02:40 AM
emakarov
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 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
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.
• Nov 20th 2013, 10:32 PM
jtoem
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.