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.

Thanks