Your question's too long: subdivide it in several ones if you need to. Let us focus on the Fibonacci question:
We assume that , and we now take n+1:
the second equality stems from the inductive hypothesis and the last one is just the definitiom
of the Fibonacci series.