Author |
Topic: n-th Fibonacci divides kn-th Fibonacci (Read 841 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
n-th Fibonacci divides kn-th Fibonacci
« on: Mar 9th, 2006, 9:54am » |
 Quote  Modify
|
Let F(1)=F(2)=1 and, for n>0, F(n+2)=F(n+1)+F(n) be the Fibonacci sequence. Then, for all positive integers n and k, F(n) divides F(kn).
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: n-th Fibonacci divides kn-th Fibonacci
« Reply #1 on: Mar 9th, 2006, 10:59pm » |
Quote Modify
|
Express Fnk in terms of Fn and Fn-1.
A follow up question: what is gcd(Fn, Fm)?
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: n-th Fibonacci divides kn-th Fibonacci
« Reply #2 on: Mar 10th, 2006, 1:45pm » |
Quote Modify
|
Here is one way of accomplishing Barukh's hint:
For any sequence gn satisfying gn = gn-1 + gn-2, if g1 = A and g2 = B, then gn = BFn-1 + AFn-2, as can easily be verified by induction. In particular gi = Fm+i works, which gives us the formula:
Fm+i = Fm+2Fi-1 + Fm+1Fi-2
Let m = kn-1, i = n+1, and you have the formula
F(k+1)n = Fkn+1Fn + FknFn-1.
Hence, if Fn divides Fkn, then it also divides F(k+1)n. And the result follows by induction.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: n-th Fibonacci divides kn-th Fibonacci
« Reply #3 on: Mar 10th, 2006, 2:27pm » |
Quote Modify
|
Wow, Icarus! Your first paragraph mercilessly shames my tortured approach to the same result! Very nice!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print