Fibonacci Induction Proofs
I have 2 proofs relating to Fibonacci numbers and each other.
1. F_m+n = (F_m-1)(F_n) + (F_m)(F_n+1) for m≥1 and n≥0. (_ indicates subscript)
So far I have,
I am letting m be fixed and using induction on n.
Basis: n = 0, LHS: F_(m+0) = F_m
RHS: F_(m-1)*F_(0) + F_(m)*F_(0+1) = F_m
Induction Hypothesis: n = k, F_(m+k) = F_(m-1)*F_k + F_m*F_(k+1)
Induction Step: n=k+1, F_[m+(k+1)] = F_(m-1)*F_(k+1) + F_m*F_[(k+1)+1]
I am not sure where to go from here, can anyone help?
Then 2. Prove that for all m≥1 and n≥1, F_m divides F_(m*n). I am to do induction on n and use what I found in part 1 to help.