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.
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?
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.
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?
There is no reason to consider the case r = 0 because induction is on q.
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.
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.
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.
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.
The proof is OK now, but there are a couple of smaller remarks.
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.
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.
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.