Fibonacci sequence proof via contraposition So we know $F_{0} = 0, F_{1} = 1$, and for all $n ≥ 2, F_{n} = F_{n−1} + F_{n−2}$ for the Fibonacci Sequence. How do we prove that for every natural number $n$, $gcd(F_{n}, F_{n+1}) = 1$?
I can make sense that we will prove the contrapositive of the induction step.
And also that only the two following properties will be useful: \begin{align}
∀n ∈ N, gcd(0, n) = n \tag{I}
\\
∀n, a, b, p, q ∈ Z, n | a ∧ n | b ⇒ n | (ap + bq) \tag{II}
\end{align}
 A: Now, the Fibonacci sequence can be written as $$F_n=F_{n-1}+F_{n-2}$$ and we want to prove $$\forall n\in \mathbb{N},\ gcd(F_n,F_{n+1})=1$$
        We will let this statement be $P(n)$.
(Note that the Fibonacci sequence can also be written as $F_{n+2}=F_{n+1}+F_{n}$ and we will use this to our advantage.)
For the base case, $n=0$:
\begin{align*}
   gcd(F_n,F_{n+1})&=gcd(F_0,F_1)\\
   &=gcd(0,1) \\
   &=1 && \text{(Using Claim 1)}
  \end{align*}
        So $P(0)$ holds.
Now, assuming $P(k)$ holds for $n=k$, we let $g=gcd(F_k,F_{k+1})$.
Then $g \mid F_k \land g \mid F_{k+1}$ by the definition of the $gcd$(greatest common divisor).
By Claim 2,\begin{align*}
   g \mid \overbrace{F_k + F_{k+1}}^\text{their sum} \land \ g \mid \overbrace{F_{k+1}-F_k(=F_{k-1})}^\text{their difference} && \text{(by the definition of the Fibonacci sequence)}\\
  \end{align*}
So we know $ gcd(F_{k},F_{k+1})=1$ and $ gcd(F_{k-1},F_{k})=1$ by this and assuming that $P(k)$ holds.
In order to prove $P(k+1)$ for $n=k+1$, observe that:
            \begin{align*}
    gcd(F_n,F_{n+1})&=gcd(F_{k+1},F_{k+2})\\
    &=gcd(F_{k+1},F_{k+1}+F_k)\\
    &=1 && \text{(as we showed earlier using Claim 2 that the sum is also divisible)}\\
    \text{Then $g=1$.}\\
    \text{This proves $P(k+1)$.}
    \end{align*}
