Prove that F_n divides F_{kn} using induction

1 reply · 2K views · last reply
hangainlover
Messages
77
Reaction score
0

Homework Statement


I have proved the first one and I am trying to do the second using the result from part 1)


Homework Equations



[itex]F_1=1, F_2=2, F_n=F_{n-1}+F_{n-2}[/itex]

The Attempt at a Solution


base case: [itex]F_1|F_k[/itex] since[itex]F_1=1[/itex]

Assume it works for n, [itex]F_n|F_{kn}[/itex]
show [itex]F_{n+1}|F_{kn+k}[/itex]

Well, using the part 1)
[itex]F_{kn+k}=F_kF_{kn+1}+F_{k-1}F_{kn}[/itex]

That's as far as i could go..
 
Attachments
  • Printed exercise 6.4.9 asking to prove two Fibonacci identities for natural numbers n and k with k at least 2: (1) F(n+k) = F_k F_{n+1} + F_{k-1} F_n, and (2) F_n divides F_{kn}.
    cc.JPG
    10.2 KB · Views: 443
I have uplloaded the problem statement in the attachment
sorry i forgot to mention that
 
Last edited: