Hey Guys, learning discrete math by myself and while I was working with a proof, I got stuck, I checked the solution and I understand the big picture but I can't seem to understand the arithmetic, here's how it goes:

By induction Let P(n) be the proposition that Fn and Fn+1 are relatively prime.

Base case: P (0) is true because F0 = 0 and F1 = 1 are relatively prime.

Inductive step: We show that, for all n ≥ 0, P(n) implies P(n + 1). So, fix some n ≥ 0and assume that P (n) is true, that is, Fn and Fn+1 are relatively prime. We will show thatFn+1 and Fn+2 are relatively prime as well. We will do this by contradiction.

Suppose Fn+1 and Fn+2 are not relatively prime. Then they have a common divisor d > 1.But then d also divides the linear combinationFn+2 − Fn+1, which actually equals Fn. Hence, d > 1 divides both Fn and Fn+1. Which implies Fn, Fn+1 are not relatively prime, a contradiction to the inductive hypothesis.

Therefore, Fn+1 and Fn+2 are relatively prime. That is, P (n + 1) is true.

How in the hellFn+2 − Fn+1equals Fn ??