gcd for fibonacci numbers number of steps proof I have to proof $gcd(F_{n+1},F_{n+2})$ need at least n steps to get gcd(we have to use version with subtraction).
My try
After first step we get $gcd(F_{n+1} - F_{n+2},F_{n+2})=gcd(F_{n+1},F_{n})$
After second step we get $gcd(F_{n+1}-F_{n},F_{n})=gcd(F_{n-1},F_{n})$
After n-th step we get $gcd(F_{3}-F_{2},F_{2})=gcd(F_{1},F_{2})$
So after n+1-th step we get $gcd(F_{1},F_{2}-F_{1})=gcd(F_{1},F_{0})$
That show us we need n+1 steps to get gcd of 2 fibonnaci numbers.
But it isn't formaly (I'm not sure that's proof) could someone help me how that should looks correctly  
 A: First, you have a small mistake:

After first step we get $gcd(F_{n+1} - F_{n+2},F_{n+2})=gcd(F_{n+1},F_{n})$

This should be:

After first step we get $gcd(F_{n+1},F_{n+2}-F_{n+1})=gcd(F_{n+1},F_{n})$

since $F_{n+2} > F_{n+1}$ (for $n > 0$)
Second, here is what a more formal (inductive) proof would look like:
Claim: For any $n$, it takes at least $n$ steps to compute $gcd(F_{n+1},F_{n+2})$
Proof by (weak) induction:
Base: $n=0$: $gcd(F_1,F_2)= gcd(1,1)=1$.  OK, so that took $0$ or $1$ steps, depending on how you count. If we count the number of subtractions, it is $0$. So yes, it takes (at least) $0$ steps to compute $gcd(F_1,F_2)$.
Step: Suppose that for some arbitrary $k$ we have that it takes at least $k$ steps to compute $gcd(F_{k+1},F_{k+2})$ . Now consider $k+1$, i.e. let's see how many steps it takes to compute $gcd(F_{(k+1)+1},F_{(k+1)+2})$. Well:
$$gcd(F_{(k+1)+1},F_{(k+1)+2}) =$$
$$gcd(F_{(k+1)+1},F_{(k+1)+2}-F_{(k+1)+1})=$$
$$gcd(F_{k+2},F_{k+1}) =$$
$$gcd(F_{k+1},F_{k+2})$$
Since by our inductive assumption this last one takes at least $k$ steps to compute, it will take at least $k+1$ steps to compute $gcd(F_{(k+1)+1},F_{(k+1)+2})$, because we added at least one more subtraction operation. Since this is what we needed to show, we have now completed the inductive step, and thereby the inductive proof.
A: It looks acceptable to me, but to make it more formal you could start from the bottom (use induction). That means first show it for $n=0$ and then prove the claim for $n=k$ implies the claim for $n=k+1$, $k$ some integer.
