Help with proof regarding fibonacci sequence
The Fibonacci sequence is given:
A1 = A2 = 1 , An = An-1 + An-2
For m >= 1 and n >= 1 Prove that Amn is divisible by Am.
I have already prepared and proved by induction a Lemma which is:
For m >= 2 and n > = 1. Fibonacci sequence satisfies:
Am+n = Am-1An + AmAn+1
The consequence of the Lemma allows me to rewrite Amn as:
Am(k+1)= Amk+m = Amk-1Am + AmkAm+1.
So now, I believe I'm suppose to convert that equation to
Amk+m = Am(Some integer).
Been going at it for hours, I'm starting to think I'm approaching it wrong. Thanks in advance!!!
Re: Help with proof regarding fibonacci sequence
You can prove that Amk is divisible by Am by induction on k. Then the first term of Amk-1Am + AmkAm+1 is clearly divisible by Am and the second term is divisible by the induction hypothesis.