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.
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?
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.
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?
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.
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.
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.
The proof is OK now, but there are a couple of smaller remarks.
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.
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.