# Math Help - Fibonacci/Euclidean Algorithmn proof

1. ## Fibonacci/Euclidean Algorithmn proof

Let u sub n be the nth Fibonacci number. Prove that the Euclidean algorithm takes precisely n steps to prove that gcd(u sub n+1, u sub n)=1

2. $u_{n+1} = 1\cdot u_n + u_{n-1}$
$u_{n} = 1\cdot u_{n-1}+u_{n-2}$
...

Keep on going until you reach the final step.